抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

七つの海

今日、海を見た。もう怖くない

博客

随笔

朋友

归档

关于

2019 CCPC 秦皇岛区域赛 回顾

七海

题解

发布于：2020年9月18日

次浏览

写在前面

已经有相当一段时间没有写过博客了；也许是因为牛客多校某次讲评时老师说的：如果为了写博客而写博客，那么写博客对于个人而言又有多少除了心理满足之外的意义呢？这句话一时间使我陷入了迷惘—— 应当警惕隐藏在其中的形式主义（

但是在漫长的补题不写博客的日子后，我渐渐发现博客的优点也确实存在：比如客观上可以加深对于题目的印象；外加如今 8 个月的寒假已经结束，是时候重新启用这个博客记录题解了。

废话少说，那么从今往后（包括那些今天之后修改的博文）的博文，如果是题解，就尽量控制废话数量：不再包含题目的详细的翻译什么的（但根据情况可能会有一句话的大意描述），也不会按照顺序一个题一个题的创建标题了——完全根据补题情况——也就是说补了几个写几个；虽然少了很多东西，但是会包括必须的资源下载的链接；至于每一个具体的题目，简单的讲解思路就直接贴代码了。

团队链接：https://vjudge.net/contest/395445/ 比赛链接：https://codeforces.com/gym/102361/ 没有找到官方的题解幻灯片 / PDF

D - Decimal

老签到题了，大胆猜测只有 2 和 5 的数字满足要求，就过了（

但是考场却 WA 了一发，还搞了半天，离谱儿

代码

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
#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>

using namespace std;
using longs = long long;
using uint = unsigned;

inline int nextInt()
{
    int x = 0, f = 0, ch = getchar();
    while (!isdigit(ch)) ch == '-' && (f = !f), ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}

int main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int t = nextInt();
    while (t --)
    {
        int n = nextInt();
        while (n % 2 == 0) n /= 2;
        while (n % 5 == 0) n /= 5;
        printf(n == 1 ? "No\n" : "Yes\n");
    }

    return 0;
}

F - Forest Program

也是个简单的题目；给一个包含一些树和仙人掌树的“森林”，你可以删除一些边以破坏掉全部的仙人掌树，使得得到的森林仅包含树；求模意义下达到目标的方案数；

仙人掌树，指的是那些不包含自环和重边，每一条边可能且最多只属于一个简单环的连通图。

思路

如果一个图是树，又或者是森林，那么随便怎么删边，它都一定满足题目要求，那么假设这个森林里有 m 个边，方案数量就是 \(2^m\) 种；

如果一个连通图是仙人掌，且假设它一共有 m 条边，含有一个边长为 c (m > c) 的环，那么：

  • 不属于环的部分：和上面一般树/森林一样，可以随意删除
  • 属于环的部分：环内可以随意删除，但是至少要删去 1 条边

那么可以通过简单的 DFS 找到所有的环，然后根据上面的结论，将非环部分和每一个环分别处理，然后结果乘起来就得到的了答案；

代码

需要注意输入的图可能包含多个连通块，需要进行处理后才能计算答案

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
#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <functional>
#include <bitset>
#include <vector>

using namespace std;
using longs = long long;
using uint = unsigned;

inline int nextInt()
{
    int x = 0, f = 0, ch = getchar();
    while (!isdigit(ch)) ch == '-' && (f = !f), ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}

struct edge
{
    int u, v, w, next;
    edge() = default;
    edge(int u, int v, int w, int next)
    : u(u), v(v), w(w), next(next) {}
};

const int N = 3e5 + 5, M = 5e5 + 5;
const int inf = 0x3f3f3f3f;
const longs mod = 998244353;

