A - Shift Sort

令有 cc 个 00，则最小操作次数为 s[1,c]s[1, c] 中 11 的数量。

考虑 s[c+1,n]s[c+1, n] 中 00 的数量，这个数与 s[1,c]s[1,c] 中 11 的数量相同，设为 MM. 我们总是可以选取一个 misplaced 11、一个 misplaced 00 和另外一个 correctly placed digit 进行操作。

同时，如果三个选择的数都是 misplaced，这个其实是没用的。

AC Code
 
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
#include <bits/stdc++.h>
using vi = std::vector<int>;

char s[105];

void Run() {
    int n, c = 0;
    std::cin >> n;
    for (int i = 1; i <= n; i++) std::cin >> s[i], c += s[i] == '0';

    vi v;
    for (int i = 1; i <= c; i++)
        if (s[i] == '1') v.push_back(i);

    std::cout << v.size() << "\n";
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0), std::cerr.tie(0);

    int t = 1;
    std::cin >> t;
    while (t--) Run();
}

B - Another Divisibility Problem

添加一个 y=2xy=2x 即可，这样 xyˉ=x×100…002\bar{xy}=x\times 100\dots 002，而 x+y=3xx+y=3x，显然 100…002=0(mod3)100\dots 002=0\pmod 3.

C - Ultimate Value

考虑 Bob 会怎么操作，由于 alice 必定会让 f(a)f(a) 变最大，于是 Bob 最优的操作最多就是撤销 alice 的操作（而且还会增加 cost\tt{cost}），故 Bob 的最优解是直接结束。

所以游戏就变成了 alice 能否在一步操作内让 f(a)f(a) 最大化，或者直接结束。令 S=∑i=1n(−1)i−1aiS=\sum_{i=1}^n (-1)^{i-1}a_i。

  • 若 alice 直接结束，则 f(a)=Sf(a)=S；

  • 若 alice 交换奇偶相同的下标，那么 SS 不变，cost\tt{cost} 最多增加 n−1n-1（nn 为奇数）或 n−2n-2（nn 为偶数）

  • 若 alice 交换奇偶不同的下标，那么假设交换 i,ji,j，且 ii 为奇数、jj 为偶数，则

    f(a)←f(a)+2(aj−ai)+∣i−j∣f(a)\gets f(a)+2(a_j-a_i)+|i-j|

    所以，我们按 i<ji\lt j 和 i>ji\gt j 分成两个部分

    • 若 i<ji\lt j，我们 maximize 的目标为 2aj+j−(2ai+i)2a_j+j-(2a_i+i)
    • 若 i>ji\gt j，我们 maximize 的目标为 2aj−j−(2ai−i)2a_j-j-(2a_i-i)

两次线性枚举分别维护前缀 min 和后缀 min 即可。时间复杂度 O(n)O(n)

AC Code
 
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
#include <bits/stdc++.h>
#define mid(l, r) (l + ((r - l) >> 1))
#define sz(x) (int(x.size()))
#define repeat(i, a, b) for (int i = (a); i <= (b); i++)
#define until(i, a, b) for (int i = (a); i >= (b); i--)
#define array_of(T) std::unique_ptr<T[]>
using ll = long long;
using vi = std::vector<int>;
using pii = std::pair<int, int>;

constexpr int N = 2e5 + 10;

int n;
ll sum;
ll a[N];
ll s1[N];

void Run() {
    std::cin >> n;
    sum = 0;
    repeat(i, 1, n) {
        std::cin >> a[i];
        sum += a[i] * (i % 2 == 1 ? 1 : -1);
    }

    ll p = n % 2 == 0 ? n - 2 : n - 1;

    repeat(i, 1, n) s1[i] = a[i] * 2 + i;
    ll pmin = 1e18;
    ll m = 0;
    repeat(i, 1, n) {
        if (i % 2 == 1) pmin = std::min(pmin, s1[i]);
        else m = std::max(m, s1[i] - pmin);
    }

    repeat(i, 1, n) s1[i] = a[i] * 2 - i;
    ll smin = 1e18;
    until(i, n, 1) {
        if (i % 2 == 1) smin = std::min(smin, s1[i]);
        else m = std::max(m, s1[i] - smin);
    }

    std::cout << sum + std::max({0ll, m, p}) << "\n";
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0), std::cerr.tie(0);

    int t = 1;
    std::cin >> t;
    while (t--) Run();
}

D - A Cruel Segment’s Thesis

赛时没想到 max⁡\max 的转化导致没做出来

