NOIP 游记

· · 生活·游记

今年初三，是第二年参加 NOIP，其实和学弟参加的次数差不多。

初三这个年级也是，向前看去感觉也没有学多长时间，向后看去却又感觉即将结束，可能整个竞赛五六年的生涯就是如此短暂。并且中考也在即，竞赛和文化课的协调也比较困难。

今年 CCF 在 CSP 整了不少花活，我也在 S 组拿到了 300 pts 的得分。NOIP 前做了好几天噩梦，都在梦到自己因为各种原因挂分，直接无缘 E 队。

解压密码发下来，打开 PDF 刚好 8:30，开始看 T1。T1 给人的初始印象更像是 dp，于是我就开始推式子，不断乱猜转移方程，发现不管怎么转移都完全不可做。30 分钟后，我的心态已经开始有一点小崩，我于是选择先将贪心写出来，并判断哪里不对后改成 dp。花了 15 分钟，打完贪心直接运行大样例发现过了，仔细思考后发现这个贪心思路越想越对，直接保存文件后就去搞 T2 了。

T2 本来想正难则反，然后发现自己唐了，直接把各部分的答案乘起来就完事了。但是题目中保证存在一种方式使得满足所有限制这句话和样例矛盾了，想了 5 分钟后还是写了特判。

到了 T3，想了半天想出来一个在完全图里选链的思路，于是暴力判断每一个点有多少条可行链并乘起来，发现过不了大样例，发现是不同的可行链对应的可行根不同。于是开始想容斥，没过脑子胡了个结论：任何可行链组成的可行情况最多只存在两个根，自己还觉得特别对。然后树形 dp 就调了很久。发现只能够通过前 4 个大样例，随手输入了条链进去发现竟然输出 0。仔细查过程发现按着自己的思路这个输出是对的，突然发现自己假了，时间只剩下一个小时。我开始纠结要不要转战 T4，但是觉得写两个小时一分没拿会很蠢，于是又回去推结论。首先发现一种可行情况可以对应多个可行根，但前提是这些可行根在一条链上。固定了两端的两条关键边之后，发现只要中间有关键边，那么贡献就会抵消，也就是说只有两条中间没有关键边的关键边才会对容斥产生贡献。我认为这是重要的结论，于是重新开始打树形 dp（因为我发现原做法假了时直接气到把代码删了），终于在 20 分钟后通过了所有大样例。

T4 因为时间紧张，完全没有认真去想，于是匆匆拿了 20 分跑路，连性质 B 可以用 ST 表做都没发现。（但特殊性质 A 的大样例跑得超级快，有没有可能因为数据过水被放过呢？）

估分 100+100+100+[20,36]=[320,336]。

高二的学长都预备退役，留下了一些很伤感的文章，作为已经见证过六届同学退役的人，我的心依旧很感伤。同时学长们留下的差点挂分的经历让我再次开始害怕自己挂分。

祝自己不挂分，祝学长前途光明。