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++，再创佳绩。

[AHOI2009] 中国象棋

大意

给定 nn 行， mm 列的格子，可以涂黑，求每行每列涂黑不超过 22 个的方案数。

题解

设 f(i,j,k)f(i, j, k) 为考虑了前 ii 行，有 jj 列涂黑 11 个， kk 列涂黑 22 个的方案数。

有转移：

f(i,j,k)←f(i,j,k)f(i+1,j,k)←f(i,j,k)(m−j−k1)f(i+1,j−1,k+1)←f(i,j,k)(j1)f(i+1,j+2,k)←f(i,j,k)(m−j−k2)f(i+1,j,k+1)←f(i,j,k)(m−j−k1)f(i+1,j−2,k+2)←f(i,j,k)(j2)f(i, j, k) \leftarrow f(i, j, k) \newline f(i + 1, j, k) \leftarrow f(i, j, k) \binom {m - j - k} 1 \newline f(i + 1, j - 1, k + 1) \leftarrow f(i, j, k) \binom j 1 \newline f(i + 1, j + 2, k) \leftarrow f(i, j, k) \binom {m - j - k} 2 \newline f(i + 1, j, k + 1) \leftarrow f(i, j, k) \binom {m - j - k} 1 \newline f(i + 1, j - 2, k + 2) \leftarrow f(i, j, k) \binom j 2 \newline

代码

提交记录

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
/*
author: byronwan
problem:
    url: https://www.luogu.com.cn/problem/P1972
    title: [AHOI2009] 中国象棋
date: 2022-09-12
*/

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 110, MOD = 9999973, INV2 = 4999987;

typedef long long ll;

int n, m;
ll f[MAXN][MAXN][MAXN];

ll comb(ll x, ll y)
{
    assert(y == 1 || y == 2);
    if (y == 1) return x;
    else return x * (x - 1) % MOD * INV2 % MOD;
}

signed main()
{
    cin >> n >> m;
    f[0][0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= m; j++) {
            for (int k = 0; j + k <= m; k++) {
                f[i + 1][j][k] = (f[i + 1][j][k] + f[i][j][k]) % MOD;
                if (m - j - k >= 1)
                    f[i + 1][j + 1][k]
                      = (f[i + 1][j + 1][k] + f[i][j][k] * comb(m - j - k, 1) % MOD) % MOD;
                if (j >= 1)
                    f[i + 1][j - 1][k + 1]
                      = (f[i + 1][j - 1][k + 1] + f[i][j][k] * comb(j, 1)) % MOD;
                if (m - j - k >= 2)
                    f[i + 1][j + 2][k]
                      = (f[i + 1][j + 2][k] + f[i][j][k] * comb(m - j - k, 2)) % MOD;
                if (j >= 1 && m - j - k >= 1)
                    f[i + 1][j][k + 1]
                      = (f[i + 1][j][k + 1]
                          + f[i][j][k] * comb(m - j - k, 1) % MOD * comb(j, 1) % MOD)
                      % MOD;
                if (j >= 2)
                    f[i + 1][j - 2][k + 2]
                      = (f[i + 1][j - 2][k + 2] + f[i][j][k] * comb(j, 2) % MOD) % MOD;
            }
        }
    }

    ll res = 0;
    for (int j = 0; j <= m; j++)
        for (int k = 0; k + j <= m; k++) res = (res + f[n][j][k]) % MOD;

    cout << res << endl;
}

[HAOI2007] 反素数

题意

  • 设 g(x)g(x) 为 xx 的因数个数。
  • 定义反素数为满足 ∀0<y<x,g(y)<g(x)\forall 0 \lt y \lt x, g(y) < g(x) 的正整数。
  • 求不大于 nn 的最大反素数

题解

首先设 xx 为反素数， x=p1k1p2k2…pqkq, p1<p2<…<pq,0≤kix = p_1^{k_1}p_2^{k_2} \ldots p_q^{k_q}, \ p_1 \lt p_2 \lt \ldots \lt p_q, 0 \le k_i 。

