2025牛客暑期多校训练营5

大概情况是这样的

STATUS	COUNT
AC	3
赛后补	4

做了 3 个补了四个，显然是赛场上出了点问题，做完最简单的三个之后我们被榜误导了，H 题很简单但是我们没看，先看了比较难的 K 题，K 题思路出来之后最终 40min 没有战胜，然后三道题遗憾离场了，排名是 373.

A. Entangled Coins ^补#

这道题属实感觉有点不应该，我中间推对了很多结论，但是后面不知道怎么又给自己推翻了。

我思维卡在的点是

操作奇数次和偶数次得到的式子不一样，没有想到把奇数拆成一个 1 和一个偶数分析；
只操作偶数次的结论其实已经大致得出了，但是边界没有处理好，晕进去了，没有想到 n < 2k 会卡边界的情况下用互相抵消的思想把 k 转化成 n - k 优化掉恶心的边界情况。

应该继续往下想的，我看完题第一句就说这题的结论应该不复杂……实际上也真不复杂，但是赛场上还是没想到

1
#include <iostream>
2

3
using namespace std;
4

5
int main() {
6
    int T;
7
    scanf("%d", &T);
8
    while (T--) {
9
        long long n, k, s, t;
10
        scanf("%lld%lld%lld%lld", &n, &k, &s, &t);
11
        if (s == t) printf("0\n");
12
        else if (n == k) {
13
            if (s + t == n) printf("1\n");
14
            else printf("-1\n");
15
        }
16
        else if ((t - s & 1) && (k % 2 == 0)) printf("-1\n");
17
        else if (t - s & 1) {
18
            int l = abs(s - k), r = min(s + k, 2 * n - s - k);
19
            if (l <= t && t <= r) {
20
                printf("1\n");
21
                continue;
22
            }
23
            int d = min(abs(l - t), abs(r - t));
24
            k = min(k, n - k);
25
            printf("%lld\n", 1 + 2 * ((d + k * 2 - 1) / (k * 2)));
26
        }
27
        else if (k & 1) {
28
            int d = abs(s - t);
29
            k = min(k, n - k);
30
            printf("%lld\n", 2 * ((d + k * 2 - 1) / (k * 2)));
31
        }
32
        else {
33
            int l = abs(s - k), r = min(s + k, 2 * n - s - k);
34
            if (l <= t && t <= r) {
35
                printf("1\n");
36
                continue;
37
            }
38
            int d1 = min(abs(l - t), abs(r - t)), d2 = abs(s - t);
39
            k = min(k, n - k);
40
            printf("%lld\n", min(1 + 2 * ((d1 + k * 2 - 1) / (k * 2)), 2 * ((d2 + k * 2 - 1) / (k * 2))));
41
        }
42
    }
43
    return 0;
44
}

C. Array Deletion Game ^补#

我是对博弈论先天性抗拒，但是这道题的性质还真不难，问题也是我们没有人看这道题。逆向思维很容易想到，比较难注意到的性质是，因为左右各差 1 个位置，l + r 相同的要么全必胜要么全必负，二分卡到中间最小的那个合法区间，现在左右端点有一个就不能动了，把移动左端点和移动右端点的情况分别讨论一下取并。这个转化也很巧妙。

1
#include <iostream>
2

3
using namespace std;
4
const int N = 100010;
5

6
int a[N];
7

8
int main() {
9
    int n, q;
10
    scanf("%d", &n);
11
    for (int i = 1; i <= n; ++i) {
12
        scanf("%d", &a[i]);
13
        a[i] += a[i - 1];
14
    }
15
    scanf("%d", &q);
16
    while (q--) {
17
        int s;
18
        scanf("%d", &s);
19
        int l = 0, r = n / 2;
20
        while (l < r) {
21
            int mid = l + r + 1 >> 1;
22
            if (a[n - mid] - a[mid] > s) l = mid;
23
            else r = mid - 1;
24
        }
25
        int d = l;
26
//         cout << d << ' ';
27
        l = 1 + d, r = n - d + 1;
28
        while (l < r) {
29
            int mid = l + r >> 1;
30
            if (a[n - d] - a[mid - 1] <= s) r = mid;
31
            else l = mid + 1;
32
        }
33
//         cout << l << ' ' ;
34
        if (l - d & 1) {
35
//             cout << endl;
36
            printf("Alice\n");
37
            continue;
38
        }
39
        l = d, r = n - d;
40
        while (l < r) {
41
            int mid = l + r + 1 >> 1;
42
            if (a[mid] - a[d] <= s) l = mid;
43
            else r = mid - 1;
44
        }
45
//         cout << l << endl;
46
        if (n - d - l + 1 & 1) {
47
            printf("Alice\n");
48
        }
49
        else printf("Bob\n");
50
    }
51
    return 0;
52
}

