NOI2021游记

· · 个人记录

7月20日到宁波，然后住了几天酒店，打了一两场模拟赛。Day-1住进寝室后，和室友边颓边卷，随便背了下笔试，Day0就满分了。

Day0.5

上午补了点去年CSP/NOIP的题，然后下午同寝室的都在复习，只有我在预习。我考虑到去年时代的眼泪靠莫队可以拿高分，又听说lxl在浙江，我就先学了下莫队和回滚莫队。然后晚上发现字符串啥都不会，就背了下SAM模板，想学PAM但是没来得及学就睡了。睡前看了一下网络流和组合恒等式。

Day1

根据前两年，盲猜D1T1是DP，D1T2大概率是DP。结果呢？D1T1数据结构，D1T2计数，D1T3图论。

抱着T1必然签到的想法，想着先搞个70分暴力，再优化成正解。70分暴力很naive：对于每次修改将链上每个点颜色染成++color，再将链上每条边的颜色染成++color，判断一条边是否是重边相当于比较边的颜色和两端点的颜色大小。写了一个多小时，然后犯了大概好几十个（也许一百多个）傻逼错误，弄到将近十二点才通过前面的样例。这时我大概想到了优化成100分的方法，但写不动了。

然后开T2，第一眼：路径不交，猜手结论，是裸的LGV引理（早上才复习了），那把邻接矩阵乘起来求det不就可以了。第二眼：偶数方案-奇数方案，哦不会了。然后以为是dp。后来想了一下k=2发现考虑左边的i号点连向右边的p_i号点，对答案的贡献的的系数是sign(p)，就是邻接矩阵的行列式。又发现性质A就是做k-1次k=2，写完这一档就跑了。并且可能考场上我突然精神错乱认为det(A)det(B)=det(AB)是个假的离谱的结论，就坚信把邻接矩阵乘起来求det是错的。

出来听同学说从第一层的i号点到第k层的p_i号点，从第一层的j号点到第k层的p_j号点，若满足i<j,p_i>p_j，那么显然从i到p_i的路径和从j到p_j的路径一定有奇数个交点，那么只需要像k=2一样做，把A_{i,j}设成从第一层的i号点到第k层的j号点的方案数即可（注意其实偶数个交点和奇数个交点的方案都会多算，比如u->mid->p_u和v->mid->p_v经过了重复的点，但是考虑把它们变成u->mid->p_v和v->mid->p_u这种方案会使得交叉点数量加或减1，那么这两种多算的情况一种对应偶一种对应奇，相互抵消）

开T3时发现写不来tarjan了，尝试自己瞎编一个缩点，然后挂了，最后树的部分分来不及写了。

期望得分：70+75+0=145 实际得分：80+75+20=175

Day1.5

决定改一下昨天T3，结果颓了一天，一天啥都没干，连T3都没调出来。

Day2

浏览了一遍题，都没思路。根据Day1的经验，坚信T1最简单。然后想了2个小时T1（中途大概有半个多小时在发呆）还是没任何想法，最后T1裸暴力走人。然后想了一下，T2要是推式子，我肯定不会，于是手算了W和E个数比较小的情况。幸运的是当时我想着每次有两种操作，写成树的形式比较方便，然后写完了之后发现就是混凝土数学97页的Stern-Brocot Tree，W就是往左走，E就是往右走，直接用第100页的结论，写个文艺平衡树，就能过了。你让我一个连tarjan都不会的选手写平衡树？因为不会平衡树，所以写了个线段树就跑了。T3想了一会儿，没考虑到要算重，以为是简单题，后来发现要容斥，但这时时间已经不够写容斥了，写了个裸暴力就跑了。出成绩后发现暴力挂了

期望得分：20+70+12=102 实际得分：24+70+8=102

最后：100+80+75+20+24+70+8=377，于是后排Ag了。

总结：两天的T1和T3分数都是全校倒数第一，靠着T2混了个Ag ，所以以后要多做T1和T3，少做T2