有 k1≥k2≥…≥kqk_1 \ge k_2 \ge \ldots \ge k_q 。

证明：若 ki<kj,i<jk_i \lt k_j, i \lt j ，则有 y=…pikjpjki…y = \ldots p_i^{k_j} p_j^{k_i} \ldots ，使得 g(y)=g(x),y<xg(y) = g(x), y < x，显然不满足条件。

反素数为所有因数个数相同的数中最小的一个。

故暴力搜索所有质数，找出不大于 nn 的满足如上条件的因数个数最多的最小的数即可。

代码

提交记录

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
/*
author: byronwan
problem:
    url: https://www.luogu.com.cn/problem/P1463
    title: [HAOI2007] 反素数
date: 2022-09-11
*/

#include <bits/stdc++.h>

using namespace std;

const int primes[]
  = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 79, 83, 89, 97},
  p_cnt = 24;

int n;
int res_cnt, res_minx = 1e9;

void dfs(long long x, int cnt, int p, int lst_k)
{
    // cerr << "# " << cnt << " " << x << " " << p << " " << lst_k << endl;
    if (cnt > res_cnt || (cnt == res_cnt && x < res_minx)) res_cnt = cnt, res_minx = x;
    else if (cnt <= res_cnt && x >= res_minx) return;
    if (p >= p_cnt) return;

    long long acc = 1;
    int k = 0;
    while (x * acc <= n && k <= lst_k) {
        // cerr << "$ " << primes[p] << " " << k << endl;
        dfs(x * acc, cnt * (k + 1), p + 1, k);
        acc *= primes[p];
        k++;
    }
}

int main()
{
    cin >> n;
    dfs(1, 1, 0, 1e9);
    cout << res_minx << endl;
    cerr << res_cnt << endl;
}

[HNOI2004] 敲砖块

大意

  • 给定一个如下的三角形，每个格子有数字。
  • 可以敲掉一些格子，若要敲掉当前格子，则必须敲掉左上和右上的格子。
  • 若最多能敲掉 mm 个格子，求最大的权值和。
  • 第一行格子数目 n≤50n \le 50 。
1
2
3
4
5
6
14  15  04  03  23
  33  33  76  02
    02  13  11
      22  23
        31

题解

可以发现，敲掉的应该是这样的：

1

可以想到 dp ，但不行，因为下一层的转移依赖上一层敲掉了哪些砖块，而显然不能状压。

考虑进行转换。

首先先向左推。

1
2
3
4
5
14  15  04  03  23
33  33  76  02
02  13  11
22  23
31

然后向左旋转 90°90 \degree 。

1
2
3
4
5
23
03  02
04  76  11
15  33  13  23
14  33  02  22  31

这样，要敲掉的就变成了：

2

发现，每一行要敲的必须不多于上一行敲的加 11 。

可以 dp 了。
设 f(i,j,k)f(i, j, k) 为考虑完了第 ii 行，该行敲了 jj 个，一共敲了 kk 个最大权值。
有转移：

f(i,j,k)=max⁡(f(i−1,j′,k−l),j−1≤j′≤i−1)+sum(i,1…l)f(i, j, k) = \max(f(i - 1, j', k - l), j - 1 \le j' \le i - 1) + sum(i, 1 \ldots l)

代码

提交记录

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
/*
author: byronwan
problem:
    url: https://www.luogu.com.cn/problem/P1437
    title: [HNOI2004] 敲砖块
title: 2022-09-11
*/

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 60, MAXM = 1250;

int n, m;
int a[MAXN][MAXN], b[MAXN][MAXN];
int sum[MAXN][MAXN];

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= (n - i + 1); j++) cin >> a[i][j];
    }
}

void pre()
{
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) b[n - j + 1][i] = a[i][j];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) sum[i][j] = sum[i][j - 1] + b[i][j];
    }
}

