Codeforces Round 1008 (Div.2) 题解

发表于 分类于 阅读次数： 本文字数： 5.8k
努力补题ing，希望能有所效果吧。

A

题意

给定一个数组 \(a\)，可以进行若干次操作：选择一个整数 \(k\) 满足 \(k\) 整除 $ a$，然后将 \(a\) 分为 \(k\) 部分，每部分变成这一部分的平均数。求是否能让数组最后只剩下一个数 \(x\)。

题解

由于每部分大小都相同，只需要所有元素的平均值为 \(x\) 即可。

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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, x;
    cin >> n >> x;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += a[i];
    }
    if (n * x == sum) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

B

题意

给定 \(n\) 个位置，每个位置 \(i\) 距离终点的距离是 \(n - i\)，给每一个位置连一条路径到其他位置，每个位置都有人，求让每个人必须沿着路径走 \(k\) 次，怎么连边才能走完 \(k\) 次后，再走向终点的路径长度最少。

题解

显然 \(k\) 为奇数的话就把 1 到 \(n-1\) 连向 \(n\)，\(n\) 连向 \(n-1\)，这样最后只有一个人到终点的距离为 1，其余都在终点了；如果 \(k\) 为偶数，就把 1 到 \(n - 2\) ，以及 \(n\) 连向 \(n-1\)，\(n-1\) 连向 \(n\)，这样也只有一个人到终点的距离为 1。注意特判 \(n = 2\)。

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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, k;
    cin >> n >> k;
    if (n == 2) {
        cout << "2 1\n";
        return;
    }
    if (k & 1) {
        for (int i = 1; i <= n - 1; i++) {
            cout << n << " ";
        }
        cout << n - 1 << "\n";
    } else {
        for (int i = 1; i <= n - 2; i++) {
            cout << n - 1 << " ";
        }
        cout << n << " " << n - 1 << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C

题意

有一个长度为 \(2n+1\) 的数组，满足奇数项之和和偶数项之和相等，且没有相同的元素。现在有一个数消失了，只知道其中 \(2n\) 个数，求出一种方案满足原来的条件。

题解

最棘手的就是没有相同的元素这一条件，我们不能让那个缺失的元素太小，不然很容易撞上相同的，考虑让它成为最大值，这样一定不会有相同的。由于原数组奇数比偶数多，我们不妨让大的数全部放在奇数，这样偶数位置就需要一个最大的数使得和等于奇数。（一个超级大哥才能带这一群小弟和对面的一群大哥打平）

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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n;
    cin >> n;
    vector<int> b(2 * n + 1), a(2 * n + 2);
    for (int i = 1; i <= 2 * n; i++) {
        cin >> b[i];
    }
    sort(b.begin() + 1, b.begin() + 2 * n + 1);
    int p = 2 * n;
    int res = 0;
    for (int i = 0; i <= n; i++) {
        a[2 * i + 1] = b[p--];
        res += a[2 * i + 1];
    }
    for (int i = 1; i <= n - 1; i++) {
        a[2 * i] = b[p--];
        res -= a[2 * i];
    }
    a[2 * n] = res;
    for (int i = 1; i <= 2 * n + 1; i++) {
        cout << a[i] << " \n"[i == 2 * n + 1];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D

题意

两个人参加两条赛道，初始一人在一条赛道，在 \(n\)​ 个决策点中，每个决策点有加法和乘法两种类型，运算后可以获得对应人数。每个决策点后新获得的人数可以任意分配到两条赛道，求最后的最大人数。

image-20250401012252191

题解

显然从前往后考虑的话需要考虑到之后的状态，尽可能往乘法较多的一边分配，因为加法获得的人是固定的，但是存在后效性并不好做。

不妨从后往前考虑，此时对于每个决策点优先选择乘法即可，如果都是乘法，选择数值更大的一边，如果数值相等，由前一个状态决定，这样我们即可知道每一个决策点的人数分配，模拟一遍过程求和即可。

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n;
    cin >> n;
    vector<int> op1(n + 1), op2(n + 1), x(n + 1), y(n + 1), flag(n + 2);
    for (int i = 1; i <= n; i++) {
        char op;
        cin >> op >> x[i];
        if (op == 'x') {
            op1[i] = 1;
        } else {
            op1[i] = 0;
        }
        cin >> op >> y[i];
        if (op == 'x') {
            op2[i] = 1;
        } else {
            op2[i] = 0;
        }
    }
    int l = 1, r = 1;
    for (int i = n; i >= 2; i--) {
        if (op1[i] == 1) {
            if (op2[i] == 1) {
                if (x[i] == y[i]) {
                    flag[i] = flag[i + 1];
                } else if (x[i] > y[i]) {
                    flag[i] = 0;
                } else {
                    flag[i] = 1;
                }
            } else {
                flag[i] = 0;
            }
        } else if (op2[i] == 1) {
            flag[i] = 1;
        } else {
            flag[i] = flag[i + 1];
        }
    }
    for (int i = 1; i <= n; i++) {
        int sum = 0;
        if (op1[i] == 1) {
            sum += l * (x[i] - 1);
        } else {
            sum += x[i];
        }
        if (op2[i] == 1) {
            sum += r * (y[i] - 1);
        } else {
            sum += y[i];
        }
        if (flag[i + 1]) {
            r += sum;
        } else {
            l += sum;
        }
    }
    cout << l + r << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

E

题意

交互题。

题目中存在两个数 \(x,y\)，你可以提问两次，每次提问给定一个数 \(k\)，返回 $(xk) + (yk) $。提问结束后题目给定一个数 \(m\)，输出 \((m\mid x) + (m\mid y)\)。

题解

如此小的询问次数必然联系着极强的性质，或运算中我们对每一位单独考虑需要 \(\log n\) 次，这里的运算次数暗示我们一次询问能知道多位的情况。考虑取 \(k = (10)_2\)，那么进行或运算后相加，将返回的结果减去 \(2k\)，就是对每一位产生的影响（排除了本身就是 1 的位）：考虑低三位之和，第三位一定是 \(1\)，因为 \(x\mid k\) 和 \(y\mid k\) 第二位或运算后一定是 1，相加后进位。而低两位有 10、00、01 三种情况，分别对应着：两个数第一位都是 1、两个数第一位都是 0、有一个数第一位是 1 且另一个数第一位是 0。可见，这样我们可以知道一位的情况。

因此，我们询问一个类似 10101010 的数，可以知道奇数位的情况，再询问一个类似 1010101 的数，可以知道偶数位的情况，两次询问即可知道每一位的情况，再用 \(m\) 根据每一位的情况进行或运算即可。

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int x = 0, y = 0;
    vector<bool> a(30), b(30);
    for (int i = 0; i < 30; i++) {
        if (i % 2 == 1) {
            x |= (1 << i);
        } else {
            y |= (1 << i);
        }
    }
    cout << y << endl;
    int c;
    cin >> c;
    c -= 2 * y;
    for (int i = 1; i < 30; i += 2) {
        if ((c & (1 << i))) {
            a[i] = 1, b[i] = 0;
        } else {
            if ((c & (1 << (i + 1)))) {
                a[i] = b[i] = 1;
            }
        }
    }
    cout << x << endl;
    cin >> c;
    c -= 2 * x;
    for (int i = 0; i < 30; i += 2) {
        if ((c & (1 << i))) {
            a[i] = 1, b[i] = 0;
        } else {
            if ((c & (1 << (i + 1)))) {
                a[i] = b[i] = 1;
            }
        }
    }
    cout << "!" << endl;
    int m;
    cin >> m;
    int ans = 0;
    for (int i = 0; i < 30; i++) {
        if (((m >> i) & 1)) {
            ans += (1 << i) * 2;
        } else {
            if (a[i] == 0 && b[i] == 0) {
                continue;
            } else if (a[i] == 1 && b[i] == 1) {
                ans += (1 << i) * 2;
            } else {
                ans += (1 << i);
            }
        }
    }
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}