近期来打得最好的一场，但是B题细节真有点多啊喂。。

A. To Zero

给定 n, k, 求把n变0次数

k >= n 答案是1， 否则n先减去k，之后无论如何选择的减数必然是偶数，然后计算次数即可

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;

using i64 = long long;

void solve() {
    i64 n, k;
    cin >> n >> k;

    i64 ans = 0;
    if (k >= n) {
        cout << 1 << '\n';
        return;
    }

    n -= k;
    ans++;

    if (k & 1) {
        k--;
    }
    
    ans += (n / k) + ((n % k) ? 1 : 0);
    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while(t--) {
        solve();
    }

    return 0;
}

B. Array Recoloring

题目大意
给定一个大小为 nn 的整数数组 aa 。最初，数组的所有元素都是红色的。

您必须精确地选择数组中的 kk 元素，并将它们涂成蓝色。然后，虽然至少有一个红色元素，但您必须选择任何有蓝色邻居的红色元素，并将其设置为蓝色。

绘制数组的代价定义为第一个 kk 选择的元素和最后一个绘制的元素的和。

您的任务是计算给定数组绘制的最大可能成本。

思路
首先考虑k == 1情况，此时无论如何最后一个数字总会是左右两端的数字，那么ans最大的情况就是

  • a[1] + a[n] 或者是 2 - n - 1中最大的值 + max(a[1], a[n])

然后看k >= 2情况，这时候你会发现无论你怎么选择元素，最后一个数字也都可以自己选择（去纸上手玩一下发现），所以最大值就是最大的k + 1个数字

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

using i64 = long long;

void solve() {
    int n, k;
    cin >> n >> k;

    vector<i64> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }    

    i64 ans = 0;
    if (k == 1) {
        ans = a[1] + a[n];
        i64 r = 0;
        for (int i = 2; i < n; i++) {
            r = max(r, a[i]);
        }
        r += max(a[1], a[n]);
        ans = max(ans, r);
    } else {
        sort(a.begin() + 1, a.end());
        k++;
        for (int i = n; i >= 1; i--) {
            if (k == 0) break;
            ans += a[i];
            k--;
        }
    }

    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while(t--) {
        solve();
    }

    return 0;
}

C. Two Colors

比B还简单的水，直接上代码

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

using i64 = long long;

void solve() {
    int n, m;
    cin >> n >> m;

    vector<i64> a(n + 1);
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        if (x <= n) a[x]++;
    }

    vector<i64> P(n + 1);
    vector<i64> Q(n + 1);
    for (int i = 1; i < n; i++) {
        P[i] = P[i - 1] + a[i];
        Q[i] = Q[i - 1] + i * a[i];
    }

    i64 s = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] == 0) continue;

        int L = max(n - i, 1);
        i64 cnt = 0;
        if (L <= n - 1) {
            i64 p = P[n - 1] - (L >= 1 ? P[L - 1] : 0);
            i64 q = Q[n - 1] - (L >= 1 ? Q[L - 1] : 0);
            cnt += (i - n + 1) * p + q;
        }
        cnt += 1LL * a[n] * i;
        s += 1LL * a[i] * cnt;
    }

    if (a[n] > 0) {
        i64 cnt = Q[n-1] + a[n] * (n - 1);
        s += a[n] * cnt;
    }

    i64 ans = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] && 2 * i >= n) {
            ans += 1LL * a[i] * (2 * i - n + 1);
        }
    }
    ans += 1LL * a[n] * (n - 1);

    cout << (s - ans) << '\n';
}   

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while(t--) {
        solve();
    }

    return 0;
}

D. Equalization

题目大意
给定两个正整数 x 和 y 。

您可以执行以下操作任意次数(可能为零)：选择一个正整数 k ，然后将 x 或 y 除以 $2^k$ 。这个操作的代价是 $2^k$ 。但是，有一个额外的约束：您不能多次选择相同的 kk 值。

你的任务是计算使 x 等于 y 的最小可能代价。

思路

注意到某个数字除以 $2^k$ 相当于右移k位，而给定的数据1e17 最多需要61次会变成0，所以可以从暴力枚举每一位入手，如果循环到某一位时候相同，就计算最小值

现在考虑怎么计算循环所需要的费用：可以预先处理一个dp数组

  • dp[i][j] 表示：将 x 右移 i 位、y 右移 j 位所需的最小代价。初始状态为 (0,0)(0,0)(0,0)，代价为 0。

  • 状态转移
    对于每个操作步长 k 从 1 到 61：

    • 你可以选择对 x 或 y 进行操作。
    • 如果对 x 操作：状态从 (i, j)(i, j)(i, j) 转移到 (i+k, j)(i+k, j)(i+k, j)，并增加的代价为 $2^k$。

    • 如果对 y 操作：状态从 (i, j)(i, j)(i, j) 转移到 (i, j+k)(i, j+k)(i, j+k)，同样增加代价为 $2^k$。

      这里使用了复制 dp 到 ndp 的方式，以保证每次操作 k 只使用一次。

  • 存储所有状态
    遍历 dp 数组，将所有可达状态（即 dp[i][j] != inf）存入 mem 向量：

    这样，我们得到了所有可能的右移位数组合及其对应的总代价。

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

using i64 = long long;
struct node {
    int x, y;
    i64 c;
};
const i64 inf = std::numeric_limits<i64>::max();

vector dp(62, vector<i64> (62, inf));
vector<node> mem;

void pre() {
    dp[0][0] = 0;

    for (int k = 1; k <= 61; k++) {
        vector ndp = dp;
        for (int i = 0; i <= 61; i++) {
            for (int j = 0; j <= 61; j++) {
                if (dp[i][j] != inf) {
                    if (i + k <= 61) {
                        ndp[i + k][j] = min(ndp[i + k][j], dp[i][j] + (1LL << k));
                    }
                    if (j + k <= 61) {
                        ndp[i][j + k] = min(ndp[i][j + k], dp[i][j] + (1LL << k));
                    }
                }
            }
        }
        dp = ndp;
    }

    for (int i = 0; i <= 61; i++) {
        for (int j = 0; j <= 61; j++) {
            if (dp[i][j] != inf) {
                mem.emplace_back(i, j, dp[i][j]);
            }
        }
    }
}

void solve() {
    i64 x, y;
    cin >> x >> y;

    i64 ans = inf;
    vector<node> a;

    for (auto tp : mem) {
        auto [l, r, c] = tp;
        if ((x >> l) == (y >> r)) {
            ans = min(ans, c);
        }
    }

    cout << ans << '\n';


}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    pre();
    
    while(t--) {
        solve();
    }

    return 0;
}