NOIP 游寄

大抵是最后一次了。

Day -2

牢 N 给了 7 道题，有的口了有的做了，总之差不多全切了，感觉比较稳，遂摆烂。

说下那个树的覆盖那道题，关键点在于点边容斥，就是连通块个数等于点数减去边数：

V-E=cnt

然后你注意到改变一条边只会改变该点出现的位置，所以做完了。

Day -1

睡到自然醒，然后窝在家里摆烂。

下午 4:00 左右出发去淄博，发现那边的宾馆十分高科技，前台无人，自主登记然后办理入住，往你手机里发一个房间密码，然后进驻。房间非常的日式风格啊，感觉跟来了日本似的。

晚上吃的牛肉面，还行，觉得偶遇了 LJL，但是不确定。

吃完晚饭后去学校试机。19:10 左右到达信息楼，在楼下跟 LLR，CYF，WLY 唱了《芳园何青青》，引来无数人的目光。进考场试机比较顺利，10min 搓出来了线段树板子和 Dijkstra 板子，感觉还不错。

回宾馆，家父身体不适，家母出去买药，希望身体没事。

Day 0

凌晨被吵醒了一次，家父吐了，后入睡。

早上不是很有精神，忘记吃了啥了，反正直奔考场。

发大样例，发考试题，开始考试。开题，看 T1，并没有一眼秒，不懂，按照往年的经验 T1 都是送分的，不知道为啥没思路。看 T2，觉得非常可做，虽然是数数题，但是感觉做题思路直接就是硬算然后乘法原理。看 T3，觉得不可做。看 T4，发现是数据结构题，暴力分应该可拿。

回来切 T1，感觉很 dp，但是就是不会设状态，遂写了一个看起来就很假的贪心，简单地说就是按两个 t 串 0 的位置分隔开，然后统计两个串 0 和 1 的个数，每到一个隔断就对答案加上两串 0 的个数取 \min 和两串 1 的个数取 \min，然后清空计数。打完后立刻把自己 hack 了，此时时间过去 30min，我的期望得分 0，爆炸了，但是注意到 T1 有 60pts 奶龙分可拿，于是转头先去打 T2。

切 T2 时的思路就很顺，注意到我们可以把每个位置的情况分类讨论一下。假设这个位置没有一元限制，则情况数为 v^2；如果这个位置有一元限制且下一位也有一元限制，则情况数为 v\cdot (v-1)+1；如果这个位置有一元限制，与下一个一元限制之间间隔了 len 个位置，那么我们需要简单讨论一下：

• 这个位置的 a\not =d：只有 a 有 v-1 种取值，剩下的随便取，有 (v-1)\cdot v^{2len+1} 种情况。

• 这个位置的 a=d：你需要计算影响会传递到多远，有一个求和式：

  \sum_{i=1}^{len-1}v^i\cdot(v-1)\cdot v^{2d-2i+1}+v^{len}

  发现求和式是等比数列，化简可得：

  v^{len+1}\cdot (v^{len}-1)+v^{len}

你注意到这一坨东西只需要在一元限制的位置上计算，最后乘法原理即可，所有的幂运算直接快速幂，你在 O(Tn\log n) 的时间复杂度下解决了该问题。对于无解的情况，直接判断有没有一元限制冲突即可。打完调了调，过了大样例，此时大概 2h。

回去看 T1，还是不会，把 20pts 爆搜和 20pts 特殊性质 A 做了，去拼 T3 暴力。

事实证明 T3 是不可做题，我打了个阶乘复杂度的爆搜，然后注意到特殊性质 A 全输出 1 能拿 4pts，赶紧打上。想了想特殊性质 B，觉得就是阶乘然后容斥一下，推了个式子是：

(n-1)!-\frac{k(k-1)}{2}(n-2)!

打了，没过大样例，遂摆烂，回归 T1。

还是不会 T1，把 20pts 的特殊性质 B 打了，去拼 T4 暴力。

T4 的 O(n^3) 做法显然且好打，参照温水佳树与圣诞树，赶紧先打了。后面又想了想，觉得特殊性质 A 不可做，特殊性质 B 好像直接把 \text{LCA} 丢到线段树上就可以了，时间复杂度是 O(n\log n) ~ O(n\log^2n)？但是我仔细抉择了一下，此时 3h，12pts 的暴力与 40pts 的正解显然后者更有吸引力，我果断选择冲 T1 正解，事实证明这是我这次 noip 做的最正确的选择。

回归 T1，选择返璞归真，仔细想想最开始的贪心为啥假了，原因很容易思考，因为顾头不顾腚，如果段不同时结束，那么还有一些能用的没用，不用浪费，所以寄了，考虑要把没用的那些也用上。于是重构代码，贪心思路不变，只不过到整段时停止，然后用长度长的那一段去匹配长度短的那一段。打完，没过大样例！没过大样例！没过大样例！寄了，急了，不知道为啥，死死瞪住代码。恍然大悟！不能只匹配能匹配的，不能匹配的也需要减去，加上，过大样例了！然而我完全无法证明做法的正确性！还剩 30min。

冲 T4 特殊性质 B，线段树启动！还剩 15min，打完发现没过样例！输出了个 313？？？再瞪！！！我草我输出成节点编号了，改成深度就过了！此时正好收卷。

最后检查一遍文件，发现 T1 的 freopen 里写成 edit2.in 了，赶紧改了，蓟县。

最终期望得分：[60,100]+100+[4,16]+[8,20]=[172,236]。

出考场，问别人做得怎么样，发现全世界除了我全会 T1，退役了。

中午没吃东西，刷一下午 B 站，玩崩铁。

晚上发现 T2 自测数据出了，打了一下，没挂分。

家父大抵是真病了，上吐下泻，精神不振，还伴有低烧。

Day 1

没心情玩了，回济南。

在车上就觉得有些不舒服，回到家里吐了。一下午跟家父症状一样，上吐下泻伴随低烧。

Day 2

在家养病。突然意识到我 T4 的时间复杂度假了，在向上合并的时候我没有倍增跳，而是暴力跳的，这下彻底废了，T4 期望分数变成了 8pts。

打了 T1 的自测，民间数据过了。

Day INF

出分了：100+95+4+20=219

T3 果然挂没了，但是 T4 拿满了？？？而且 T2 95pts？？？

晚上和 LXH 交流，他帮我捉出了 T2 的 bug，我跳出循环跳早了，导致一元限制在 n 处冲突时会挂，无敌了。

明年难说，这个唐诗分数上不上下不下的，当然省一稳了，不过估计最后一年了，回归 whk。

鲜花

回顾我这一年的 OI 经历，好像也挺充实的。自初中以来，我学 OI 一直都没有朋友，一直独来独往的。SY 给了我开阔眼界的机会，我也认识了许多志同道合的人。细数一下，这一年我认识了 WLY、LLR、ZZM、CSY、QRZ、NXQ、LMZ、CYH、CYF、GYY、ZYQ、WSR、ZHR、WZY、SJB、ZCL、LJL、JJL、TCW 这些朋友，我们在机房里共同度过了一整个春秋冬夏。

我喜欢晚自习的信竞合唱团，喜欢在往灯上扔气球，喜欢飞牌，喜欢打斗地主，喜欢崩铁启动。信竞的生活真的很有趣，我大概这辈子都忘不了信竞吧。

“我们重复着这样一时的牵绊，”

“抓住了却又放开，就这样生活下去”

“这虽然很寂寞，但也不全是悲伤的故事。”

学一辈子信竞！