WC2021 咖啡记

其实咖啡就是拿铁的意思

Day 0

发现明天就是冬令营了但是我还什么都不会，已经差不多做好了要继续拿 $\text{Cu}$ 的准备。

去年的 $\text{WC2020}$ 是我爆炸的开始。由于当时水平不行，所以省选成绩在当时的情况下还稍微能看。但 $\text{WC2020}$ 看 $\text{l}\color{red}{\text{indongli2004}}$ 拿 $\text{Ag}$，$\text{Z}\color{red}{\text{cus}}$ 差点 $\text{Ag}$，我却只有踩线 $\text{Cu}$，就很难受。

之后的 $\text{APIO, CSP-S, NOIP}$ 全都挂成 $\text{sb}$，令人自闭。

Day 1-4

第一课堂好难，第二课堂好 $\text{sb}$。

这些边我不加，这些边我不加！暴力怎么做，暴力是不是！加边！加边！加边！然后，并查集查询！

上午：《随机算法》

下午：$\text{zyy:}$ 随机算法没有前途。

$\text{lyx:}$ 大家都掉线了？那我讲快一点。

捐赠（$\times$）聚敛（✔）

啥都没学会，就记着些梗，吃枣药丸。

由于坐标 $\text{HN}$，省选 $\text{A+C}$，所以省内没有安排考点。教练通知要带笔记本在会议室考试，惊奇地发现笔记本只有 $\text{windows}$......

于是花了好长的时间装了个虚拟机并且调整成能看的样子......

发现自己真的什么都不会，慌得一批，于是疯狂复习复习复习。然而显然没用

Day 5

早上应该是按时到了？买了两根巧克力棒，然后随便找了个位置坐下来。

很快就开题了，右边是 $\text{M}\red{\text{entos\_Cola}}$，左边是 $\text{Y}\red{\text{uanchenpu}}$。瞟了一眼三道题，发现果然和之前预料的一样，难度降低了不少的样子。

但是没有 $\text{C++11}$ 差评，好毒。

给了自己每题 $\text{20min}$ 先想想，发现对于 $\text{bracket}$ 和 $\text{fib}$ 毫无想法，但是感觉 $\text{expr}$ 是可做题。加上本人感人的数学功底，所以直接扔了 $\text{fib}$，开始想 $\text{expr}$。冥冥之中感觉对这道题有一些印象。

十分显然的是要建立表达式树，然后变成树上问题。

十分显然的是要分位考虑。

十分显然的是不能二分。

此时突然灵光一现，记起之前给同学们出的一道十分简单的题，就是叶子上是 $0/1$，然后每个节点是 $\text{and/or}$，求根节点是 $0/1$ 的方案数。

那就枚举好了，直接转化为上面一模一样的问题，直接做就可以拿到 $\text{55pts}$。

再加上 $\text{naive}$ 的模拟，就有 $\text{70pts}$。

此时还不到 $\text{1h}$，挺开心的。觉得 $\text{70pts}$ 还是比较赚的，于是开始码码码。一遍就码过了前面几个小样例，但是大样例 $\text{RE}$，于是去上个厕所压压惊。遇到了 $\text{Z}\red{\text{cus}}$，发现他的分好像已经吊打我了，方脏。

回来之后仔细 $\text{debug}$ 发现有一个地方要用 $\text{int}$ 我却用了 $\text{char}$，溢出导致我的其他变量被修改了，淦。

改了改就可以跑大样例了，复杂度是 $\mathcal{O}(nm|E|)$，显然跑不过大样例。但是本机跑个 $\text{13s}$ 就跑出来了，答案是对的，松了一口气。

于是开始想正解。回想自己的题，其加强版需要使用动态 $\text{dp}$，但这里一次修改的 $0/1$ 位置过多了，不能用。陷入自闭......

再仔细地检查了一下，确保自己不挂分。此时已经 $\text{2h}$，还只有 $\text{70pts}$ 让我稍微有点担心。

于是扔了 $\text{expr}$，转去想 $\text{bracket}$。此时右边的 $\text{M}\color{red}{\text{entos\_Cola}}$ 貌似已经爆切 $\text{bracket}$，搞到我的心态了。

不过下考发现他并没有过，所以我又双叒叕自己搞自己的心态了

