游记 - GDCPC 2024

Day -?

和尊贵的 luogu 管理以及 zhafde fans club 群友组队，原因是想起来去年七月命名的 Alchemy 队名似乎还没用上（当时是用来申请 ucup，只是懒惰的我一次也没有打）。

然后群里转发了一个个人赛的链接，说每个队要派一个去打，然后我就稀里糊涂地报了名。

Day 0

2024.5.25.

发现个人赛可以不报名。OK。

讨论了板子问题，最后由 zhafde 整出高达 31 页的板子整理。恐怖如斯。我提出建议，筛法可以不带。

上午翘开幕式，然后简单试机，并且膜拜 wzj33300。午饭在真功夫等了半天，然后睡觉。13:57 醒来，父母都以为 14:30 开个人赛，而我看着选手牌上的 14:00，一路狂奔。结果到了才发现，怎么真的延误成了 14:30……

个人赛题意简述

A：给一个序列，多次询问如果去除下标在 $[l_i,r_i]$ 的元素，剩下来的任选三个数组成三角形，最大的周长是多少。无解输出 -1。$n\le 5\times 10^5$，$q\le 10^6$。

B：给一棵有根树。定义一个点集是好的，当且仅当其中任意两点的 LCA 为同一个点，且这个点在集合中。定义一个点集的集合是好的，当且仅当每个点集是好的，并且全部点在且恰好在一个点集中。忘了怎么算点集的集合的权值，反正要求全部好的点集集合的权值的加和或乘积。$n\le 200$。

C：给一个正整数序列 $a$ 表示 $n$ 个人的初始分数。两个人打一场比赛的结果，是都加 $1$ 分或者某一个人加 $3$ 分。若每个人都打了 $k$ 场比赛，求分数严格高于第一个人的分数的人数的最小值。$2\le n\le 10^5$，$1\le k\le 10$。

D：多次询问，构造方案，在 $n\times m$ 的棋盘上放 $k$ 个马，使得它们两两不能攻击，规则用中国象棋的。$t\le 10^4$，$n,m\le 10^3$。

E：构造无限长的 01 字符串 $S$，$S_i$ 为 $i$ 在二进制下 popcount 的奇偶性，$i$ 从 $0$ 开始。每次给一个含 0/1/? 的字符串，对每个前缀问每种给 ? 填 01 的方式中，前缀的在 $S$ 中的子串个数的和。范围忘了，似乎是 $10^5$ 级别。

F：简而言之是一道二合一，是入门题加背包和体积很大、价值比较小的多重背包。大到 $10^{12}$。

G：有 $n$ 块钱，要数有多少组正整数 $(a,b,c)$，满足 $40a+39b+\frac{1}{2}c=n$。$n\le 10^{16}$。

H：定义一个 $n$ 个点的简单图是好的，当且仅当任意两点间的路径数目在 $[k,k+1]$ 之间，给定 $k$，数好的图的个数。数据范围忘了。

历程

先看了会 A，没有秒。发了会呆，打算跟榜开题。然后开了 G，然后过了。

然后想明白了 A，有对数长度的性质。简而言之，就是最大的三个数 $a,b,c$ 不能满足，那么 $2c\le a$，依此类推，所以最多暴力试 $\log V$ 次。然后写了个主席树，两只 $\log$，被卡了。

然后再跟榜，看 C，发现好像有点麻烦。然后口胡了这样一个办法：$a\le a_1$ 和 $a>a_1+3k$ 的直接无视，可以让它们都赢来让中间的部分输。然后二分中间的部分有几个可以不超过 $a_1+3k$，其余的直接全赢即可，这部分全赢的就挑较大的那些。这个地方的判定感觉有点模糊，直接写：记录每个点还给输的总次数和给平局的总次数，一胜二负可换三次平局，不行就 break。然后就过了，没有卡我，估计是数据造水了，感觉不是很严谨。

然后发现 A 不需要主席树，直接维护前/后缀的前 37 大就可以了。这个时候开始了智熄操作：两发罚时没删调试语句，两发罚时罚 iostream。从结果上看，这个失误直接导致了我掉出前 20。

切完三道签到，已经过了 100 min，感觉有点久了。榜上有别人做的就是 D，然后就想到矩形和等腰直角三角形是满足条件的。更广泛一点，一个八边形，其中只有横边、纵边、45 度边的，都是可以的。然后就想能不能枚举四个角，时间太久，没想到优化。

看了眼其他题，B 似乎最优做法是 $n^4$，目测不好写也比较久。E、H 不可做。F，已经把题意拆成上面所述的了，然后发现不会这种大体积背包，然后放弃。

结束前 6 min，突然觉得 D 可以只枚举左上和右下的三角形，然后就慌了，以为会了。

赛后

讲了讲 D 做法，突然发现假了，那还是活该。

手动滚榜，一万个名字被读错，分辨率有点低下。

广州市铁一中学初二学子战绩斐然！祈福英语实验小学荣获 rk6！长沙市雅礼中学包揽 rk1,2！而且双双切下 B 题！