int dp[MAXN][MAXN][MAXM];
int calc()
{
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= i; j++) {
            for (int k = j * (j + 1) / 2; k <= m; k++) {
                for (int l = max(j - 1, 0); l <= i - 1; l++) {
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][l][k - j] + sum[i][j]);
                }
            }
        }
    }

    int res = 0;
    for (int i = 0; i <= n; i++)
        res = max(res, dp[n][i][m]);
    return res;
}

int main()
{
    read();
    pre();
    cout << calc() << endl;
}

[SCOI2010] 生成字符串

题意

  • 给定 nn, mm ；
  • 生成 nn 个 11 ，mm 个 00 组成的字符串；
  • 满足在任意一个前缀中，11 的个数大于等于 00 的个数。

题解

将选择 11 看作向右走， 00 看作向上走，那么所求即为从 (0,0)(0, 0) 出发，到 (n,m)(n, m) ，不经过直线 x−y+1=0x - y + 1 = 0 的方案数。

先不考虑个数限制，所有的方案数为 (n+mn)\binom {n + m} n 。

接下来考虑不合法的方案数

如图，所有经过 x−y+1=0x - y + 1 = 0 直线的路径，可以在第一次经过直线处翻折，使得终点为 (m−1,n+1)(m - 1, n + 1) 。

1.png

同时对于到 (m−1,n+1)(m - 1, n + 1) 的所有路径，沿第一次经过直线处翻折，得到唯一一条非法路径。

因而非法的个数为 (n+mn+1)\binom {n + m} {n + 1} 。

答案为 (n+mn)−(n+mn+1)\binom {n + m} n - \binom {n + m} {n + 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
/*
author: byronwan
problem:
    url: https://www.luogu.com.cn/problem/P1641
    title: [SCOI 2010] 生成字符串
*/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MOD = 20100403, MAXN = 2e6 + 10;

ll n, m;

ll qpow(ll x, ll p)
{
    return !p ? 1 : p & 1 ? x * qpow(x, p ^ 1) % MOD : qpow(x * x % MOD, p >> 1);
}

ll fac[MAXN], inv[MAXN];
void init()
{
    fac[0] = 1;
    for (ll i = 1; i < MAXN; i++) fac[i] = fac[i - 1] * i % MOD;
    inv[MAXN - 1] = qpow(fac[MAXN - 1], MOD - 2);
    for (ll i = MAXN - 2; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % MOD;
}

ll comb(ll n, ll m) { return fac[n] * inv[m] % MOD * inv[n - m] % MOD; }

int main()
{
    cin >> n >> m;
    init();
    cout << (comb(n + m, n) - comb(n + m, n + 1) + MOD) % MOD << endl;
}

[SDOI2009] HH的项链

大意

给定一个序列，每次询问区间内有多少不同的数。

题解

考虑离线处理询问。

先把所有的询问按照右端点从左到右排序，然后考虑加点，查询左端点。

记 f(x)f(x) 为当前区间 x…rx \ldots r 的答案

每次加入一个新的数字，
只会对在该数字上一次出现的位置后产生贡献，
即 f(lst(x)…x)←f(lst(x)…x)+1f(lst(x) \ldots x) \leftarrow f(lst(x) \ldots x) + 1 ，
例如：

1
2
3
2 1 5 3 4 2 3 5
    |---------|
        + 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
/*
author: byronwan
problem:
    url: https://www.luogu.com.cn/problem/P1972
    title: [SDOI2009] HH的项链
date: 2022-09-12
*/

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 10;

struct BinaryArray {
    int a[MAXN];

    void update(int i, int x)
    {
        for (; i >= 1; i -= i & (-i)) a[i] += x;
    }

    int query(int i)
    {
        int res = 0;
        for (; i < MAXN; i += i & (-i)) res += a[i];
        return res;
    }
} bin;

int n, m, a[MAXN];
struct Ask {
    int id, l, r;
} ask[MAXN];
int res[MAXN];

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

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

    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> ask[i].l >> ask[i].r;
        ask[i].id = i;
    }
    sort(ask + 1, ask + 1 + m, [](auto x, auto y) { return x.r < y.r; });
}