仔细观察了一下，发现形如 $\text{a}\rightarrow \text{b}\leftarrow{c}$ 且边上颜色相同的图形是十分有用的，但是仍然没有什么思路。

接下来就是 思考 $\rightarrow$ 掉线 $\rightarrow$ 重连 $\rightarrow$ 思考 的循环辽，一直在画图但是一直没有任何思路......

再去上个厕所，遇到了初三神仙 $\text{j}\color{red}{\text{uju}}$，发现他的分好像已经吊打我了，方脏。

回来之后稍微有了一些想法，观察发现 $\text{a}\rightarrow \text{b}$ 合法和 $\text{b}\rightarrow \text{a}$ 合法是等价的。同时如果出现了 $\text{a}\rightarrow \text{b}\leftarrow{c}$ 的图形，那么走到 $\text{a}$ 和走到 $\text{c}$ 实际上就等价了。

那不就 加边！加边！加边！然后，并查集查询！ 并查集将他们缩在一起就可以了？

手玩一下发现能过两个样例，于是开始码。

发现过不了自己手玩过了的第二个样例，艹。思考后发现是因为当一些点缩在一起之后，边也需要放到一个点上。

那不就启发式合并就可以了？写了之后发现跑不出来，意识到可能是重边太多了。所以把链式前向星改成 $\text{set}$，直接过了所有样例。

此时我仍然认为这是个乱搞，因为我并没有严谨证明为什么满足上述条件就完全是一个等价类。考后发现挺显然的

手造了一个极限数据，发现要 $\text{0.9s}$，方脏。又双叒叕去上了个厕所，于是遇到了老 $\text{K}$，他的分显然吊打我，所以完全不方脏。

回来之后想着如何搞掉 $\text{set}$，发现如果有 $\text{C++11}$，直接上 $\text{unordered\_set}$ 就啥事没有了，但是没有，艹。

还是改成了 $\text{vector}$，发现极限只要 $\text{0.2s}$ 了，稳得一批。

此时已经 $\text{12:45}$ 左右，赶紧去 $\text{rush}$ 了一个 $\text{fib}$ 的 $\text{20pts}$。然鹅忘了无解于是保龄了

接下来大概 $\text{30min}$ 就在考场各种安享晚年，再想想 $\text{expr}$ 要怎么写 $\text{100pts}$。但是显然一直没有想到。

到了最后 $\text{15min}$，$\text{Z}\color{red}{\text{cus}}$ 突然开始狂码，看起来他要阿卡了。但是他没有写完，还是比较可惜的。下考之后 $\text{Z}\color{red}{\text{cus}}$ 一句 “ $2^m$ 预处理 ” 点醒梦中人，发现我就是 $\text{sb}$，为啥这不会。

还忘记了我的 $\text{bracket}$ 是正确的，以为他可以被卡。实际上完全卡不掉

之后去吃了 金拱门 麦当劳，下午+晚上机房团建，快乐。

Day 5.5

意识到我的 $\text{fib}$ $\text{20pts}$ 都没有，还以为 $\text{bracket}$ 可以被卡，十分难过，觉得自己没有 $\text{Ag}$ 了。

在洛谷讨论里看到有人问 $160$ 左右什么牌，有人说 $\text{Au}$，但是我显然没相信。

Day 6

上午模拟赛，错过论文答辩还是蛮可惜的。

下午 $\text{4:00}$ 才闭幕式，于是一直在打摆。

然后打开直播闭幕式，突然发现 $\text{Au}$ 线 $158$？？！？！那看起来就算挂了分还是有机会的。

十分紧张，看大家成绩一个个出来辽，有些担心第一题是不是会沦为暴力分。不过就算沦为暴力分也有 $\text{Ag}$，也能算差强人意。

最后出来了，$\text{170pts}$，踩到了，还有机房的 $\text{z}\color{red}{\text{xyhymzg}}$ 也拿到了 $\text{Au}$。没挂其他分了还是很开心的，毕竟人生第一块 $\text{Au}$。

总结

本次 $\text{WC2021}$ 十分幸运地拿到了 $\text{Au}$，但是运气成分其实占比是很大的。要是我没有突然想到 $\text{expr}$ 的 $\text{70pts}$，我很可能就做不完 $\text{bracket}$。

还是不够强，导致只有遇到稍微擅长一些的题目才能多拿些分。实际水平完全比不上很多同省/外省的同届神仙。

再接再厉吧！