首先我们肯定选上所有线段，令 S=∑i=1nri−liS=\sum_{i=1}^n r_i-l_i。然后，我们想要选出 ⌊n2⌋\lfloor \frac{n}{2}\rfloor 对线段对 (a,b)(a,b) 使得

maximize ∑(a,b)max⁡{ rb−la,ra−lb } \text{maximize }\sum_{(a,b)} \max\set{r_b-l_a,r_a-l_b}

考虑后面的 max⁡\max，我们对他应用一个转化 max⁡{ a,b }=a+b+∣a−b∣2\max\set{a,b}=\frac{a+b+|a-b|}{2}，所以有

∑(a,b)rb−la+ra−lb+∣(rb−la)−(ra−lb)∣2  ⟹  ∑(a,b)(rb−lb)+(ra−la)+∣(rb+lb)−(ra+la)∣2 \sum_{(a,b)} \frac{r_b-l_a+r_a-l_b+|(r_b-l_a)-(r_a-l_b)|}{2} \\ \implies \sum_{(a,b)} \frac{(r_b-l_b)+(r_a-l_a)+|(r_b+l_b)-(r_a+l_a)|}{2}

当 nn 为偶数时，所有线段都会用得上，我们把线段按 l+rl+r 排序就可以求出绝对值里的东西之和了。

当 nn 为奇数的时候稍微麻烦一些，我们需要枚举是哪一条线段失配，并且还要根据这个判断第 (n+1)/2(n+1)/2 条线段应该被算在较小的 n/2n/2 条线段里，还是较大的 n/2n/2 条线段里。

总时间复杂度 O(nlog⁡n)O(n\log n).

AC Code
 
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>
#define mid(l, r) (l + ((r - l) >> 1))
#define sz(x) (int(x.size()))
#define repeat(i, a, b) for (int i = (a); i <= (b); i++)
#define until(i, a, b) for (int i = (a); i >= (b); i--)
#define array_of(T) std::unique_ptr<T[]>
#define all(x) x.begin(), x.end()
#define range(x, a, b) x + a, x + b + 1
using ll = long long;
using vi = std::vector<int>;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

constexpr int N = 2e5 + 10;

int n;
pll a[N];

void Run() {
    std::cin >> n;
    ll ans = 0;
    repeat(i, 1, n) std::cin >> a[i].first >> a[i].second, ans += a[i].second - a[i].first;

    std::sort(range(a, 1, n), [](pll &x, pll &y) { return x.first + x.second < y.first + y.second; });

    if (n % 2 == 0) {
        for (int i = 1, j = n; i < j; i++, j--) {
            auto [l1, r1] = a[i];
            auto [l2, r2] = a[j];
            ans += (r1 - l1 + r2 - l2 + r2 + l2 - r1 - l1) / 2;
        }
    } else {
        ll tp = 0, add = 0, sub = 0;
        int t = (n + 1) / 2;
        repeat(i, 1, n) {
            tp += a[i].second - a[i].first;
            if (i < t) sub += a[i].first + a[i].second;
            else if (i > t) add += a[i].first + a[i].second;
        }
        ll tans = 0;
        repeat(i, 1, n) {
            tp -= a[i].second - a[i].first;
            ll v = a[i].first + a[i].second;
            if (i < t) sub += a[t].first + a[t].second - v;
            else if (i > t) add += a[t].first + a[t].second - v;

            tans = std::max(tans, tp + add - sub);

            tp += a[i].second - a[i].first;
            if (i < t) sub -= a[t].first + a[t].second - v;
            else if (i > t) add -= a[t].first + a[t].second - v;
        }

        ans += tans / 2;
    }

    std::cout << ans << "\n";
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0), std::cerr.tie(0);

    int t = 1;
    std::cin >> t;
    while (t--) Run();
}

E1 - Prime Gaming (Easy Version)

看到 n≤20n\le 20 可以思考会不会是 bitmask 暴力 dp。我们令 bitmask 中 bi=0b_i=0 表示第 ii 堆石子数量为 11，bi=1b_i=1 表示第 ii 堆石子数量为 22。

然后我们发现一个状态是可以复用的。考虑令 dp[rem][mask][A/B]=1\texttt{dp[rem][mask][A/B]}=1 表示：剩余 rem\tt rem 个石子堆，并且这 rem\tt rem 个石子堆的 1,21,2 分布由 mask\tt{mask} 表示，当前为 A/B\tt A/B 行动，dp=1\texttt {dp}=1 表示最后 alice 可以取到数量为 22 的石子堆。

