WC自闭记

· · 个人记录

听课不想写了，除了杂题选讲听懂一些以外基本啥都没听懂.......

Day 1(好像也只有1天)

8:30准时进去了，网站居然没崩（之前NOI同步赛的时候好像崩了5分钟），可喜可贺！!1

点开pdf，发现居然是3道传统，可喜可贺！!1

日常把所有题先扫了一遍，T3数学题肯定直接跳了，然后看T1和T2感觉应该都可做，然后T2是计数题感觉自己应该擅长一些，就决定开题顺序T2->T1->T3。

稍微想了一会儿之后发现好像O(nmE)是送你的，直接把表达式树建出来，然后假设f_{x,i}表示计算完x子树内的运算结果是i的方案数DP一下就可以。

然后这样就70了？？？挺震惊的。

这会儿应该才9:00左右，瞬间感觉挺稳的，于是上了个厕所开始想T1。

但是想了差不多半个小时一点思路都没有，于是想算了去看T3有没有能写的东西，然后发现好像20分似乎是送你的，于是就花了5分钟写了一下就跑路了（主要是真的对这种数学题有恐惧症啊！!1）。

然后又回去想了半个小时T1，终于想出了一个O(n^6)的DP，32分应该是稳了，于是决定去看T2能不能把T2切了。

然后本场我最傻逼的事情就要来了：

我回去看T2的时候突然想到，m似乎很小，应该对m进行特殊处理，然后min与max至于1-m的相对大小顺序有关，于是我们可以对所有大小关系预处理出DP答案。

然后我们就得到了一个极其优秀的O(m!mE)的做法！!1

但最牛逼的就是，我不知道为什么考场上脑子一抽，把m!想成了1024，然后瞬间感觉这时间复杂度十分优秀，然后就直接开码了。

码的时候发生了一个小插曲，就是上厕所的时候看到changruinian2020大佬迎面走来。

他问我：您多少了？

我：只会T2（O(m!mE)）。

他：这T1,T2都挺水的啊，我T2已经打完了，准备开始打T1。

这会儿才10:30，这就是人与人的差距吗......

然后码了差不多半个小时之后，一测大样例：

“欸，我怎么卡死了。”

然后冷静了一下才发现，m!好像不止1024，甚至比1024大上无数倍！!1

当时差不多11:00左右，感觉自己瞬间万头草泥马从心头奔过，旁边的changruinian2020已经切了两道题，我只有一道题有思路然后还假了。

还好现在自己的心态比以前强大多了，迅速冷静了一下后发现我这个DP改成O(2^mE)很简单，我们并不关心算出来具体是谁而是是否大于等于某个值。

于是可以假设f_{x,S,0/1}表示x子树内，把集合S中的数当成1，算出来的值是0/1，然后对于n个数组求答案的时候可以轻易算出最后答案是x的方案数。

然后稍微改了改自己的DP，码完差不多11:30，感觉切了一道题其实还行。

然后做数学题是不可能的，这辈子都不可能的，于是果断选择了肝T1。

重新组织思路想了想，发现这个题似乎跟[HNOI2019]校园旅行挺像的（这道题跟找回文串也有关系）。进一步思考可以发现，若x到y有一条类似于([((()))])（即只有嵌套没有拼接），可以把x和y放在同一个连通块内，然后任意连通块内的点都能互相到达。

于是写了一个O(m^2)的校园旅行弱化版，但是发现大样例过不去，想了想其实问题在于我这个想法只考虑了串类似于((()))((()))((()))，但并没有考虑类似于((())(()))(())的情况（即我这样DP只处理了只有一次嵌套后拼接的情况，但拼接完可以接着嵌套）。

自然，有种十分的简单的暴力就是我一直进行O(m^2)的DP直到没有新的连通块形成。但是进一步思考可以发现，对于一个点的所有同种入边，其连接的所有点都应该在同一个连通块。

于是我们可以每次把这些点缩成一个点，把其边集通过启发式合并在一起，这样每缩一次都要减少deg-1条边，时间复杂度显然有保证。

你以为我就即将AC\ T1，拿到220的高分？我考场也是这么想的。

但问题就在于，我在想出上述的一切时，时间已经来到了12:30。然后我前一天又没睡好，这天又没带咖啡喝，导致我困得如随时要停机一般。再加上我还没有想清楚所有细节就开码了，这样都不翻车谁翻车？

然后后面的故事就很简单了，因为发现离考试结束只剩20分钟，于是改了改自己之前假的暴力然后交了。

期望得分：32+100+20=152。我也不知道为啥没有O(nm^2)的部分分。

Day 2

发成绩。

看到Au\ 158分之后心凉了半截，不会吧不会吧，不会我真的离Au差6分吧。（我现在真的想对当时的自己说一句：别急，不是差6分，后面有惊喜等着你）

然后。。。。

我现在真的十分无语，你知道有多夸张嘛，就是Ag倒数第二页最后一个人刚好是153，然后同学们都开始奶我稳了（他们都知道我估分152），然后翻页一看我的名字正好出现在Ag最后一页，156分......

不是吧，O(nm^2)就多4分？

后来有个群友发了成绩才发现我的成绩是56+100+0，我T3暴力写错了，草.......

顺带一提，changruinian2020大佬喜提全国第6，老nb了。而我考得那么垃圾居然是CQ第2？（没错CQ只有一个Au）可能是大佬们都发挥失常/不愿意给CCF送钱吧。

也许退役前的倒数第二次比赛就这样结束了，十分遗憾并没有捞到自己的第二个Au。

下一次就是决定命运的省选了，即使有着联赛离省队线40分，校线60分遥远差距，还是尽力最后一搏吧，联合省选2021\ rp \ ++

God\ Bless.