以为有讲题。

回来看题解，发现 B 正解就是 $O(n^4)$，而 F 可以反转价值和体积，属于是智熄了一下。

没事，不过是热身。

Day 1

2024.5.26.

到处都是小情侣和女装大佬。

题意简述

A：给一些线段，数有多少个田字格，大概这样，不记得了。

B：给若干个字符串，求两两 LCPS 的长度总和，$\operatorname{LCPS}(A,B)$ 为最长的 $s$，满足 $s$ 为 $A$ 后缀、也为 $B$ 前缀。$\sum |S|\le 3\times 10^6$。

C：忘了，因为我没做，但好像很简单。

D：超长题面，懒得读。

E：对 $n$ 个点的竞赛图，有任选 $m$ 个点，必有一个点指向其他所有点、必有一个点被其他所有点指向。求点的出度集合的最小大小。$n,m$ 比较大，多测。

F：给一个无向图，找到一对 $(u,v)$ 和 $\lceil\frac{m}{n-1}\rceil$ 个 $u\to v$ 的边不交的路径。$n,m\le 3\times 10^5$。

G：$10$ 次询问，每次给定 $[l,r]$，求 $\max_{l\le x<y\le r} \gcd(x,y)$。$1\le l<r\le 10^{12}$。

H：有 $m$ 个盒子，$n$ 个球。每个盒子有容量。编号为 $i$ 的球操作时会从序列 $a_i$ 中找到最先的没满的盒子，然后投进去，如果没有就不投进去。给这些球排序，让它们依次操作，使得投进盒子的球数最大。输出最大球数及一种方案。$t\le 500$，$n\le 500$，$m\le 500$，$\sum nm\le 2.5\times 10^5$。

I：有长为 $n$ 的正整数序列 $a$，和 $m$ 个限制，形如 $a_{x_i}\ge a_{y_i}+a_{z_i}$，求最小的 $\sum a$，满足 $\sum a\le 10^9$，无解输出 -1。忘了范围了。

J：考虑编号为 $2\sim n$ 的无向图，$u,v$ 有边当且仅当 $u|v\lor v|u$。求所有联通点对的编号乘积之和。$n\le 10^{11}$。

令人无语的赛程

有意思的是，被堵门一段时间才进场，没有人检查身份证，而且发现电脑仍未重置。

先跟会榜。突然发现智障地卡了 G 题，卡了一卡，感觉没很水的做法，还是写整除分块。反正过了 G、I、C，其中 heaksicn 在 I 题贡献了 2 发罚时，zhafde 通过了 C。

猜 J，heaksicn 提出是一大坨联通图再加比较大的一些质数的样子，觉得非常有道理。然后发现要求质数前缀和和质数平方前缀和。尝试场推 min_25 筛，式子推对了，时间全假了。加了记忆化，还是跑不动。一点不会实现，开摆。

队友写 E，暴力写挂，我实在急了，我说你要不猜吧，然后发现他猜的贼有道理，就是首项和末项猜一下，然后中间是一大串 $n$，然后公差为 $2$ 下降。然后就 TLE 了，原来是 iostream 导致的。过了。至此，heaksicn 贡献了 4 发罚时，可见其贡献之大。

会了 B，知道是 AC 自动机，每个点直接 fail 子树 sum 乘上 trie 子树 sum，然后可能还要容斥。然后突然又不会了，想不清楚怎么计算“longest”。吃了点东西，又会了，发现可以让每一个都有贡献，算最长 border 就行。然后过了。这个东西呢，是两片面包夹着紫薯、蛋、番茄、肌肉、生菜的矩形三明治，感觉味道很奇怪。

然后队友继续 H，这可是他们最喜欢的费用流。我猜 F，猜不到一点，只往找 dfs 树（后来看看这一部分本来应该对对脑电波的）、找点双、以及最大化最小割想，显然越想越偏。

还剩一个小时，一个 H 调不出来，急了。然后把输出排列的部分写拓扑排序（这玩意能写 40 min 有点绷不住），然后就 TLE 了，最后认为是费用流导致的。

什么？你问 A 和 D？加训 ds 的 zhafde 早就看了，并且表示不可做，从最终的榜上看，的确没人做。

虽然上了金线，也高于校另一队两名，但还是感觉遗憾。seanlsy 场推 min_25 筛，除了膜拜还有什么！广东实验中学初二如此强悍，还能说什么！

结局

打星没有任何 award。和同校的吃了个 KFC，然后跑路。

正如 zhafde fans club 群友所说，但凡带一个 min_25 板子（我愚笨的脑子还是实在想不起那个优秀的实现方法和时间的证明），但凡他把 F 题想到树的灵感拿出来讨论一下（其实好像也讨论不到那么妙的做法，虽然我隐约对过脑电波），（H 实在不知道咋回事，有人 zkw 费用流可过，让我们队很懵），其实很多缺憾都弥补了。

经验问题。实力问题。

然后在 Q 群和知乎吃瓜。