NOIP 游记

前情提要：color 100\to 0，arena 92/100\to 36。

最后一场模拟赛喜提 0+0+100+0，挺乐的。

Day 0

晚上九点睡，然而还是很早就醒了，但是时间体量巨大所以还是不困。

Day 1

早上去高新吃早饭。吃兵哥豌豆面，故意吃某个不辣的面，但是完全不如豌杂面等！！

买了瓶东鹏特饮，带了一点 sugar 和一个能量巧克力（这个没吃）就进去了。门口 lxs 说要细心。

进入考场又可以提前写板子/qd。写了个线段树 3 和网络流，然后看题。背后是 cwfxlh（但是他应该不认识我）和 hwy，预备开始窥屏（没有执行）。

翻了一遍没有构造，两个计数，先小乐一下。

T1 一看连续段可以任意排列，然后肯定是确定跟确定匹配，其次是只有一个不确定的匹配，否则可以交换调优，最后再都不确定匹配。15 分钟时通过了大洋里。

T2 义眼动态 dp，又具体写了一下，发现好像直接乘起来贡献即可。不知道为什么写到了九点半，因为发现 v^{n-1} 执行次数很多就记录了一下（note here）。

T3 看了看好像是生成树计数？？这跟关键边有关系吗？？

瞪了一会之后发现好像无向图 dfs 树不能有横叉边，然后一个点的团那个完全图就是只能是一条链，链头是出发点或者连过来的点。好像把这个结构拼接起来就可以了！看看去重问题，莫名联想到 PE 的一道题？？（虽然好像没啥关系）。然后我想想一个怎么 dp，设 h_i 为 i 从父亲下来的子树方案数，这个直接先递推；设 f_i 为 i 算上父亲边子树里面的方案数，还需要再设 g_i 为 f 和 h 交大小。然后转移去重就大概是考虑链头是这个儿子，链尾是前面的某个儿子减去掉就可以了，前缀和优化后为 O(n\log n)。

最终调了一会之后在 11:00 通过了所有大洋里。去上个厕所（当然前面还有很多次），回来的时候看了一眼发现 hwy 已经开始写线段树（显然是 T4），感觉 T3 和 CSP T3 一样应该都是大众过了，有点震撼？？

T4 义眼 64，然后想想想不会。11:30 开始在注释里开香槟（note here）（我是什么傻逼？？），11:40 决定开始写暴力。发现胡的链假了。

这个时候稳一手，检查一下前面的题，突然感觉 T2 有问题（什么 byd 直觉），发现 T2 过不了样例 2？？查看一下那个傻逼优化（note）挂了，修改一下。

然后想了一下好像整体二分维护连续段可以做链的 2log，遂在 12:25 开冲，由于 DS 调试水平确实南平没有调过（为什么我会中场开香槟？？）（前情提要：模拟赛 DS 没调出来率或可达 \frac 14）。

12:57 发现 T4 交的玩意注释了文件输入输出，紧急改动。

跟同学交流，过 T3 的人很少？？hwy 写了 T4 的 2log，其他人好像也不会 T4。洛谷上好像过了逸车 T4。

回家的车上突然发现 T4 的整体二分改动一下变成 dfn 就是两个 log 的 [80,100]？？！考场上很傻逼，不过鉴于没调出来也没有什么可说的。

所以最后的期望是 100+100+100+32=332。

正确的策略应该是 T2 做快一点，T4 麻溜一点。

回顾突然发现 T4 n>5000 是先判的链，然后链最终是什么也不做！！在 R-L+1=K 放个链就死了。但是发现没有多测和 sub，应该就是不会多放一点，乐乐楽

T3 没似，100+95+100+32