int lst[MAXN];
void pre()
{
    static int lst_i[MAXN];
    for (int i = 1; i <= n; i++) {
        lst[i] = lst_i[a[i]];
        lst_i[a[i]] = i;
    }
}

void solve()
{
    for (int i = 1; i <= m; i++) {
        auto a = ask[i];
        for (int j = ask[i - 1].r + 1; j <= a.r; j++) {
            bin.update(j, 1);
            bin.update(lst[j], -1);
        }
        res[a.id] = bin.query(a.l);
    }
}

int main()
{
    setup();
    pre();
    solve();

    for (int i = 1; i <= m; i++) cout << res[i] << endl;
}

[TJOI2011] 树的序

大意

  • 有一个序列 aa ，元素各不相同，按照如下的方式建成二叉查找树：
    • 按顺序插入每个元素；
    • 若树是空的，直接成为根节点；
    • 若比当前节点小，插入左子树，否则插入右子树。
  • 给定一个序列，求生成的树一样的同种序列字典序最小。
  • 序列长度 n≤105n \le 10^5

题解

答案就是建成树后的先序遍历，难点在优化建树。

对于一个节点 uu ，序列中的元素 xx 会插入进来，当且仅当遍历时，若 uu 在遍历到的 vv 的左子树中，x<val(v)x \lt val(v) ，否则 x>val(v)x \gt val(v) 。

记上述的 xx 的最大值和最小值为 mx(u)mx(u) 和 mn(u)mn(u) 。
则对于左右儿子，有：

mn(l(u))=mn(u),mx(l(u))=val(u)−1mn(r(u))=val(u)+1,mx(r(u))=mx(u)mn(l(u)) = mn(u), mx(l(u)) = val(u) - 1 \newline mn(r(u)) = val(u) + 1, mx(r(u)) = mx(u) \newline

而每个节点的左右儿子，是接下来的第一个 mn(u)≤l(u)<val(u)<r(u)≤mx(u)mn(u) \le l(u) \lt val(u) \lt r(u) \le mx(u) 。

用线段树维护 pospos 序列，其中 pos(u)=i⇐a(i)=upos(u) = i \Leftarrow a(i) = u ，支持获取区间最小值和单点修改。

从左往右考虑，若到 ii ，使用线段树获取最小的满足条件的 l(i)l(i) 和 r(i)r(i) ，然后 pos(i)←∞pos(i) \leftarrow \infty ，使线段树只获取后面的值。

代码

提交记录

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

using namespace std;

const int MAXN = 1e5 + 10;

int n;
int a[MAXN], pos[MAXN];

struct SegmentTree
{
    int minx[MAXN * 4];
    
    void build(int x, int l, int r) {
        if (l == r) {
            minx[x] = pos[l];
            return;
        }
        int mid = (l + r) / 2;
        build(x * 2, l, mid), build(x * 2 + 1, mid + 1, r);
        minx[x] = min(minx[x * 2], minx[x * 2 + 1]);
    }

    int query(int x, int l, int r, int ql, int qr) {
        if (ql > qr) return 1e9;
        if (ql <= l && r <= qr) return minx[x];
        int res = 1e9, mid = (l + r) / 2;
        if (ql <= mid) res = min(res, query(x * 2, l, mid, ql, qr));
        if (qr >= mid + 1) res= min(res, query(x * 2 + 1, mid + 1, r, ql, qr));
        return res;
    }

    void update(int x, int l, int r, int q, int val) {
        if (l == r) {
            assert(l == q);
            minx[x] = val;
            return;
        }
        int mid = (l + r) / 2;
        if (q <= mid) update(x * 2, l, mid, q, val);
        else update(x * 2 + 1, mid + 1, r, q, val);
        minx[x] = min(minx[x * 2], minx[x * 2 + 1]);
    }
} seg;

void read()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n;

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

