2025春训第五场 - Star's Blog

又是熟悉的博弈问题，又是熟悉的做不出来，不过剩下三道能做出来的都挺有意思的，相对比较满足。

A. 游戏#

答案= min(max(从小到大交替选，从大到小交替选)，max(A从最大的连续选，A从最小的连续选)).

提示：A 希望答案尽可能大，所以由 A 决策决定的应取 max，B 希望答案尽可能小，所以由 B 决策决定的应该取 min.
建议：给 @xx liu (qwertyuiop) 佬磕一个

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

4
using namespace std;
5

6
int a[100010];
7

8
int main() {
9
    int n;
10
    scanf("%d", &n);
11
    for (int i = 1; i <= n; ++i) {
12
        scanf("%d", &a[i]);
13
    }
14
    sort(a + 1, a + n + 1);
15
    long long A = 0, B = 0;
16
    long long res;
17
    for (int i = n; i > 0; i -= 2) A += a[i];
18
    for (int i = n - 1; i > 0; i -= 2) B += a[i];
19
    res = abs(A) - abs(B);
20
    A = 0, B = 0;
21
    for (int i = 1; i <= n; i += 2) A += a[i];
22
    for (int i = 2; i <= n; i += 2) B += a[i];
23
    res = max(res, abs(A) - abs(B));
24
    A = 0, B = 0;
25
    for (int i = 1; i <= n; ++i) {
26
        if (i <= (n + 1) / 2) A += a[i];
27
        else B += a[i];
28
    }
29
    long long t1 = abs(A) - abs(B);
30
    A = 0, B = 0;
31
    reverse(a + 1, a + n + 1);
32
    for (int i = 1; i <= n; ++i) {
33
        if (i <= (n + 1) / 2) A += a[i];
34
        else B += a[i];
35
    }
36
    res = min(max(t1, abs(A) - abs(B)), res);
37
    printf("%lld\n", res);
38
    return 0;
39
}

B. 音符#

单调队列优化的 dp 效率最高，或者线段树也行，两版代码都贴一下。

res = \max_{i = 1}^{n} \max_{j < i\ \land\ a_i - a_j <= k}\{i - j + 1 + \max_{k < j\ \land \ a_{j - 1} - a_k <= k}\{j - k\}\}

一个双指针维护内层 max，一个单调队列维护 $\max_{j < i\ \land\ a_i - a_j <= k}\{- j + 1 + \max_{k < j\ \land \ a_j - a_k <= k}\{j - k + 1\}\}$ ，就可以实现 O(n).

单调队列代码

1
#include <iostream>
2
#include <algorithm>
3
#include <map>
4

5
using namespace std;
6

7
const int N = 500010;
8
int a[N], q[N];
9
long long f[N];
10

11
int main() {
12
    int n, k;
13
    scanf("%d%d", &n, &k);
14
    for (int i = 1; i <= n; ++i) {
15
        scanf("%d", &a[i]);
16
    }
17
    long long res = 0;
18
    int pre_max = 0;
19
    sort(a + 1, a + n + 1);
20
    int hh = 0, tt = -1, t = 0;
21
    for (int i = 1, j = 1; i <= n; ++i) {
22
        while (hh <= tt && a[i] - a[q[hh]] > k) hh++;
23
        while (j <= i && a[i] - a[j] > k) j++;
24
        if (hh <= tt) res = max(res, i + f[q[hh]]);
25
        f[i] = -i + 1 + pre_max;
26
        pre_max = max(pre_max, i - j + 1);
27
        while (hh <= tt && f[i] >= f[q[tt]]) tt--;
28
        q[++tt] = i;
29
    }
30
    printf("%lld\n", res);
31
    return 0;
32
}

线段树暴戾代码（离散化疑似反向优化了）

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

5
using namespace std;
6

7
const int N = 500010;
8
map<int, int> mp;
9
int a[N], b[N];
10
long long tr[N * 4], f[N][2], s[N];
11

12
void pushup(int u) {
13
    tr[u] = max(tr[u << 1], tr[u << 1 | 1]);
14
}
15

16
void init(int u, int l, int r) {
17
    if (l == r) tr[u] = l == 0 ? 0 : -__LONG_LONG_MAX__;
18
    else {
19
        int mid = l + r >> 1;
20
        init(u << 1, l, mid), init(u << 1 | 1, mid + 1, r);
21
        pushup(u);
22
    }
23
}
24

25
void modify(int u, int l, int r, int p, int v) {
26
    if (l == r) tr[u] = v;
27
    else {
28
        int mid = l + r >> 1;
29
        if (p <= mid) modify(u << 1, l, mid, p, v);
30
        else modify(u << 1 | 1, mid + 1, r, p, v);
31
        pushup(u);
32
    }
33
}
34

35
long long query(int u, int l, int r, int ql, int qr) {
36
    if (ql <= l && r <= qr) return tr[u];
37
    else {
38
        long long res = -__LONG_LONG_MAX__;
39
        int mid = l + r >> 1;
40
        if (ql <= mid) res = max(res, query(u << 1, l, mid, ql ,qr));
41
        if (qr > mid) res = max(res, query(u << 1 | 1, mid + 1, r, ql, qr));
42
        return res;
43
    }
44
}
45

