WC2025 游记

· · 生活·游记

Day -?

在所有人的期盼下终于停课了，要不然我就停课了。

让安装 Linux，搞了很久 VMware。

打代码源的抽象比赛以及听 jiangly 的抽象题目，总之就是很抽象。混乱邪恶
懒得再开一个集训总结的新文章了，所以下面是 WC 之前的所有总结。

DAG 计数

考虑状压，枚举入度为 0 的点，假设有 cnt 个，那么容斥系数为 (-1)^{cnt+1}，复杂度为 O(3^n)。
模板是 [ABC306Ex] Balance Scale，进阶一点的有 [省选联考 2024] 重塑时光。

DP 状态

不一定要是基于初始态（全局态）定义的。我们可以只存在接下来的 DP 中有用的，舍弃掉已经 DP 过的信息。例题是 [PA2019] Desant，在从左往右填每一个数的时候，并不需要存每一个数是否选过，只需要知道对于那些还没有选、但有可能选的值，比他大的有多少个，于是总状态数就减少了。
下面的 Permanent 也算。

事实上这样的优化思路就是 X 算法的本质。

vector 代替哈希表

本人在比赛及补题中多次使用 unordered_map 被制裁，望周知。

遂有了一个 vector 代替哈希表的想法。大致思路是，存元素的时候先不去重，直接往 vector 里面放，当容器大小达到一定阈值的时候拿出来去重合并。在分层图的时候可以简化为每一层转移结束后合并。
这样子可以避免当状态数达到 3\times10^6\sim8\times10^6 时哈希表访问过慢，但由此又会引申出一个问题：原本哈希表是 O(1) 的，但这里每次去重需要排序，复杂度将至 O(\log V)，其中 V 为去重前的状态数，可能是一个比较大的 \log。本人因为这个问题怒挂 30\texttt{pts}。解决方式是基数排序。

有关 mex 的 trick

例题：[THUPC 2024 初赛] 套娃。

vector 比数组慢 4 倍？

不是很懂，本人在写 [THUSC 2021] 搬东西 的时候用了 vector，本机跑了 10s，卡了很久常数到了 8s。结果换成数组一下子成了 2s？老师的解释是，nodgd 曾经说过，vector 比数组慢至少 4 倍……

一个线性代数的结论

对于 p\in\texttt{primes}，有如下结论成立：

-1&(p-1\mid k) \\ 0&(p-1\nmid k) \end{cases}\pmod{p}

下半部分的证明：
此时显然 p\ge3，则 p 为奇数。考虑模 p 的原根 g（显然存在），令 i\equiv g^{x_i}(i\in[1,p))，于是有 \forall i\ne j,x_i\ne x_j。
所以 \sum_{i=1}^{p-1}i^k\equiv\sum_{i=1}^{p-1}g^{kx_i}\equiv\sum_{i=1}^{p-1}g^i\equiv\sum_{i=1}^{p-1}i\equiv0。

Tutte 定理与 Tutte-Berge 公式

定理内容：

公式内容：

上述的 \operatorname{odd}(V) 表示 V 中有多少个联通分量具有奇数个顶点。
证明

容易发现 Tutte 定理就是 Tutte-Berge 公式的特殊情况。其中公式给出了一般图计算最大匹配的方式，可以用来 DP 之类的，例题是 [ARC190E] Gaps of 1 or 2。

异或哈希判断区间交

应该算是经典 trick 了，又遇到了所以记录一下。定义合法区间是与其他区间相离或包含的区间（即不能相交），则异或哈希可以快速判断是否合法。优点是简单快捷，缺点是可能被卡哈希。

积和式

一个类似于行列式的东西，用 per(A) 或者 perm(A) 表示。定义为：

per(A)=\sum_P\prod_{i=1}^nA_{i,P_i}

可以看到与行列式的差别只有符号。

这玩意有一些组合意义。比较典型的是二分图完美匹配的个数：对于 G=(L,R,E)，其中 L,R 分别表示左部和右部的点集，定义方阵 A，满足如果左部的 i 与右部的 j 有连边，则 A_{i,j}=1，反之 A_{i,j}=0，则完美匹配的数量恰好为 per(A)。

稀疏矩阵的积和式：Permanent。

左旋右旋的直接运用

这是构造题的一种思路，先将题目给出的东西抽象为二叉树，用左旋右旋来描述题干给定的操作。于是只需在二叉树上面构造。参考 [WC2022] 序列变换。

Day -7

说要培训 Linux，让我们自带电脑，结果一直到晚上 9 点才开始……（感觉讲了，但又没完全讲）讲一半电脑还没电了。
发现下好的 Linux 没有中文，红温了，这下不得不好好学 English 了。

Day -5

参加 P 营和 T 营的同学都走了，晚自习只有我和 recollect_i 两个人。（苟王之后也来了）
冷冷清清