这里的“可以复用”是说，比如说某个状态 mask=100111011\text{mask}=100111011，它可以是从 mask′=100‾0111011\text{mask}'=10\underbar{0}0111011 移除下划线 00 得到，也可以从 mask′=100111‾1011\text{mask}'=10011\underbar{1}1011 中移除 11 得到，而后续的变化是相同的，可以复用。

所以，如果当前是 Alice 行动，让 Alice 在 mask\tt mask 石子堆里移除某一位然后交给 Bob 行动。只要存在某一个后继状态其 dp 值为 11，就说明 alice 可以移除某一位到达这个后继状态，从而使得自己可以走到 11。

如果当前是 Bob 行动，让 Bob 在 mask\tt mask 移除某一位。只要存在某一个后继状态的 dp 值为 00，就说明 Bob 可以通过操作阻止 Alice 最后走到 11.

我们最多会走过 O(2n)O(2^n) 个 mask\tt mask，每个 mask\tt mask 里，我们需要 O(n)O(n) 枚举移除的位置。所以我们可以直接写一个记忆化搜索，时间复杂度 O(n⋅2n)O(n\cdot 2^n)

AC Code
 
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
76
77
78
#include <bits/stdc++.h>
#define mid(l, r) (l + ((r - l) >> 1))
#define sz(x) (int(x.size()))
#define repeat(i, a, b) for (int i = (a); i <= (b); i++)
#define until(i, a, b) for (int i = (a); i >= (b); i--)
#define array_of(T) std::unique_ptr<T[]>
#define all(x) x.begin(), x.end()
#define range(x, a, b) x + a, x + b + 1
using ll = long long;
using vi = std::vector<int>;
using pii = std::pair<int, int>;

constexpr int T = 20;
constexpr int N = (1 << 20) + 5;

int n, m, k;
int g[30];
int dp[T + 5][N][2];

void Run() {
    std::cin >> n >> m >> k;
    repeat(i, 1, k) std::cin >> g[i];

    if (m == 1) {
        std::cout << 1 << "\n";
        return;
    }

    for (int i = 1; i <= n; i++)
        for (int j = 0; j < (1 << i); j++) dp[i][j][0] = dp[i][j][1] = -1;

    auto remove = [&](int mask, int p) {
        int low = mask & ((1 << p) - 1);
        int high = (mask >> (p + 1)) << p;
        return high | low;
    };

    auto dfs = [&](auto F, int remain, int config, int turn) -> int {
        auto &val = dp[remain][config][turn];

        if (val != -1) return val;
        if (remain == 1) return val = config;

        if (turn == 0) {
            repeat(i, 1, k) {
                if (g[i] <= remain) {
                    // remove g[i]-1 th bit
                    int next = remove(config, g[i] - 1);
                    if (F(F, remain - 1, next, 1) == 1) return val = 1;
                }
            }
            return val = 0;
        } else {
            repeat(i, 1, k) {
                if (g[i] <= remain) {
                    int next = remove(config, g[i] - 1);
                    if (F(F, remain - 1, next, 0) == 0) return val = 0;
                }
            }
            return val = 1;
        }
    };

    for (int mask = 0; mask < (1 << n); mask++) dfs(dfs, n, mask, 0);
    int ans = 0;
    for (int mask = 0; mask < (1 << n); mask++) ans += 1 + dp[n][mask][0];

    std::cout << ans << "\n";
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0), std::cerr.tie(0);

    int t = 1;
    std::cin >> t;
    while (t--) Run();
}

E2 - Prime Gaming (Hard Version)

我们尝试把 0,10,1 的意义拓展到 m>2m\gt 2 的范围，如果令

  • 1:ai≥k1:a_i\ge k
  • 0:ai<k0:a_i\lt k

根据 E1，我们钦定初始 0101 分布的 mask 的时候，可以计算出最后剩下的石子堆是否是 0/10/1，记为 f:mask={ 0,1 }n↦{ 0,1 }f:\text{mask}=\set{0,1}^n\mapsto \set{0,1}.

所以，假设最后剩下的石子堆数量为 aa，那么它会被一些 mask 统计为 11，这样的 mask 满足 f(mask)=1f(\text{mask})=1，也就是说，它会被 ≥1,≥2,≥3,…,≥a\ge 1, \ge 2, \ge 3,\dots,\ge a 统计总共 aa 次。

但是 mask\text{mask} 只是 { 0,1 }\set{0,1} 分布的，怎么才能计算出 mask\text{mask} 对应的序列数量呢？假设 popcount(mask)=r\text{popcount}(\text{mask})=r，说明 mask 中有 rr 个 11、n−rn-r 个 00，所以

Codeforces
License

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。