E. Mysterious XOR Operation#

这道题是我想的 + 我做的，想到的有点慢了，如果没有限制条件，传统的做法就是对每个二进制位分别前缀和，对于每个数枚举数位和前缀和比较，统计答案。加上第奇数个 1 的限制之后统计就稍微复杂了，本来我想着要 dp，但是是不合理的，如果做了线性 dp 相当于把所有数位拆开排列组合了一遍，显然不对；应该做的是统计。后来灵机一动想到无论如何两个后缀 1 个数都是偶数的数的后缀异或之后 1 的个数一定还是偶数，因为只能两个 1 相消偶数 + 偶数 - 偶数还是偶数，于是就解决了。

1
#include <iostream>
2
#include <cstring>
3

4
using namespace std;
5

6
int cnt[40][2][2];
7

8
int main() {
9
    int n;
10
    scanf("%d", &n);
11
    long long res = 0;
12
    for (int i = 0; i < n; ++i) {
13
        int t;
14
        scanf("%d", &t);
15
        for (int j = 0, k = 0; j < 32; ++j) {
16
            int c = t >> j & 1;
17
            res += (long long)cnt[j][c ^ 1][k] << j;
18
            k ^= t >> j & 1;
19
        }
20
        for (int j = 0, k = 0; j < 32; ++j) {
21
            cnt[j][t >> j & 1][k]++;
22
            k ^= t >> j & 1;
23
        }
24
    }
25
    printf("%lld\n", res);
26
    return 0;
27
}

H. VI Civilization ^补#

这道是最可惜的一道，似乎可能是题干比较长[?]没人做，实际上很简单，我们都被骗了，一眼都没看，其实就是一个简单的二分和一个简单的 dp。

虽然但是，如果我看到了去敲代码了可能会弄出来一大堆 Floating Point Exception. 后面补题的时候没特判 mid == 0 的情况出了好几次问题。

1
#include <iostream>
2
#include <cstring>
3

4
using namespace std;
5

6
const int N = 110;
7
int a[N], k[N], b[N], c[N]; // 需要的科技点 科技点增量 尤里卡需要的生产力 尤里卡减少的科技点
8
int f[N][N][N]; // 前 i 轮使用了 j 次生产力完成了 k 个科技
9
int m, s, t, n; // 科技点 胜利需要的科技点 回合限制 总个数
10

11
bool check(int mid) {
12
    int res = 0;
13
    for (int i = 1; i <= t; ++i) {
14
        for (int j = 0; j <= i; ++j) {
15
            for (int l = 0; l <= n; ++l) {
16
                f[i][j][l] = -0x3f3f3f3f;
17
                f[i][j][l] = max(f[i][j][l], f[i - 1][j][l] + m + k[l]);
18
                if (i - (a[l] + m + k[l - 1] - 1) / (m + k[l - 1]) >= 0)
19
                    f[i][j][l] = max(f[i][j][l], f[i - (a[l] + m + k[l - 1] - 1) / (m + k[l - 1])][j][l - 1]);
20
                if (mid != 0 && i - (a[l] - c[l] + m + k[l - 1] - 1) / (m + k[l - 1]) >= 0 && j - (b[l] + mid - 1) / mid >= 0)
21
                    f[i][j][l] = max(f[i][j][l], f[i - (a[l] - c[l] + m + k[l - 1] - 1) / (m + k[l - 1])][j - (b[l] + mid - 1) / mid][l - 1]);
22
                if (f[i][j][l] >= s) return true;
23
            }
24
        }
25
    }
26
    return false;
27
}
28