Day -3

跟着苟王训练，啥也不会。评价是采九朵莲。

去做往年的 WC 真题，越做越感觉自己是小丑了。想到正解不敢写，以及不会做“建议降蓝”。传来了 P 营 Stinger \texttt{200+} 以及 T 营 hyx_0704 \texttt{300+} 的喜报，听说今年有一些“观察题”，和平时的联系呼应上了属于是。

Day -2

题目链接
比昨天有进步，昨天只会 D1T1，今天会 D1T1+Day2。大胜利。

把交互库整得 UKE 了

Day -1

又爆 U 啦，现在 U 贬值这么严重？？？
显然这里指的不是粉色的 U，是黑色的 U。（即答：unique）

Day 0

到绍兴一中了，入住了宿舍。据说食堂的饭不好吃，试了下发现还可以，挺不戳的，但是饭菜都有点冷，算是扣分项。事实上后面再吃就感觉不太行了。

开幕式，先是绍剧。中途其中一个演员的扇子掉了，鉴定为节目效果。

然后是杜子德讲话，没想到还挺幽默的。说了一些不那么枯燥的东西，比想象的好得多。（左数第 4 个就是，但是画质感人，没办法，手机是这样的）

后面还有节目，印象比较深刻的是别人跳舞的时候看到群里一堆人在发“妹子能不能分我一个”……

打了会儿原神，到点之后老师把电子设备收了。同学们开始讲 PKU 的题目。有点困，所以睡的比较早（？）。同宿舍的几个都是一中的，在打 CF。

day 1

听说早上 7 点有非常大的铃声，本人睡得比较死，没听到，八点起来的，事实上差点找不到队伍了。

上午 zky 讲非随机性算法。感觉很妙，前面大半部分基本都听懂了，最后上了一点奇怪数学，晕……

zky 的原创题（讲义上没有，记一下）

给定一个序列，多次操作，操作有：

  • 区间翻转
  • 查询 [l,r] 中选出一个子集的最大异或和。
n,q\le5\times10^4,a_i\in[0,2^{60})

solution:
维护 100 个序列，每个序列的所有数均有 \frac12 的概率为 0 或 a_i，区间翻转正常使用平衡树维护。查询的话每次取出每个序列在 [l,r] 上的区间异或和作为点值，建立线性基，则我们认为它有较高概率是 [l,r] 真正的线性基。zky 说对于每组询问的错误率是 2^{-100} 的。

小结：随机化主要用来控制条件，当条件的情况比较多而复杂时，考虑将权值变为 0\operatorname{or}1 是否会好做，以及是否有一定的正确率。增大正确率的方法主要有多次随机以及增大随机值域两种。

下午是 sjy 的图论专讲，啥也没听懂。喵喵喵
学习了耳分解与双极定向，还有什么树分解、树宽，不是很懂。
其中边三联通分量的求法比较重要，给了两个阅读材料：边四联通分量，边五联通分量。

晚上被拉去听了苟王的论文交流：(%%%)

Day 2

整个寝室都睡着了，8:40 才起床……

上午讲 AI 应用，没啥好记的。
（我打不过 AI o3……采九朵莲）

下午是郭羽冲讲思维题选讲。没有脑子，不会思维题。喵喵喵
但是还是小结一下：一般遇到比较棘手的题目限制，考虑通过各种方法将其抽象为常见模型。例如，可以手摸 corner 寻找规律，数形结合，拆分限制/贡献等。将其转化为常见模型后可能也不太可做，甚至可能是熟知的 NP/NPC 问题，此时要再次从题目中提取关键条件，或许在一些特殊限制下即便是上述问题也可以做到多项式复杂度，所以也无需害怕。

Day 3

考试日。

题目不放了，到处都有。

T1 30\min 就写完了，自认为可以过，去看 T2。发现 T2 没什么头猪，决定回去 SelfEval 测一下 T1，结果喜提 65\texttt{pts}。后面发现输入顺序反了，此时离考试开始过了大概 70\min。（感觉把浪费的这点时间拿去拼 T2 可以金？？？）
由于 T2 没什么头猪，去开 T3。什么，这不是线段树模板题吗？？？于是开始狂码 5k 代码，调了很久，代码力太菜了是这样的。总共花费 3h 在 SelfEval 上通过了 T3。但是本人的写法有点小问题，不会离散化，于是直接在 [0,10^9] 上动态开点。这样的话由于有效点有 2n 个，所以数组应该要开 60n。但是这会 MLE。本人造了一组随机数据，感觉这样有效点会取满，事实上我线段树只用了 30n 个点。最后提交的代码开的是 40n，会不会 RE 就看天命了。感觉 SelfEval 可以过就没啥问题。
冲 T2，但没什么时间了，最后只有 22\texttt{pts}。

SelfEval Score：100+22+100=222\texttt{pts}
听说大众分 228？？？