int l[MAXN], r[MAXN], minx[MAXN], maxx[MAXN];

void solve(int i)
{
    l[i] = seg.query(1, 1, n, minx[i], a[i] - 1);
    r[i] = seg.query(1, 1, n, a[i] + 1, maxx[i]);
    if (l[i] < 1e9) {
        minx[l[i]] = minx[i];
        maxx[l[i]] = a[i] - 1;
    }
    if (r[i] < 1e9) {
        minx[r[i]] = a[i] + 1;
        maxx[r[i]] = maxx[i];
    }
    
}

void output(int i)
{
    cout << a[i] << " ";
    if (l[i] < 1e9) output(l[i]);
    if (r[i] < 1e9) output(r[i]);
}

int main()
{
    read();
    seg.build(1, 1, n);
    
    minx[1] = 1, maxx[1] = n;
    for (int i = 1; i <= n; i++) solve(i);
    
    output(1);
    cout << endl;
}

[ZJOI2007] 物流运输

大意

  • 给定一张无向联通图，有边权。
  • 考虑若干天，每天有一些节点不可用。
  • 每天一条路径，若当天的路径与前一天不同，有额外花费 kk 。
  • 求总花费最小，即求每天的路径权综合与切换路径的花费的和最小。

题解

考虑 dp 。

设 f(i)f(i) 为第 ii 天最小花费，包括切换路径的花费 。

考虑每天，f(i)f(i) 已经计算。
枚举规划之后 jj 天的路径，计算在这若干天中都可以使用且不变化的最小路径长度 dd ，然后：

f(i+j)=f(i)+dj+kf(i + j) = f(i) + dj + k

给一条按照能用 xx 天计算的路径更新 f(i+y),y<xf(i + y), y \lt x 肯定不优，因此每次计算 dd 只有更新最后的即可。

先预处理节点 uu 在第 ii 天时还能连续用几天 g(u,i)g(u, i) 即可：

g(u,i)={g(u,i+1)available0otherwiseg(u, i) = \begin{cases} g(u, i + 1) & \text{available} \\\\ 0 & \text{otherwise} \end{cases} \newline

代码

提交记录

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
/*
author: byronwan
problem:
    url: https://www.luogu.com.cn/problem/P1772
    title: [ZJOI2006] 物流运输
date: 2022-09-12
*/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 30, MAXD = 110;

int day, n, cost, m;
vector<pair<int, int>> edges[MAXN];
bool available[MAXN][MAXD];
int left_time[MAXN][MAXD];
ll dp[MAXD];

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

    cin >> day >> n >> cost >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges[u].push_back({v, w});
        edges[v].push_back({u, w});
    }

    for (int i = 1; i <= n; i++) fill(available[i] + 1, available[i] + day + 1, 1);
    int cnt;
    cin >> cnt;
    while (cnt--) {
        int u, x, y;
        cin >> u >> x >> y;
        for (int i = x; i <= y; i++) available[u][i] = false;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = day; j >= 1; j--)
            left_time[i][j] = available[i][j] ? left_time[i][j + 1] + 1 : 0;
    }

    memset(dp, 0x3f, sizeof(dp));
    dp[1] = 0;
}

int dis[MAXN];
bool vis[MAXN];
ll dijkstra(int l, int r)
{
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[1] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push({dis[1], 1});

    while (q.size()) {
        int u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto e : edges[u]) {
            int v = e.first, w = e.second;
            if (l + left_time[v][l] - 1 < r) continue;
            if (dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                q.push({dis[v], v});
            }
        }
    }

    return dis[n];
}

void solve(int d)
{
    for (int i = d; i <= day; i++) {
        ll dis = dijkstra(d, i);
        dp[i + 1] = min(dp[i + 1], dp[d] + (i - d + 1) * dis + cost);
    }
}

int main()
{
    setup();
    for (int i = 1; i <= day; i++) solve(i);
    cout << dp[day + 1] - cost << endl;
}

[IOI2007] training 训练路径

大意

