NOIP2022游记

2022.11.26

6：30

前一天晚上10点看着象棋分解就神奇的睡着了（
虽然晚上睡得不安稳，但是总归获得了难得充足的睡眠。
洗漱，吃了放在房间门口的早餐，就该集合了。

7：10

被领着到酒店考点，在门口排队做核酸。
趁机做了几道天天象棋上的残局，感觉自己状态良好。

8：20

总算让试了一下机（我寻思你10min能试出什么错误啊，给这么点时间试机）
敲了个A+B problem 就草草了事了。

8：30

坐了快半小时总算开始了。
考试时间8：30-13：00

开题。
快速扫了一遍四道题。t1题面太长，看样例应该是一道模拟；t2一眼看到排列，又看到数据 \(T\) 组 \(m\) 之和 \(S\) 取 \(2e6\) ，应该是数论题；t3好像有点tarjan缩点的感觉，就没有细看了；t4统计区间 \([l,r]\) ，看起来能用线段树拿暴力分。
此时8：35，开始着手想t1。
给定一张 \(n*m\) 的01图，分别求在图中取部分点使得图案为C，F的情况数，\(n<=3000,m<=3000\) 。首先想到C和F的方案统计应该是有相似性的，可以一起求解。接着想到预处理每一行的0，并存储，接着枚举每一列来统计。
题面挺长的，看完+想完初步解法就已经8：50了。
然后就开始想怎么统计了。首先在纸上画了C和F的图案，左边的竖是相同的，唯一的区别在于横。
已知有 \(m\) 条横线，长度为 \(n_{1},n_{2},n_{3}...n_{m}\) ，挑选其中两条，其中F还需要确定竖线应该选到何处，C，F如何统计便呼之欲出了。
想出具体解法，此时9：10。
花了半个小时左右把方法实现了，此时9：40多一些，相比去年t1一道题卡了我3小时，今年的速度明显高了不少。我还有3.5h+来思考后面的题。
我再次更细一些地读了后面三道题。t2还是感觉是一道玄学题，还是先放一放。
我的注意力集中到t3。n个点，m条无向边，讨论点取不取，取了的点必须保证相连通，求可能的方案总数。思路几乎一蹴而就：tarjan处理完割边，然后树形dp统计。如此简单地想到思路，我激动的心情难以表述。
此时9：50。
但是很快，我就发现我不知道tarjan算法怎么处理割边。几个星期前我就一道题与同学们聊到过tarjan处理割边，但没有自己实现过。我犹如被泼了一盆凉水。
我仔细回想了10min，并尝试自己根据tarjan算法求缩点推出来如何处理割边，但很快就放弃了。
此时10：05。
看了看部分分，可以用暴力做的 \(n<=3000,m<=5000\) 部分仅45分。但是希望还是出现了，我发现 \(n<=5\times10^{5},m<=1\times10^{6}\) 的特殊性质 \(m=n\) 和 \(m=n-1\) 可以以 \(O(n)\) 复杂度解决。而这样不需要tarjan算法的暴力分达到了80分。
于是我分类讨论地处理了80分的判定割边环节，此处暴力的码量很大，写完+debug完已经11：00出头了。我按照预想的方案开始写树形dp环节。
然后在实现过程中，我才发现问题接连不断。首先dp过程中就遇到了问题。我声明了数组dp[i][0]表示以第 \(i\) 点为根，子树中没有设立军营，即没有取到的点的方案数，dp[i][1]表示以第 \(i\) 点为根，子树中有取到的点的方案数。但是状态转移方程 \(dp[u][1]*=(dp[v][1]+2*dp[v][0])\)， \(dp[u][0]*=dp[v][0]*2\) 似乎并不能涵盖所有的情况。其次根节点不取点不一定不能乘2。最后割掉的边是否应该派兵驻守也没有统计。
此时11：40。
时间已经不充裕了。我尝试解决这些问题。割掉的边似乎对于问题的解答并不影响，只需要最后全部乘以2即可；根节点不取点可以最后控制根节点的所有子节点只有一个是子树取了点的来统计；这样dp转移方程也合理起来了。我快速地将这些实现。此时12：00，距离比赛结束仅剩1h。
但是，将样例复制过去，却总是与正确答案有所偏差。我不断地调改，时间一分一秒地过去。然而遗憾的是，尝试多种改法之后仍然输出的不是正确的答案。
此时12：20。
我只能决定，停止修改这道题。
我再次浏览了一下t2，t4。花了5分钟思索了一下t2，我认为这样一道题在时间紧迫的情况下很难得分，便转头把t4的线段树暴力分写了。此时已经12：40了。
老师已经开始说明提交方法了，考场也开始躁动。我最后思考了一会t3，这是我NOIP的句号，也几乎是我OI生涯的句号。
12：50，距离考试结束10分钟。
我给t1,t4,t3加了文件读入读写和return 0，最后检查一遍，便草草提交了。
考试结束。

26日下午，宾馆

如果t3的80分写出来，再加上t4的暴力分，是一个很不错的成绩，应该能拿到全省前几的名次。我宁愿当时t3根本看不见希望而转头写t2。但是谁又知道那会怎么样呢，说不定那样出考场的时候我就会想宁愿不去写t2而去写t3。不管如何，4年的OI生涯告一段落了，这是一段美好的回忆。

预测得分：100+12+0+0=112

希望t1别再挂分了。