我是唐诗，把密码条丢了，不知道成绩喵。只能后面看官方成绩有没有 FST 了……
upd：并没有 FST 捏，可爱喵\~

晚上讲题，听说 T2 在 CTS 那边 0 人通过？总之被 30\min 速通了……

“可以举个水表示题目非常水，可以举个厕所表示题目非常厕所。”
“大家避雷这个出题人。”

文艺汇演

一上来设备有点问题，电脑要更新，全场开始举“技术问题” 的牌子。

Day 4

上午讲随机化与算法设计，感觉都是比较宽泛的东西，不太具体，不如 zky 的浅谈随机性算法。

下午黄洛天讲动态图连通性（强制在线），讲了三个算法：

  1. 边修改，均摊复杂度 O(n\log^2n)。
  2. 边修改，带随机化。（没听懂捏，下线了）
  3. 点修改，修改复杂度 O(m^{\frac34})，查询复杂度 O(m^{\frac14})。（对修改定期重构，阈值是 m^{\frac23}）

显然第一个比较重要。其他两个几乎用不到，知道就行。
这东西比较高级，反正我是不会写的:)

事实上到现在 WC 就基本算结束了，有部分学校是提前返回，所以已经可以陆续看到有人离开了。

晚上回寝室，因为比较重要的事都结束了，大家都比较放松，先是原神启动，然后开始德州扑克。（反正只要输麻了总有人会做慈善，所以总有些人在 all in）
玩一半接到了通知，让我们出一套关于冬令营所学内容的题目。讨论了一会儿，Acoipp 给出了 T1 的 idea，感觉还不错，本人接下了 std 和 data 的任务。

Day 5

上午是稀疏图上更快的单源最短路算法，女讲师好看捏，感觉讲的还是挺清楚的，但是这玩意发明出来好像除了坑人以外没什么用？
本来打算带电脑去把 std 写了的，结果出门的时候忘记把前一条上交的电脑装包里了。于是开始和 Acoipp 讨论 T2。他给了一个无向图哈密顿路的基础题，但是只会 O(nk^32^k)。我们两个疯狂对峙之后 pass 了一堆想法，最后还是只做到了 O(nk^32^k)。我给了他一个对转移系数 dp 的 idea，后面他好像优化到了 O(nk^22^k)。

下午是从模拟退火到概率编程，巧了我 T1 的 std 就是模拟退火。这次没有忘记带电脑，贺了一个板子，把 std 写完了。但是感觉 data 超级难造，跟他们讨论说每个人贡献一点。（其实最后发现大家都没空，所以还是我一个人造的）

这天也是 CTS Day2 的考试，之后前 6 可以进入下一轮。最后苟王考出来还是很遗憾，看了下其他人的分数，发现其实苟王只需要 CTS Day1 正常发挥（他被 T1T2 搞炸了心态，所以 T3 会做也没用了，只有 60\texttt{pts}）就可以进前 6 了。他也挺难过的，一个人休息了好一会儿，调整了情绪之后晚上来我们寝室玩。nodgd 给我们买了奶茶。前半段感觉苟王还是有点 emo，后面我们没出题了，开始一起打德扑，慢慢气氛活跃了起来，苟王也终于缓过来了。

Acoipp 的 T2 一直在“我会了”“我假了”之前反复切换。剩下的人在出 T3。

Day 6

上午是国家队选拔，老师让去熟悉下流程，于是什么都没有带，结果到了之后广播说所有观看国家队选拔的营员不得提前离场。蚌埠住了，只能罚坐 4\rm h。提问环节其余的老师都挺正常的，但是我们杜老师仍旧非常幽默。Acoipp 原话：“他是懂阴阳的。”

下午闭幕式，Au 258，Ag 212，Cu 163，这还是 WC 吗？？？
他真的把所有获奖选手的学校名字都念了一遍，我哭死。

晚上回寝室继续造数据。造到一半发现不对劲，发现很难造出方案数多的数据，大部分数据的方案数都是 bool。又想了想发现这种强数据似乎根本不存在？？？于是只需要将暴力剪个枝（记忆化搜索）应该就过了？？？什么，T1 被爆了？？？
和 Acoipp 讨论了一下发现真的被爆了。骂骂咧咧……（我的 std 和造好的 data 啊）
不过还好，稍微修改了一下题面，把限制放宽就解决了。但是已经比较晚了，所以决定第二天再重写 std。

听说 3 道题的数据都不好造……

Day 7

早上 8 点的大巴，启程回 CQ 了。（可惜的是忘了去自习室看一下，听说有好东西）
飞机上补了一下 std 和 checker，然后太困了就睡了会儿，数据是回家造的。（左边苟王，右边 free4all，前面 nodgd，瑟瑟发抖）
注：nodgd 把 gf 也带上了，所以一直在前面撒狗粮……

题目链接：ABC。