给定一个无向图, 有树边和非树边, 删去若干条非树边, 使得图中不存在偶环 (点不得出现两次), 求删去最小边权.

题解

限制

考虑每条非树边 ee, 设 d(e)d(e) 为 ee 的两端在树上的距离.

  1. 当 d(e)d(e) 为奇数时, 加上 ee 就会形成偶环, 显然不行.

  2. 此外, 两条非树边不能重叠, 如下图所示:

    1

    图中绿色的边为非树边. 此时, 红色路径就构成了一个环. 证明: 由 1 , x+yx + y, y+zy + z 均为偶数, 红色长 x+z+2=(x+y)+(y+z)−2y+2x + z + 2 = (x + y) + (y + z) - 2y + 2 显然也是偶数.

    下图同理

    2

综上, 合法的图应该是这样的

3

树形dp + 状压dp

可以用 树形dp 和 状态压缩 解决.

可以把问题转化为合法地加上的最大边权.

设 fu,Sf_{u, S} 为在 uu 的子树中, 不考虑子集合 SS 的最大边权.

显然有 fu,S≥fu,S′,S′⊆Sf_{u, S} \ge f_{u, S'}, S' \subseteq S

转移情况:

  1. 从儿子直接转移 fu,S=∑v∈son(u),v∉Sfv,∅f_{u, S} = \sum_{v \in son(u), v \not\in S} f_{v, \emptyset}

  2. 存在 u∈x→yu \in x \to y 且 x,y∈sons(u)x, y \in sons(u), 显然 u=lca⁡(x,y)u = \operatorname{lca}(x, y)

    设 x→yx \to y 为 {x,p1,p2,⋯ ,pn,u,qm,qm−1,⋯ ,q1,y}\{x, p_1, p_2, \cdots , p_n, u, q_m, q_{m - 1}, \cdots, q_1, y\}.

    设 aa 为贡献, 那么: (认为 x=p0,y=q0x = p_0, y = q_0)

    a=fx,∅+∑i=1nfpi,{pi−1}+fy,∅+∑i=1mfqi,{qi−1}a = f_{x, \emptyset} + \sum_{i = 1}^{n} f_{p_i, {\{p_{i - 1}\}}} + f_{y, \emptyset} + \sum_{i = 1}^{m} f_{q_i, \{q_{i - 1}\}}

    转移为

    fu,S∪{x,y}=fu,S+a(x,y∉S)f_{u, S \cup \{x, y\}} = f_{u, S} + a (x, y \not\in S)

[NFLS 1462/3] 岛屿 题解

大意

给定一个基环树森林, 求每棵基环树的直径之和.

题解

树上求直径很容易, 设 fuf_u 为以 uu 在 uu 的子树中以 uu 为一端的最长链的值.

fu=max(fv+w), {v,w}∈edges(u),v≠fauf_u = max(f_v + w),\ \{v, w\} \in edges(u), v \not= fa_u,

res←max(res,fx+wx+fy+wy), {x,wx},{y,wy}∈edges(u),x,y≠faures \leftarrow max(res, f_x + w_x + f_y + w_y),\ \{x, w_x\}, \{y, w_y\} \in edges(u), x, y \not= fa_u

而基环树则要考虑环.

考虑破环为链, 再扩大一倍.

那么 res←max(res,fi+fj+len(i,j)), 1≤i,j≤2∗n,∣j−i∣<nres \leftarrow max(res, f_i + f_j + len(i, j)), \ 1 \le i, j \le 2 * n, |j - i| \lt n, 其中 nn 为环的长度.

使用前缀和, 贡献则变为 fj+len(1,j)+fi−len(1,i)f_j + len(1, j) + f_i - len(1, i).

考虑使用单调队列.

在队头, 每次弹出 i−j≥ni - j \ge n.

在队尾, 每次弹出 g(j)<g(i)g(j) < g(i), 其中 g(x)=fx−len(1,x)g(x) = f_x - len(1, x).

每次用队头元素更新即可.