牛客周赛105

牛客周赛 Round 105

grade

  • Rating: 1397(+41)
  • Rank: 188/1142
  • AC: 5/6

题解

题目描述

构造两个不相等的非负整数，使得两数的异或和等于k

$1\le k\le 10$

solution

1
2
3
4
5
6
7
8
void solve()
{
    // 目标值 k
    int k;
    cin >> k;
    // 0 ^ k = k
    cout << 0 << ' ' << k;
}

题目描述

求长度为n的数组的所有相邻元素异或结果的最大公因数

$2\le n\le 20$

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void solve()
{
    // 数组长度 n
    int n;
    cin >> n;
    
    // 读入数组
    vector<int> v(n);
    for (int i = 0; i < n; ++i)
        cin >> v[i];
    
    // 计算所有相邻元素异或结果
    vector<int> b(n - 1);
    for (int i = 0; i < n - 1; ++i)
        b[i] = v[i] ^ v[i + 1];
    
    // 求所有异或结果的最大公因数
    int ans = b[0];
    for (int i = 1; i < n - 1; ++i)
        ans = gcd(ans, b[i]);
        
    cout << ans;
}

题目描述

构造满足每行每列的异或和之和sum为k的n*n的01矩阵

$1\le n\le 10^3, 0\le k\le 2n$

eg:

0^1^1 = 0 0^0^0 = 0 0^1^0 = 1
0 0 0 0^0^0 = 0
1 0 1 1^0^1 = 0
1 0 0 1^0^0 = 1

sum = 0 + 0 + 1 + 0 + 0 + 1 = 2;

思路

记$sum_{xr}$为第$x$行异或和,$sum_{xl}$为第$x$列异或和
任意改变第i行第j列的数， 都会使$sum_{ir} = sum_{ir} \oplus 1, sum_{jl} =sum_{jl} \oplus 1$

显然二者之和的奇偶性不会改变

因为全0矩阵的 sum = 0

所以 sum 只能为偶数

一种简单的构造方法：初始化为全0矩阵， 对角线上每多一个1， sum += 2

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void solve()
{
    // n：矩阵大小 k：目标sum值
    int n, k;
    cin >> n >> k;
    
    // 如果k是奇数, 不存在
    if (k % 2)
    {
        cout << -1;
        return;
    }
    
    // 初始化矩阵全为'0'
    memset(arr, '0', sizeof arr);
    
    // 在矩阵对角线上设置 k/2 个‘1’
    for (int i = 0; i < k / 2; ++i)
        arr[i][i] = '1';
        
    // 输出矩阵
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
            cout << arr[i][j];
        cout << endl;
    }
}

题目描述

将仅由1或2组成的数组重排得到一个所有相邻元素最大公约数之和为 k 的数组

$2\le n \le 210^5; 0\le k \le 2n$

思路

eg:

arr[] = {1, 2, 2, 2, 1, 2}

sum = gcd(1,2) + gcd(2,2) + gcd(2,2) + gcd(2,1) + gcd(1,2) = 7

显然所能构造的最小情况为:{2, 1, 2, 1, 2, 2}
即用1尽量把2分开
sum = 6

所能构造的最大情况为:{2, 2, 2, 2, 1, 1}
即把2放在一起
sum = 8

构造 sum = k 只需先算出需要多少2放在一起， 剩下只需保证1和2相间即可

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
void solve()
{
    // n: 数组长度 k: 目标值
    int n, k;
    cin >> n >> k;
    
    // 统计数组中1和2的个数
    int cnt1 = 0, cnt2 = 0;
    int t;
    for (int i = 0; i < n; ++i)
        cin >> t, t == 1 ? ++cnt1 : ++cnt2;
        
    // 计算最小值和最大值
    int maxans = 2 * (cnt2 - 1) + cnt1;
    int minans;
    if (cnt2 <= cnt1 + 1)
        minans = n - 1; // 可以全被1隔开
    else
        minans = 2 * (cnt2 - 1); // 不能全被1隔开
        
    // 超出最大值和最小值
    if (k < minans || k > maxans)
    {
        cout << -1;
        return;
    }
    
    // 计算需要多少个2放在一起
    int cnt = k - n + 1;
    for (int i = 0; i <= cnt; ++i)
        cout << 2 << ' ';
    cnt2 -= cnt + 1;
    
    // 剩下的按 1 2 1 2 排列
    while (cnt2 && cnt1)
    {
        cout << 1 << ' ' << 2 << ' ';
        --cnt1, --cnt2;
    }
    while (cnt2)
    {
        cout << 2 << ' ';
        --cnt2;
    }
    while (cnt1)
    {
        cout << 1 << ' ';
        --cnt1;
    }
}

题目描述