CSP 2022 Senior 题解和心得

假期计划 holiday

link

难度：蓝

一道很容易挂分的细节超多的图论题。

题意

  • 有一张无向图，称若点 AA 和点 BB 满足 dis(A,B)≤k+1dis(A, B) \le k + 1 ，则 AA 和 BB 相连。

  • 要求选定 4 个不同的，且不为 点1 的点，设为 AA, BB, CC, DD，满足 点1 和 AA、AA 和 BB、BB 和 CC、CC 和 DD、DD 和 点1 相连，求最大点权和。

  • 点数 n≤2500n \le 2500 ，边数 m≤104m \le 10^4 ，最大距离 k≤100k \le 100

题解

考虑先枚举两个点，再求出点权最大的满足条件的另两个点。

如果先求 AA 和 DD，则难以保证 BB 和 CC 相连。
而求 AA 和 CC，BB 和 DD 同理。

故先枚举 BB 和 CC。

具体实现：

  1. O(n2)\Omicron(n^2) 对于每个点预处理所有相连的点。
  2. O(n2)\Omicron(n^2) 对于每个点预处理出和它与 点1 相连且权值最大的 4 个点。（理论上 3 个已经足够，但似乎有办法卡掉)
  3. O(n2)\Omicron(n^2) 枚举 BB 和 CC，要 BB 和 CC 相连，分别从各自最大的 4 个点中枚举 AA 和 DD，注意保证各不相同。

代码

提交记录

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
/*
author: byronwan
problem:
    url: https://www.luogu.com.cn/problem/P8817
    title: [CSP-S 2022] 假期计划
date: 2022-11-10
*/

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int MAXN = 2.5e3 + 10, MAXM = 1e4 + 10;

int n, m, k;
int res = 0;
int value[MAXN];
vector<int> edges[MAXN];

bool can_arrive[MAXN][MAXN];

int dis[MAXN];
bool vis[MAXN];
void bfs(int s)
{
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    queue<int> q;
    q.push(s);
    dis[s] = 0;
    while (q.size()) {
        int u = q.front();
        q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        if (u != s) can_arrive[s][u] = true;
        for (auto v : edges[u]) {
            if (dis[v] > dis[u] + 1) {
                dis[v] = dis[u] + 1;
                if (dis[v] <= k + 1) q.push(v);
            }
        }
    }
}

vector<int> maxv[MAXN];

void calc(int s)
{
    maxv[s].resize(6);
    for (int i = 2; i <= n; i++) {
        if (i != s && can_arrive[s][i] && can_arrive[1][i]) {
            maxv[s][5] = i;
            sort(maxv[s].begin(), maxv[s].end(), [](int i, int j) { return value[i] > value[j]; });
        }
    }
}

signed main()
{
    scanf("%lld%lld%lld", &n, &m, &k);
    for (int i = 2; i <= n; i++) {
        int x;
        scanf("%lld", &x);
        value[i] = x;
    }
    value[1] = value[0] = -1e18;
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%lld%lld", &u, &v);
        edges[u].push_back(v);
        edges[v].push_back(u);
    }

    for (int i = 1; i <= n; i++) bfs(i);
    for (int i = 2; i <= n; i++) calc(i);

    for (int i = 2; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (!can_arrive[i][j]) continue;
            for (auto x : maxv[i]) {
                for (auto y : maxv[j]) {
                    if (x == i || x == j || y == i || y == j || x == y) continue;
                    if (!x || !y) continue;
                    res = max(res, value[i] + value[j] + value[x] + value[y]);
                }
            }
        }
    }

    printf("%lld\n", res);
    return 0;
}

策略游戏 game

link

难度：绿

一道以为是博弈论实际上是简单贪心的数据结构题。

题意

  • 给定序列 A 和 B，序列中为整数，有两个人 小L 和 小Q。
  • 多次询问，每次给定四个数 l1l1，r1r1，l2l2和r2r2，小L 选择 ii 有 x=Ai,i∈[l1,r1]x = A_i, i \in [l1, r1]，小Q 选择 jj 有 y=Bj,j∈[l2,r2]y = B_j, j \in [l2, r2]，结果为 k=xyk = xy。
    小L 想让 kk 最大，小Q 想让 kk 最小，他们都很聪明，会作出最佳选择。
  • 序列长 n,m≤105n, m \le 10^5，询问数 q≤105q \le 10^5。

题解

显然需要注意的就是符号了，所以要分类讨论。
为了叙述方便，认为 00 也是正数。

  1. 小L 选正数，小Q 选最小的；
    1. 若 小Q 最小的为正数，小L 选最大的；
    2. 否则，小L 选最小的。
  2. 小L 选负数，小Q 选最大的；
    1. 若 小Q 最大的为正数，小L 选最大的；
    2. 否则，小L 选最小的。

