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}$。

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

再接再厉吧!

添加新评论