29
int main() {
30
    scanf("%d%d%d%d", &m, &s, &t, &n);
31
    for (int i = 1; i <= n; ++i) {
32
        scanf("%d%d%d%d", &a[i], &k[i], &b[i], &c[i]);
33
        k[i] += k[i - 1];
34
    }
35
    memset(f, -0x3f, sizeof(f));
36
    f[0][0][0] = 0;
37
    int l = 0, r = 1000000001;
38
    while (l < r) {
39
        int mid = l + r >> 1;
40
        if (check(mid)) r = mid;
41
        else l = mid + 1;
42
    }
43
    printf("%d\n", l == 1000000001 ? -1 : l);
44
    return 0;
45
}

I. Block Combination Minimal Perimeter#

超级大水题。

1
#include <iostream>
2

3
using namespace std;
4

5
int main() {
6
  int n;
7
  cin >> n;
8
  if (n & 1) cout << 2 * ((n + 1) / 2 + n) << endl;
9
  else cout << 2*((n / 2) + n + 1) << endl;
10
  return 0;
11
}

J. Fastest Coverage Problem ^队友#

这也是一道简单题，逻辑上来说二分答案就可以，实际上当时写代码的时候并不顺利，WA 了两次才过。

后面我补题的时候也 WA 了好几次，而且 97.6%.

没有处理一个 1 都没有的清况；
处于最角上四个不合法块夹出来的矩形的中心正好对着格的间隙……这个情况我感觉不太好处理，于是干脆多遍历了一遍，枚举中心点，验证四个角，常数 * 2，变相解决了这个边界问题。

1
#include <iostream>
2
#include <queue>
3
#include <vector>
4
#include <climits>
5

6
using namespace std;
7

8
vector<vector<int>> mp, f;
9
int n, m;
10

11
bool check(int mid) {
12
    int mnxpy = INT_MAX, mnxmy = INT_MAX, mxxpy = INT_MIN, mxxmy = INT_MIN;
13
    for (int i = 0; i < n; ++i) {
14
        for (int j = 0; j < m; ++j) {
15
            // cout << f[i][j] << ' ';
16
            if (f[i][j] > mid) {
17
                mnxpy = min(mnxpy, i + j);
18
                mnxmy = min(mnxmy, i - j);
19
                mxxpy = max(mxxpy, i + j);
20
                mxxmy = max(mxxmy, i - j);
21
            }
22
        }
23
        // cout << endl;
24
    }
25
    if (mxxpy == INT_MIN) return true;
26
    else {
27
        // cout << mxxpy << ' ' << mnxpy << ' ' << mxxmy << ' ' << mnxmy << endl;
28
        for (int i = 0; i < n; ++i) {
29
            for (int j = 0; j < m; ++j) {
30
                if (max(max(mxxpy - i - j, i + j - mnxpy), max(mxxmy - i + j, i - j - mnxmy)) <= mid) {
31
                    // cout << i << ' ' << j << ' ' << max(max(mxxpy - i - j, i + j - mnxpy), max(mxxmy - i + j, i - j - mxxmy)) << endl;
32
                    return true;
33
                }
34
            }
35
        }
36
        return false;
37
    }
38
}
39

40
int main() {
41
    scanf("%d%d", &n, &m);
42
    mp = vector<vector<int>>(n, vector<int>(m));
43
    f = vector<vector<int>>(n, vector<int>(m, n * m));
44
    queue<pair<int, int>> q;
45
    for (int i = 0; i < n; ++i) {
46
        for (int j = 0; j < m; ++j) {
47
            scanf("%d", &mp[i][j]);
48
            if (mp[i][j]) {
49
                f[i][j] = 0;
50
                q.push({i, j});
51
            }
52
        }
53
    }
54
    int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
55
    while (!q.empty()) {
56
        auto s = q.front();
57
        q.pop();
58
        for (int i = 0; i < 4; ++i) {
59
            auto t = s;
60
            t.first += dx[i], t.second += dy[i];
61
            if (t.first >= 0 && t.first < n && t.second >= 0 && t.second < m && f[t.first][t.second] == n * m) {
62
                f[t.first][t.second] = f[s.first][s.second] + 1;
63
                q.push(t);
64
            }
65
        }
66
    }
67
    int l = 0, r = n * m;
68
    while (l < r) {
69
        int mid = l + r >> 1;
70
        if (check(mid)) r = mid;
71
        else l = mid + 1;
72
    }
73
    printf("%d\n", l);
74
    return 0;
75
}