可以用 ST表 或者线段树维护区间中的最大，最小，非负数最小，负数最大即可。
实现细节参照代码。

代码

提交记录

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
/*
author: byronwan
problem:
    url: https://www.luogu.com.cn/problem/P8818
    title: [CSP-S 2022] 策略游戏
date: 2022-11-11
*/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;

int n, m, q;
ll a[MAXN], b[MAXN];

struct SegmentTree {
    struct Node {
        ll max_ge0 /*= -1e18*/, min_ge0 /*= 1e18*/; // 不能这么做！会 CE ！
        ll max_lt0, min_lt0;
        ll maxx, minx;
        bool has_ge0, has_lt0;

        void init() // 要这么做
        {
            max_ge0 = -1e18, min_ge0 = 1e18;
            max_lt0 = -1e18, min_lt0 = 1e18;
            maxx = -1e18, minx = 1e18;
            has_ge0 = false, has_lt0 = false;
        }

        void merge(Node a, Node b)
        {
            has_ge0 = a.has_ge0 || b.has_ge0;
            has_lt0 = a.has_lt0 || b.has_lt0;
            max_ge0 = max(a.max_ge0, b.max_ge0);
            min_ge0 = min(a.min_ge0, b.min_ge0);
            max_lt0 = max(a.max_lt0, b.max_lt0);
            min_lt0 = min(a.min_lt0, b.min_lt0);
            maxx = max(a.maxx, b.maxx);
            minx = min(a.minx, b.minx);
        }

        void operator=(ll x)
        {
            if (x >= 0) {
                has_ge0 = true;
                has_lt0 = false;
                max_ge0 = min_ge0 = x;
                max_lt0 = -1e18, min_lt0 = 1e18;
            } else {
                has_ge0 = false;
                has_lt0 = true;
                max_ge0 = -1e18, min_ge0 = 1e18;
                max_lt0 = min_lt0 = x;
            }
            maxx = minx = x;
        }
    } tr[MAXN * 4];

    void build(int x, int l, int r, ll* src)
    {
        if (l == r) {
            tr[x] = src[l];
        } else {
            int mid = (l + r) / 2;
            build(x * 2, l, mid, src), build(x * 2 + 1, mid + 1, r, src);
            tr[x].merge(tr[x * 2], tr[x * 2 + 1]);
        }
    }

    Node query(int x, int l, int r, int ql, int qr)
    {
        if (ql <= l && r <= qr) return tr[x];
        int mid = (l + r) / 2;
        Node res;
        res.init();
        if (ql <= mid) res.merge(res, query(x * 2, l, mid, ql, qr));
        if (qr >= mid + 1) res.merge(res, query(x * 2 + 1, mid + 1, r, ql, qr));
        return res;
    }
} seg_a, seg_b;

void setup()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> b[i];

    seg_a.build(1, 1, n, a);
    seg_b.build(1, 1, m, b);
}

void ask()
{
    int l1, r1, l2, r2;
    cin >> l1 >> r1 >> l2 >> r2;
    auto x = seg_a.query(1, 1, n, l1, r1);
    auto y = seg_b.query(1, 1, m, l2, r2);
    ll res = -1e18;

    if (x.has_ge0) {
        ll b = y.minx;
        if (b >= 0) res = max(res, x.max_ge0 * b);
        else res = max(res, x.min_ge0 * b);
    }
    if (x.has_lt0) {
        ll b = y.maxx;
        if (b >= 0) res = max(res, x.max_lt0 * b);
        else res = max(res, x.min_lt0 * b);
    }

    cout << res << endl;
}

int main()
{
    setup();
    while (q--) ask();
}

额外注意

对于很大的静态数组初始化时，及时只初始化一部分，编译器也会将静态数组中的所有东西添加到可执行文件中，可能会导致编译错误或者 OJ 拒绝评测。

上例代码中已经标出。

星战 galaxy

link

难度：紫

考验人类智慧的随机化。

题意

  • 给定一个有向图，每条边有一个状态。

  • 有多个操作，每次执行以下操作之一：

    • 1 禁用一条边（保证启用）；
    • 2 禁用以一个点为终点的所有边；
    • 3 启用一条边（保证禁用）；
    • 4 启用以一个点为终点的所有边。

  • 每次操作后，你需要考虑如果只考虑启用的边，是否同时满足以下两个条件：

    • 1 对于每个点，是否存在一条以其为起点的长度无限的路径（每个点，每条边可经过无限多次）？
    • 2 对于每个点，是否出度为 1 ？

  • 点数 n≤5×105n \le 5\times 10^5，边数 m≤5×105m \le 5\times 10^5，操作数 q≤5×105q \le 5\times 10^5。

