NOI2022游记

· · 个人记录

有的人写文章像古龙小说。

古龙好像是为了获得更多稿费才写成这样的。

——dottle

于是打算少打几个回车，本来想的是整篇文章都放到一段的，但发现这样太毒瘤了很不可读，于是又多打了几个回车。

8月20日住进去之后就是颓颓颓颓颓。晚上睡觉，室友比我先睡着，鼾声很大，于是很晚才睡着。

8月21日六点多就醒了，很困，于是继续睡，我觉得要是室友起床吃早饭那应该会发出比较大的动静，会把我吵醒，安心睡就是了。一觉醒来问室友时间，他说已经八点半了，但我看他还躺在床上玩手机，就问是不是该去吃早饭了，他说吃早饭应该是七点左右去，现在应该没饭吃了。我：？？？你是已经吃过了吗？他：我不吃早饭。我突然想起来报道的地方旁边要卖吃的，去看了一圈发现没东西卖了，于是吃午饭前只能喝水充饥。因为发现尽管去年就吃了写不来板子的亏，现在还是不会写任何一种平衡树，也不会写tarjan，于是计划卷卷卷卷卷，但好像过度沉迷于与BH、钟爸一起和学弟茶话会。8月22日仍然在茶话会，茶话会的途中发现除了tarjan和平衡树，我也不会写kdt和求斯特林数，BH问我会不会KM我发现我也不会，于是赶紧回寝室贺了几个板子。

Day1

进场后先读T1，感觉求出现次数大于一半的众数暴力就是扫一遍，维护当前众数以及一个cnt，瞎--cnt或者++cnt一下，大概cnt=0的时候换众数（考完后得知这个叫摩尔投票），这个东西看着就能用个线段树维护，但一时想不起来它具体是啥，于是决定先看T2。读T2时以为是两个人轮流取要先手必胜，于是觉得就是打个表，sg函数应该有什么类似于34位循环节的简单规律，写完T1慢慢找规律就是了。接着读T3，读懂题意后一时没什么靠谱思路，但直觉告诉我乱搞搞应该有巨大多分。我要得200+了.jpg。

这时开考十多分钟了，我开始回去想T1。T1怎么都想不起来摩尔投票的细节，然后发现直接枚举众数是什么再在m个线段树上查一下出现次数是O(\sum m^2\log)的，加个根号分治就是O(n\sqrt n\log)的了，毛估估一下有80分，因为NOID1T1向来数据水，说不定就过了。于是开写，约九点十分写完。然后因为线段树根节点区间设的是l=1,r=n+q而我又用了while(q--)于是调了半个多小时。发现1e5的大样例只用跑几十毫秒后我就没管T1了。然后看T2，打了个表发现完全看不出规律，找规律找着找着突然想到我unrD1T2对着错误结论做了两个小时导致后来时间不够，于是决定先看看打的表能否过样例，幸好这样做了，我发现过不去最小的样例，手动模拟了一下我觉得我的暴力是写对了的，于是回去又读了一遍题，意识到我前面做的全是假的。读对题后我把暴力改对了，终于过了小样例，然后继续对着表找规律，发现还是看不出任何规律。此时考试时间只剩约两个小时，我T2还是没有任何头绪，就去看T3了。又认真读了一遍题后发现链直接猫树就行了，前两个点好像可以换根dp做到O(n^2)-O(1)，接着发现三度化之后都不用换根dp，可以枚举根去直接dp，就去写了。然后一直调不出来，我以为是三度化会对正确性产生影响，就把三度化去了，但还是过不了样例。调了半个小时才发现是我每次新选一个点作为根重新dfs时原来算出的dp值又算了一遍且初值没清空，把算过的dp值直接跳过就能过样例了。这么说我之前有三度化的写法问题也是出在这里，于是狂按Ctrl+Z回退到了之前的版本，果然加个if(vis[id]) return;就过小样例了。然后写了发猫树，发现过不了，调了一万年还是过不了。这时离考试结束只有半个小时了，因为以为T2是大家都会的简单题，于是回去看T2，看了20分钟还是不会，再看T3代码发现我猫树查询的时候写的是C(a[l][dep],a[r][dep])而不是C(a[ql][dep],a[qr][dep])，改了改就过链的样例了。最后十分钟发现T3的dp是O(nd)的，代码稍微改改能过第九个点。下午查分发现果然T1数据把我放过了，T3第9个点不知道挂哪了，可能是常数太大预处理时询问次数超过3e7了吧

期望得分：80+15+25=120

实际得分：100+15+20=135

Day1.5

准备复习Day1前没复习完的板子以及题，结果白天一直复习不动，到了晚上九点半才开始认真复习，最后只敲了个dinic板子，计划的DAG链剖分和边三连通分量板子一个都没写。有一件趣事是我带耳塞听了两个小时歌，听了一个多小时耳机掉了但我还听得到声音才发现一直是外放的；还有一件趣事是随缘复习题目时看到了一道一个月前做的判定树同构题，觉得这玩意儿咋可能考就跳了。

Day2

我看，T1暴力85 那还写个屁的正解 ——dottle

打开题面发现T1叫挑战NPC，吓傻了，以为是FJOI。读到T1第一句话意识到出题人是zyy觉得是毒瘤题就先看T2去了。读完T2还是不会就去看T3去了。读完T3发现更不会就回去看T1了。仔细看了看T1的部分分后发现有过半的点k=0，感觉直接树哈希有很多分，拿个vector记录每棵子树删若干个点可能的哈希值集合，去个重感觉就有80+分了，那还写个屁的正解。然后看T2部分分，暴力和A性质都很简单，B和C应该也不难，加一起有80分，那还写个屁的正解。感觉T3网络流一下应该有好几十分就开始堆暴力了。写T1的时候发现不会树哈希了，就瞎编了一个，反正题面上说的是合理的哈希不会被卡，约九点十分写完（为什么两天都是约九点十分写完T1的80分暴力？），调了调过了，然后因为vector去重要排序，多个log，于是尝试用gp_hash_table或者unordered_map来减少时间，结果它们少个log但慢几倍，于是最后还是用的vector。卡了卡常把最后一个大样例卡进了1s，不知道能不能冲过n\leq 150。然后看T2，考完后听说有些选手特殊性质是先会的O(n^2)甚至O(n^3)，但不知道为什么每个性质我第一个想到的做法就是O(n\log n)的，A性质大概就是按l排序贪心往左放0，最后没填的一段前缀是0，一段后缀是1。然后看B性质，猜它直接贪心是对的，证了证发现贪心确实自动保证了新填的数是递增的，然后发现C不会了，打算先把会的64分写了再说。写着写着发现A性质贪心满足了最小值的限制后可以把B的代码直接粘过来，写起来很舒服。过掉A和B性质的大样例后，发现还是不会C，抱着试一试的心态把B的贪心代码粘C上稍微改了改，发现能过大样例，很离谱。最后一个半小时一直在想T3怎么流，没有意识到k<5可以直接讨论，最后只交了个暴搜。下午查分发现T1没冲过n\leq 150，并且树哈希挂了16分，但T3莫名其妙多搜过了9分。听说我T2的性质C的那个做法就是对的，而且和A的第一步贪心拼起来直接能过掉T2，感觉很震撼

期望得分：80+80+8=168

实际得分：64+80+17=161

三天总分100+135+161=396

总结：要是D2T1树哈希不挂就Au了，不过对于我这个不会D1T1的低水平选手来说这个成绩还行，主要问题是Day2一心只想着拼暴力，T2离正解只有一步之遥，T1说不定我也能想出来；以及手速不够，没时间做D1T2的40分暴力