K. Perfect Journey ^补#

佬们放着简单的 H 不做，都来 K 题当卡常高手了……

树上路径只要两个端点确定了那就是一定的，只考虑关键边下到的节点构成的虚树的话顶多只有 m² 种路径，只能有 m² 种合法的 bitmask，然后做状压 dp，如果常数优秀的话可以恰好过了。

离谱的问题:

最后的状压 dp 里有这么一行代码

1
way[j | mask[i]] = ((long long)way[j | mask[i]] + (long long)way[j] * cnt[i] % MOD) % MOD;

最快的情况，第一个 long long 不加，同时后面的乘法取模
慢 600 ms 的情况，第一个 long long 加上，同时后面的乘法取模
慢 400 ms 的情况，第一个 long long 不加，同时后面不取模

那个佬可以解释一下为什么😭

1
#include <iostream>
2
#include <cstring>
3
#include <bitset>
4

5
using namespace std;
6

7
const int N = 200010;
8
const int MOD = 998244353;
9
int head[N], ver[N * 2], ne[N * 2], tot = 1;
10
int f[N], fa[N];
11
bool flag[N];
12
int id[N];
13
int mask[N], cnt[N];
14
int g[1 << 22], way[1 << 22];
15

16
void add(int x, int y) {
17
    ver[++tot] = y;
18
    ne[tot] = head[x];
19
    head[x] = tot;
20
}
21

22
void dfs(int x) {
23
    for (int i = head[x]; i; i = ne[i]) {
24
        int y = ver[i];
25
        if (y == fa[x]) continue;
26
        fa[y] = x;
27
        dfs(y);
28
    }
29
}
30

31
void dfs2(int x) {
32
    if (flag[x]) f[x] |= 1 << id[x];
33
    for (int i = head[x]; i; i = ne[i]) {
34
        int y = ver[i];
35
        if (y == fa[x]) continue;
36
        f[y] |= f[x];
37
        dfs2(y);
38
    }
39
}
40

41
int main() {
42
    int n, m, k;
43
    scanf("%d%d%d", &n, &m, &k);
44
    for (int i = 1; i < n; ++i) {
45
        int x, y;
46
        scanf("%d%d", &x, &y);
47
        add(x, y), add(y, x);
48
    }
49
    dfs(1);
50
    for (int i = 0; i < m; ++i) {
51
        int t;
52
        scanf("%d", &t);
53
        int x = ver[t * 2], y = ver[t * 2 ^ 1];
54
        if (fa[y] == x) swap(x, y);
55
        flag[x] = true;
56
        id[x] = i;
57
    }
58
    dfs2(1);
59
    int siz = 0;
60
    while (k--) {
61
        int x, y;
62
        scanf("%d%d", &x, &y);
63
        int cur_mask = f[x] ^ f[y];
64
        bool found = false;
65
        for (int i = 0; i < siz; ++i) {
66
            if (cur_mask == mask[i]) {
67
                found = true;
68
                cnt[i]++;
69
                break;
70
            }
71
        }
72
        if (!found) {
73
            mask[siz] = cur_mask, cnt[siz] = 1;
74
            siz++;
75
        }
76
    }
77
    memset(g, 0x3f, sizeof(g));
78
    g[0] = 0, way[0] = 1;
79
    for (int i = 0; i < siz; ++i) {
80
        for (int j = 0; j < (1 << m); ++j) {
81
            if (g[j | mask[i]] > g[j] + 1) {
82
                g[j | mask[i]] = g[j] + 1;
83
                way[j | mask[i]] = (long long)way[j] * cnt[i] % MOD;
84
            }
85
            else if (g[j | mask[i]] == g[j] + 1) {
86
                way[j | mask[i]] = (way[j | mask[i]] + (long long)way[j] * cnt[i] % MOD) % MOD;
87
            }
88
        }
89
    }
90
    if (way[(1 << m) - 1]) printf("%d %d\n", g[(1 << m) - 1], way[(1 << m) - 1]);
91
    else printf("-1\n");
92
    return 0;
93
}

Star's Blog

A. Entangled Coins 补#

C. Array Deletion Game 补#