题解

我们先考虑要满足的条件。

可以发现，假如满足了 条件2，必然满足 条件1，以下图为例：

1

证明：假设在满足了 条件2 的图中，存在一条极长路径，终点为 uu，因为 uu 存在一条出边，所以故不存在该路径。

可以发现，若维护出度，可以 O(1)\Omicron(1) 处理每个询问，但是这样对于 操作2 和 操作4，需要 O(n)\Omicron(n) 的时间。

而维护入度，每个操作都可以 O(1)\Omicron(1) 时间内处理。

那么这样要怎么维护询问呢？

不能简单地判断和是否等于 nn ，因为可能出现这种情况：

2

所以问题就是，想办法让每个点“不同”，想到了随机化的方法：

对于每个点 uu ，赋予一个随机权值 wuw_u，
和一个要维护的量 f(u)=∑v→u∈E∧enable⁡(u→v)wvf(u) = \sum_{v \to u \in E \land \operatorname{enable}(u \to v)} w_v，即存在一条边连向它的点的权值和。
同时，记录最初 f(u)f(u) 的状态，记为 f0(u)f_0(u)。

对于每次操作：（设选中的点为 uu，选中的边为 u→vu \to v）

  • 操作1：f(v)←f(v)−f(u)f(v) \leftarrow f(v) - f(u)
  • 操作2：f(u)←0f(u) \leftarrow 0
  • 操作3：f(v)←f(v)+f(u)f(v) \leftarrow f(v) + f(u)
  • 操作4：f(u)←f0(u)f(u) \leftarrow f_0(u)

那么操作后如果 ∑f(u)=∑w(u)\sum f(u) = \sum w(u)，那么就可以认为每个点的出度都为 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
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
79
80
81
82
83
84
85
86
/*
author: byronwan
problem:
    url: https://www.luogu.com.cn/problem/P8819
    title: [CSP-S 2022] 星战 galaxy
date: 2022-11-13
*/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 5e5 + 10;

int n, m, q;
vector<int> edges[MAXN];

std::mt19937* rng;
ll w[MAXN], f[MAXN], g[MAXN];
ll tot, cur;

void setup()
{
    rng = new std::mt19937(114514);
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) w[i] = (*rng)();

    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
        f[v] += w[u];
    }
    memcpy(g, f, sizeof(f));
    for (int i = 1; i <= n; i++) tot += w[i];
    for (int i = 1; i <= n; i++) cur += f[i];

    cin >> q;
}

void solve()
{
    int op;
    cin >> op;
    switch (op) {
    case 1: {
        int u, v;
        cin >> u >> v;
        cur -= w[u];
        f[v] -= w[u];
    } break;
    case 2: {
        int u;
        cin >> u;
        cur -= f[u];
        f[u] = 0;
    } break;
    case 3: {
        int u, v;
        cin >> u >> v;
        cur += w[u];
        f[v] += w[u];
    } break;
    case 4: {
        int u;
        cin >> u;
        cur += g[u] - f[u];
        f[u] = g[u];
    } break;
    }

    if (cur == tot) cout << "YES" << endl;
    else cout << "NO" << endl;
}

int main()
{
    setup();
    while (q--) solve();
}

感受和心得

最后，作为一名选手，谈一下感受和心得。

首先，本人认为，本次的题目质量不错，比初赛好多了，而难度和去年相当。

第一题，这种枚举几个算几个是常用的 trick 了，但细节很多，在考场上做了两个小时，还挂了分。感谢 CCF 的数据，只挂了10分，而民间数据中挂了 30 到 40 分。

第二题，第一眼以为是博弈论，虽然后面看出来了是简单贪心，但感觉处理正负号太麻烦，并且时间不够（实际上还挺多的，只是因为太急了），只打了 60 分。

第三题，打了暴力，没想到是乱搞随机化。

第四题，dp 好题，也只是打了暴力，实力不够。

得分最高 280 （100 + 100 + 50 + 30），实际 230。

总结一下经验就是，要心态平稳，把能拿的分都拿到（比如第二题），注意细节，不要挂分。

还是要吐槽以下考场环境，用 win7 就不说了，省里本来说要有的 noilinux 只有 cygwin，还是 32位 的，不过有 vim 也算能用。

NOIP2022 马上就到了（写这篇博客时 2022年11月13日，广州这几天病例每天新增几千例，在家上网课，不知道能不能办)
祝愿自己和广大 OIer 们在 NOIP2022 中 RP++，再创佳绩。