longs fastPow(longs a, longs b)
{
    longs ans = 1;
    while (b)
    {
        if (b & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans % mod;
}

namespace FWS
{
    int head[N];
    int tot;
    edge ee[M * 2];

    void init(int n = N - 1)
    {
        memset(head, -1, sizeof(int) * (n + 1));
        tot = 0;
    }

    void addEdge(int u, int v, int w)
    {
        ee[tot] = edge(u, v, w, head[u]);
        head[u] = tot ++;
    }

    inline void forEach(int st, const function<void(edge&)>& func)
    {
        for (int c = head[st]; ~c; c = ee[c].next)
            func(ee[c]);
    }
}

vector<int> ring;
bitset<N> vis;
int dfn[N];

void dfs(int u, int p)
{
    dfn[u] = dfn[p] + 1;
    vis[u] = true;
    FWS::forEach(u, [&](edge &e)
    {
        if (e.v == p) return;
        if (dfn[e.v])
            if (dfn[u] > dfn[e.v])
                ring.push_back(dfn[u] - dfn[e.v] + 1);
            else;
        else dfs(e.v, u);
    });
}

int main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    auto n = nextInt(), m = nextInt();
    FWS::init(n);
    auto cnt = m;
    while (m --)
    {
        int u = nextInt(), v = nextInt();
        FWS::addEdge(u, v, 0);
        FWS::addEdge(v, u, 0);
    }
    dfn[0] = 0, dfs(1, 0);
    for (int i = 1; i <= n; ++ i)
        if (!vis[i]) dfs(i, 0);
    for (auto ii : ring) cnt -= ii;
    auto ans = fastPow(2, cnt);
    for (auto ii : ring)
    {
        auto t = fastPow(2, ii);
        t = (t - 1 + mod) % mod;
        ans = ans * t % mod;
    }
    printf("%lld\n", ans);

    return 0;
}

不要看到树上有环就满脑子 tarjan 啊 kora，好好地区别 SCC 和环啊草！

I - Invoker

简单的 DP；虽然看起来吓死人，但是三个字母长的序列翻来覆去也就六种情况，直接暴力转移完全大丈夫

于是就有了下面这种在考场上写的丑陋代码

代码

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
#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <array>
#include <unordered_map>

#define VAR(var) ""#var" = " << var

using namespace std;
using longs = long long;
using uint = unsigned;

inline int nextInt()
{
    int x = 0, f = 0, ch = getchar();
    while (!isdigit(ch)) ch == '-' && (f = 1), ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}

const int N = 1e5 + 5;
longs dp[N][6];
unordered_map<char, string> mm[6];
string s;

inline void mov(int x)
{
    int a = x - 1, b = x;
    char aa = s[a - 1], bb = s[b - 1];
    if (aa == bb)
    {
        for (int i = 0; i < 6; ++ i)
            dp[b][i] = dp[a][i];
        return;
    }
    for (int j = 0; j < 6; ++ j)
    {
        dp[x][j] = 0x3f3f3f3f3f3f3f3f;
        for (int i = 0; i < 6; ++ i)
        {
            auto add = 0;
            if (mm[i][aa][1] == mm[j][bb][0] &&
                mm[i][aa][2] == mm[j][bb][1])
                add = + 1;
            else if (mm[i][aa][2] == mm[j][bb][0])
                add = + 2;
            else add = + 3;
            dp[x][j] = min(dp[x][j], dp[x - 1][i] + add);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    auto &m = mm[0];
    m['Y'] = "QQQ", m['V'] = "QQW", m['G'] = "QQE", m['C'] = "WWW", m['X'] = "QWW";
    m['Z'] = "WWE", m['T'] = "EEE", m['F'] = "QEE", m['D'] = "WEE", m['B'] = "QWE";
    for (auto &ii : m)
    {
        for (int i = 1; i < 6; ++ i)
            mm[i][ii.first] = m[ii.first];
        swap(mm[1][ii.first][1], mm[1][ii.first][2]);
        swap(mm[2][ii.first][0], mm[2][ii.first][1]);
        mm[3][ii.first] = mm[2][ii.first];
        swap(mm[3][ii.first][1], mm[3][ii.first][2]);
        mm[4][ii.first] = mm[1][ii.first];
        swap(mm[4][ii.first][0], mm[4][ii.first][1]);
        mm[5][ii.first] = mm[4][ii.first];
        swap(mm[5][ii.first][1], mm[5][ii.first][2]);
    }
    cin >> s;
    for (int i = 0; i < 6; ++ i) dp[1][i] = 3;
    auto siz = s.length();
    for (int i = 1; i < siz; ++ i) mov(i + 1);
    longs ans = dp[siz][0];
    for (int i = 1; i < 6; ++ i)
        ans = min(dp[siz][i], ans);
    cout << ans + siz << endl;

    return 0;
}

J - MUV LUV EXTRA

给定参数 a 和 b，记截断小数的小数部分的循环节长度为 l，出现的循环节循环部分长度为 p，要求计算 \[ a \times p - b \times l \] 的最大值；a 和 b 均为正整数；

思路

本来还以为要考虑 a 和 b 的大小关系，考虑什么单调性什么什么的，结果连怎么找到循环节都没想出来，经济基础都没建立还满脑子上层建筑，跟个脑瘫似的（笑）一直听着隔壁队伍大声吵吵 KMP，也没做出这个题==

但是它确实是脑瘫 KMP 题；

一般 KMP 找到的是什么？模式串所有前缀的 border —— 也就是最长的公共真前后缀；这样当模式串在后缀的后面匹配失败的时候，就可以直接原地起飞回到前缀的后面，省去了前缀部分的匹配。

这个题目要关注的是被截断的小数部分，可以看成字符串；因为要求的循环节是从后面延申的，所以求所有前缀的 border 并无卵用，应该求后缀的 border；因此我们 KMP 之前需要翻转小数部分

那么我们可以发现，原本 KMP 中的 border 的前缀部分现在变成后缀，后缀变成了前缀；现在的后缀和前缀依然是相等的；这样就符合了循环小数的定义：我们可以把字符串后缀除了 border 后缀部分的部分看作是循环节，后缀 border 看作是循环节的延申，就可以对于每一个后缀求出 p 和 l 了；

这里本来有张图，但是画错了……

需要注意的是这并没有覆盖全部的情况：比如字符串 ...ABCABCA，它只考虑了 l = 3, p = 4 和 l = 3, p = 7 的情况，没有考虑到 l = 6 和 p = 7 的情况，但是因为 a 和 b 都是正整数，所以显然 l 较小的时候比较占优势；因为 border 是最大的真公共子串，所以它一定会包含所有可以包含的部分，所以它总是会包含最优的 l；

如果不是这样的话这就变得有点麻烦了（

代码

注意：因为字符串的下标从 0 开始，所以 p = 0 （即第一位失配）的值是无意义的，不应该考虑；

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
#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cassert>

using namespace std;
using longs = long long;
using uint = unsigned;

inline int nextInt()
{
    int x = 0, f = 0, ch = getchar();
    while (!isdigit(ch)) ch == '-' && (f = !f), ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}

const int N = 1e7 + 5;

template <class T>
void buildKMP(const T *arr, vector<int> &kmp, int length)
{
    kmp.resize(length + 1);
    int i = 0, j = kmp[0] = -1;
    while(i < length)
        if(-1 == j || arr[i] == arr[j])
        {
            ++ i, ++ j;
            if (i == length || arr[i] != arr[j])
                kmp[i] = j;
            else kmp[i] = kmp[j];
        }
        else j = kmp[j];
}

int main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    string s;
    longs a, b;
    cin >> a >> b;
    getline(cin, s, '.');
    getline(cin, s, '\n');
    reverse(s.begin(), s.end());
    vector<int> kmp;
    buildKMP(s.c_str(), kmp, s.size());
    const auto siz = s.size();
    longs ans = -0x3f3f3f3f3f3f3f3f;
    for (int p = 1; p <= siz; ++ p)
    {
        int l = p - kmp[p];
        ans = max(ans, a * p - b * l);
    }
    cout << ans << endl;

    return 0;
}

此外还有需要注意的是：上面代码的优化后的 KMP 求出的并不是严格的 border，虽然就算不管这个还是可以过掉这道题就是了，但是也许可以进行更深层次的讨论；

E - Escape

一个 n * m 的矩阵，有的位置有墙，其他的可以通行；在第一行的上面有 a 个机器人，在最后一行下面有 b 个出口；机器人只能走直线，但是你可以加入转向器（两个方向对换，但是阻止另外两个方向）改变机器人前进的方向；问 a 个机器人是否都能够到达出口；

思路

有的人看到只有 100 的数据范围就想到了网络流，有的人看到了 a 进 b 出想到网络流，还有的人纠结了转向器的含义纠结了半个小时

首先给出结论：若可以到达终点，任何两个机器人的行动路线之间一定不会有长度大于 0 的公共部分；或者说，不会有两个机器人通过同一个转向器；解释如下：

  • 若没有障碍，没有转向器：一个入口格子上只能有一个机器人；他们直走，互相平行；
  • 若它们经过了同一个转向器转向：那么转向前它们的方向相同，但这样的机器人对在起点就不存在；
  • 若他们被不同的转向器转到同一方向：在前面的转向器一定会阻挡后面的机器人；

因此，可以得到推论：每一个格子只可以被横着通过一次，竖着通过一次；若转向，会同时占用横竖；

综上所述，可以建立网络流：在空格子之间建立双向边，在“横格子”和“竖格子”之间建立双向边，跑最大流即可；若最大流等于机器人总数，则满足题目要求。

代码

网络流最大流的图中可以出现重边！不用担心，嗯流就完事了（

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <functional>
#include <queue>

#define USE_DINIC

using namespace std;
using longs = long long;
using uint = unsigned;

inline int nextInt()
{
    int x = 0, f = 0, ch = getchar();
    while (!isdigit(ch)) ch == '-' && (f = !f), ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}

const int X = 110;
char g[X][X];
int p[X], e[X];
int n, m, t, a, b;
int h[X][X], v[X][X];

using number = int;               // 设置流量数据类型
const int N = X * X * 3, M = N * 10;

struct edge
{
    int u, v, next;
    number w;
    edge() = default;
    edge(int u, int v, number w, int next)
            : u(u), v(v), w(w), next(next) {}
};

namespace FWS
{
    int head[N];
    int tot;
    edge ee[M * 2];

    using method = function<void(const edge &e)>;

    void init(int n = N - 1)
    {
        memset(head, -1, sizeof(int) * (n + 1));
        tot = 0;
    }

    int addEdge(int u, int v, number w)
    {
        ee[tot] = {u, v, w, head[u]};
        return head[u] = tot ++;        // 返回加入的边的编号，方便处理重边
    }

    void forEach(int u, const method &iter)
    {
        for (auto ii = head[u];
             ii != -1;
             ii = ee[ii].next)
            iter(ee[ii]);
    }
}

namespace FN
{
    constexpr int inf = 0x3f3f3f3f;    // 严格匹配 number，不要自动转型！
    int S, T, total = 0;    // 重新建图之后的节点数

    int addEdge(int u, int v, number w)
    {
        auto pos = FWS::addEdge(u, v, w);
        FWS::addEdge(v, u, 0);
        return pos;
    }
#ifdef USE_DINIC
    /**
     * Dinic 算法
     * O (n²m)
     *
     * - 在残量网络上使用 BFS 构造分层图
     * - 在分层图上 DFS 寻找增广路，并更新边权
     * - 当前弧优化：避免寻找不可能增广的边
     */
    namespace Dinic
    {
        number dis[N];
        int cur[N]; // 当前弧优化

        // 先创建分层图
        bool bfs()
        {
            using namespace FWS;
            static queue<int> q;
            memset(dis, 0x3f, sizeof(number) * (total + 1));
            q.push(S); dis[S] = 0;
            while (!q.empty())
            {
                int u = q.front(); q.pop();
                for (int cc = head[u]; cc != -1; cc = ee[cc].next)
                {
                    edge& e = ee[cc];
                    int v = e.v; auto w = e.w;
                    cur[u] = head[u];
                    if (!w || dis[v] <= dis[u] + 1) continue;
                    dis[v] = dis[u] + 1; q.push(v);
                }
            }
            return dis[T] != inf;
        }

        number dfs(int u, number inflow)
        {
            using namespace FWS;
            if (u == T) return inflow;
            number outflow = 0, rest = inflow;
            for (int &cc = cur[u]; cc != -1; cc = ee[cc].next)  // 当前弧优化
            {
                edge &e = ee[cc], &r = ee[uint(cc) ^ 1u];
                int v = e.v; auto w = e.w;
                if (!w || dis[v] != dis[u] + 1) continue;
                int t = dfs(v, min(w, rest));
                outflow += t; e.w -= t; r.w += t; rest -= t;
                if (!rest) break;
            }
            if (!outflow) dis[u] = 0;
            return outflow;
        }

        number go()
        {
            number maxFlow = 0;
            while (bfs()) maxFlow += dfs(S, inf);
            return maxFlow;
        }
    }
#elif defined USE_ISAP
    /**
     * Improved Shortest Augumenting Path
     * O (n²m)，比起 Dinic 算法只需要一次 BFS
     *
     * - 反向 BFS 并标记节点深度
     * - 正向 DFS，用尽节点的出流时回溯加深深度
     * - gap 优化：当某一深度不再包含节点时停止搜索
     * - 当 S 的深度达到 n 时，搜索一定结束
     *
     * 和 Dinic 类似，本算法也可以进行当前弧优化
     */
    namespace ISAP
    {
        int dep[N], gap[N]; // 节点的深度 & 特定深度节点的数量
        number maxFlow = 0;
        int cur[N];         // 当前弧优化

        void bfs()
        {
            memset(dep, -1, sizeof dep);
            memset(gap, 0, sizeof gap);
            dep[T] = 0, gap[0] = 1;
            queue<int> q; q.push(T);
            using namespace FWS;
            while (!q.empty())
            {
                auto u = q.front();
                q.pop();
                for (int cc = head[u]; cc != -1; cc = ee[cc].next)
                {
                    edge& e = ee[cc]; int v = e.v;
                    if (dep[v] != -1) continue;
                    q.push(v);
                    ++ gap[dep[v] = dep[u] + 1];
                }
            }
        }

        number dfs(int u, number flow)
        {
            if (u == T) return maxFlow += flow, flow;
            number used = 0;
            using namespace FWS;
            for (int cc = head[u]; cc != -1; cc = ee[cc].next)
            {
                edge& e = ee[cc], &r = ee[uint(cc) ^ 1u];
                int v = e.v; auto w = e.w;
                if (!w || dep[v] + 1 != dep[u]) continue;
                auto t = dfs(v, min(w, flow - used));
                if (t) e.w -= t, r.w += t, used += t;
                if (used == flow) return used;
            }
            if (-- gap[dep[u]] == 0) dep[S] = total + 1;
            ++ gap[++ dep[u]];
            return used;
        }

        number go()
        {
            maxFlow = 0;
            bfs();
            while (dep[S] < total)
                memcpy(cur, FWS::head, sizeof(int) * (total + 1)),  // 当前弧优化
                        dfs(S, inf);
            return maxFlow;
        }
    }
#endif

    void setInfo(int s, int t, int cnt)
    {FN::S = s, FN::T = t, FN::total = cnt;}
}

bool in(int r, int c)
{return r > 0 && r <= n && c > 0 && c <= m;}

// TODO: 思考这样处理的合理性？
// 直接加两条边或者加重边没有区别
void addEdgeX(int u, int v)
{
    FWS::addEdge(u, v, 1);
    FWS::addEdge(v, u, 1);
}

void buildGraph()
{
    using namespace FN;
    S = T = total = 0;
    FWS::init(2 + n * m * 2);
    for (int i = 1; i <= n; ++ i)
        memset(h[i], 0, sizeof(int) * (m + 1)),
        memset(v[i], 0, sizeof(int) * (m + 1));
    S = ++ total, T = ++ total;
    for (int r = 1; r <= n; ++ r)
        for (int c = 1; c <= m; ++ c)
        {
            h[r][c] = ++ total, v[r][c] = ++ total;
            if (g[r][c] == '0')
            {
                if (in(r - 1, c) && g[r - 1][c] == '0')
                    addEdgeX(v[r - 1][c], v[r][c]);
                if (in(r, c - 1) && g[r][c - 1] == '0')
                    addEdgeX(h[r][c - 1], h[r][c]);
                addEdgeX(h[r][c], v[r][c]);
            }
        }
    for (int i = 1; i <= a; ++ i)
        addEdge(S, v[1][p[i]], 1);
    for (int i = 1; i <= b; ++ i)
        addEdge(v[n][e[i]], T, 1);
}

int main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    cin >> t;
    while (t --)
    {
        cin >> n >> m >> a >> b;
        for (int i = 1; i <= n; ++ i)
            cin >> (g[i] + 1);
        for (int i = 1; i <= a; ++ i)
            cin >> p[i];
        for (int i = 1; i <= b; ++ i)
            cin >> e[i];
        buildGraph();
        auto res = FN::Dinic::go();
        cout << (res == a ? "Yes" : "No") << endl;
    }

    return 0;
}

再度验证了我全新版本网络流板子的正确性建图的时候请务必记得分配源点和汇点

K - MUV LUV UNLIMITED

是有趣的新游戏

有一棵树，先手和后手轮流操作，每次可以拿掉若干叶子结点（但不能不拿），拿到根结点的人获胜。问先手是否必胜。

思路

有很多种思考的模型：从简单考虑到复杂情况和状态转化的推导；下面进行示例

首先考虑在一棵树的某个非叶结点下面加上一个叶子结点：

  • 原树是必败态，那么先手第一次只取新叶子后就留下了必败态，所以新树是必胜态
  • 原树是必胜态，那么先手第一次取下新叶子和原树必胜态中第一步应该取下的叶子，所以新树还是必胜态

所以说，当不管原树怎么样，只要有一个叶子节点的父亲度数大于等于 2，那么它就是必胜态

当然，显然这不是充要条件：比如原树是一个链的时候，并不存在这样的叶子节点，但是依然可以根据链的长度的奇偶性来判断当前是必胜态还是必败态。显然，这也不是一个充要条件；

但是链最终可以转化成上面说的那种必胜态的树型，只是先手后手必须一片叶子一片叶子的拿才可以；那么我们假设某长度为 x 的链的末端的叶子节点有一个度数大于等于 2 的祖先，设这个祖先的子节点是 a，那么问题就变成了怎么样删除节点让 a 节点成为叶子节点时玩家先手。形式化的说：假设当前树有 k 条链，链上当前的叶子节点和上述 a 节点的距离为 xi；每次可以选择部分 xi 使得它们减一，将其中一个减小到 0 的人输掉游戏。

因为树只会有上面两种构造，所以上述两种情况包括了全部的可能性；对于任何一棵树，我们只需要分析它的所有叶子节点距离第一个父亲节点度数大于 2 的节点的距离，也就是转化成上面的形式，从而可以进行胜败态的分析。

当 xi 中出现了偶数的时候，先手可以选择所有长度为偶数的链减一；这样就转化为了所有链长为奇数的状态；当最短链长为 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
#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>

using namespace std;
using longs = long long;
using uint = unsigned;

inline int nextInt()
{
    int x = 0, f = 0, ch = getchar();
    while (!isdigit(ch)) ch == '-' && (f = !f), ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}

const int N = 1e6 + 5;
int deg[N], p[N];

int main()
{
    ios::sync_with_stdio(false);

    int t = nextInt();
    while (t --)
    {
        int n = nextInt();
        memset(deg, 0, sizeof(int) * (n + 1));
        for (int i = 2; i <= n; ++ i)
            ++ deg[p[i] = nextInt()];
        bool ok = true;
        for (int i = 1; i <= n; ++ i)
            if (!deg[i])
            {
                auto x = i, len = 0;
                while (x && deg[p[x]] == 1)
                    x = p[x], ++ len;
                ok &= bool(len % 2);
            }
        printf(!ok ? "Takeru\n" : "Meiya\n");
    }
    
    return 0;
}

A - Angle Beats

一个平面里有 n 个点，现在每次询问给一个新点 P，你需要从 n 个点中选出两个点和 P 构成直角三角形；一共询问 q 次，求对于每次询问，可以构成直角三角形的不同方案数量；

C - Sakurada Reset

给定数列 A 和 B，将数列中的每个子序列都看作一个 1000 进制数，问有多少对 (x,y)满足 x 是 A 的某个子序列，y 是 B 的某个子序列，并且 x > y；相同的子序列需要去重。

思路

有句古话说：所有的计数问题都可以直接或间接地使用动态规划来解

后记

这个出题人老二次元了而且还是个重度 MUV-LUV 厨

因为这次主要的时间花在了博弈论上，所以深有感触；对于树的两种状态的分析都有，但是却没有将它们结合起来考虑，导致这个题花了很多时间。

我们队竟然没有人会平面几何（悲），这不太行；该努力学习提升自己的塑料平面几何水平了（

参考链接

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://shiraha.cn/2020/2019-ccpc-qinhuangdao/

更新于：2020年9月18日

算法

ACM

Codeforces

Gym

评论