NOIP 2023 游记

· · 个人记录

考前一天模拟赛卡死 \rm T2 完全没有信心地睡了 10 个小时在床上翻来覆去想没考好就干脆退役吧。

准备了大量水与大量草稿纸，换身衣服，剪指甲，只是为了调整心态。

$8:30$ 扫一眼 $4$ 个题，留个印象。$\rm T4$ 一眼 $\rm DP$，$\rm T2T3$ 两个神秘。 $8:35$ 开 $\rm T1$，发现只有最小值最大值有用，想了想还要记最大值的次小值，$9:00$ 过大样例。 $9:00$ 开 $\rm T2$，发现每个变量只需记录最后赋值。然后设计了本质不同的状态，初值，真值，其它变量的正反，然后想了想，前两种随便搞，后面那种建边不是一堆链吗，于是写写写，$\rm 30min$ 后发现第一个样例不对，吸一口冷气。 哦原来是可以有环的啊，当时脑子一抽以为只会有自环，判掉之后过了第一个样例，第二个过不去了，吸一口冷气。 样例不大直接手模，发现是棵基环树。心里一慌开始重构，各种什么内向基环树的东西全扔上去了，大概是 $\rm 10:15$ 写完，怎么还是过不去第二个样例。哦原来环的正确性不是环长而是 $-1$ 的个数，然后直接把第三个大样例冲过去了，结果第四个大样例凉凉。 当时真的慌了，心想正式赛没切过 $\rm T2$ 可太丑陋了，之后 $\rm 30min$ 各种乱调，甚至把第四个大样例的单组数据整出来放到一个单独的文件里。然后一看，基环树找环写错了。于是改改改，改到 $11:00$ 发现第二、三个样例都过不去了，突然想到还有内向树，然后又改改改，加特判，$11:15$ 重新过第二个样例，突然又发现建边写错了，终于把 $4$ 个大样例都过了。 $\rm 11:30$ 心里慌得很，看 $\rm T3$ 一时间没头绪，直奔 $\rm T4$ 找部分分。发现好像 $28$ 分是白送，一想好像随便整个后缀和就有 $\rm 36$ 分，立刻开写，结果变量名写错调不出来，上个厕所回来才发现错误，此时 $\rm 11:50$。过了第 $3$ 个大样例，发现 $52$ 分好像是个裸的 $\rm DS$ 优化 $\rm DP$，想想 $\rm T3$ 还没写，立刻放弃。 $12:00$ 翻到第一页看时限突然发现 $\rm T1$ 有 $n=1$，一测果然错了，立刻改，然后随手测了一组 $n=2$ 又错了。猛地发现自己的次小值当且仅当最小值更新才会跟着更新，吓出一身冷汗，$\rm 5 min$ 补完，立刻回去看 $\rm T3$。 $12:10$ 开始想 $\rm T3$，过了 $10$ 分钟发现等价于存在某种双指针移动过程使得全程单调，开始贪，发现似乎大指针越大越好，小指针求出能够移到的最右边界，移动到区间中最小值最优。心想这个东西不是可以二分 $\rm ST$ 表秒了吗，一阵狂喜但是感觉完全没时间调求稳。开始打单次询问复杂度神秘的暴力，发现这个玩意好像假了，此时 $12:40$，立刻胡了个 $O(nmq)$ 的可行性 $\rm DP$，$12:50$ 过了第三个大样例。 最后 $10$ 分钟检查加开摆，只要不像之前的正式赛烂完就好。 预计分数 $100+100+35+36=271$。发现 $\rm T2$ 很多人都没写基环树，心里很慌，但是洛谷，小图灵，云斗都过了，估计是稳了。 希望还能继续走下去。