46
int main() {
47
    int n, k;
48
    scanf("%d%d", &n, &k);
49
    init(1, 0, n);
50
    for (int i = 1; i <= n; ++i) {
51
        scanf("%d", &a[i]);
52
        mp[a[i]];
53
    }
54
    int m = 0;
55
    for (auto &i : mp) {
56
        i.second = ++m;
57
        b[m] = i.first;
58
    }
59
    for (int i = 1; i <= n; ++i) {
60
        s[mp[a[i]]]++;
61
    }
62
    for (int i = 1; i <= m; ++i) s[i] += s[i - 1];
63
    long long res = 0;
64
    for (int i = 1; i <= m; ++i) {
65
        int l = 0, r = i - 1;
66
        while (l < r) {
67
            int mid = l + r + 1 >> 1;
68
            if (b[mid] < b[i] - k) l = mid;
69
            else r = mid - 1;
70
        }
71
        f[i][0] = max(f[i - 1][0], s[i] - s[l]);
72
        f[i][1] = s[i] + query(1, 0, n, l, i - 1);
73
        modify(1, 0, n, i, -s[i] + f[i][0]);
74
    }
75
    for (int i = 1; i <= m; ++i) {
76
        res = max(res, f[i][1]);
77
    }
78
    printf("%lld\n", res);
79
    return 0;
80
}

非常反直觉，其实我敲线段树比上面的单调队列快，单调队列比较考验思维，不像我们线段树和二分查找，直接背板子就行了。

C. 星星点灯#

过滤掉所有边权大于 m 的边，然后跑最小生成树，同时统计边权和，最后加上连通块个数 * m 就是答案。相对比较 easy.

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

4
using namespace std;
5

6
const int N = 1010;
7
struct edge {
8
    int x, y, z;
9
} ed[N * N];
10
int fa[N];
11

12
int getfa(int x) {
13
    return x == fa[x] ? x : fa[x] = getfa(fa[x]);
14
}
15

16
int main() {
17
    int val, n, m = 0;
18
    scanf("%d%d", &val, &n);
19
    for (int i = 1; i <= n; ++i) fa[i] = i;
20
    for (int i = 1; i <= n; ++i) {
21
        for (int j = 1; j <= n; ++j) {
22
            int t;
23
            scanf("%d", &t);
24
            if (i < j) ed[++m] = {i, j, t};
25
        }
26
    }
27
    sort(ed + 1, ed + m + 1, [](edge a, edge b) {
28
        return a.z < b.z;
29
    });
30
    long long res = 0;
31
    for (int i = 1; i <= m; ++i) {
32
        if (ed[i].z > val) break;
33
        int x = ed[i].x, y = ed[i].y;
34
        x = getfa(x), y = getfa(y);
35
        if (x == y) continue;
36
        else {
37
            fa[y] = x;
38
            res += ed[i].z;
39
        }
40
    }
41
    for (int i = 1; i <= n; ++i) if (i == fa[i]) res += val;
42
    printf("%lld\n", res);
43
    return 0;
44
}

D. 翘课#

类似于分组背包问题，先把每一天单独的旷 [0, k] 节课的后呆在教学楼的时间算出来，然后跑分组背包dp即可。（理论上可以在维护每天单独的时间的同时做分组背包dp，但是我不知道为什么一直写挂）

ps：说的很简单，但是内部逻辑其实有点绕。

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

5
using namespace std;
6

7
vector<int> a[510];
8
int f[510][510];
9
int g[510][510];
10

11
int main() {
12
    int n, m, k;
13
    scanf("%d%d%d", &n, &m, &k);
14
    for (int i = 1; i <= n; ++i) {
15
        for (int j = 1; j <= m; ++j) {
16
            int t;
17
            scanf("%d", &t);
18
            if (t) a[i].push_back(j);
19
        }
20
    }
21
    memset(f, 0x3f, sizeof(f));
22
    memset(g, 0x3f, sizeof(g));
23
    for (int i = 1; i <= n; ++i) {
24
        for (int j = 0; j < a[i].size(); ++j) { // 旷课 j 节
25
            int t = a[i].size() - j; // 上课 t 节
26
            for (int k = t - 1; k < a[i].size(); ++k) {
27
                f[i][j] = min(f[i][j], a[i][k] - a[i][k - t + 1] + 1);
28
            }
29
        }
30
        f[i][a[i].size()] = 0;
31
    }
32
    g[0][0] = 0;
33
    for (int i = 1; i <= n; ++i) {
34
        for (int j = 0; j <= k; ++j) {
35
            for (int l = 0; l <= j; ++l) {
36
                g[i][j] = min(g[i][j], g[i - 1][l] + f[i][j - l]);
37
            }
38
        }
39
    }
40
    int res = 0x3f3f3f3f;
41
    for (int i = 0; i <= k; ++i) {
42
        res = min(res, g[n][i]);
43
    }
44
    printf("%d\n", res);
45
    return 0;
46
}