CSP-S2025+NOIP2025游记

· · 生活·游记

省流：CSP-S 100+100+25+20=245，NOIP 100+48+0+0=148。

CSP-S

T1，先不管 n/2 人的限制，发现贪心就可以。于是自然地想到超过限制时贪心取损失最小的。25min过所有大样例。
T2，第一反应 O(2^k(m+nk)log(m+nk))，明显过不了。然后发现只需要考虑原图最小生成树，就没有 m 了，但还是过不了。为了干掉log还费了一些工夫，代码2.7KB（怎么同学的都比我短一半）。本地大样例0.4秒，没咋想就交上去了（赛后听说大样例n只有1000，搞不好要TLE80了）。这时候是2小时出头。
T3，一眼看出要找到最左和最右不同的字符位置（中间一段可以用map维护），然后就变成了左边要是后缀，右边要是前缀。到这里不会了（改成一边我是会的，Trie树）。于是只好去想特殊性质。最终是在结束前五分钟打了个 O(nq) 的哈希，性质B就是把二元前缀改成了整数比大小，一维枚举一维树状数组即可，但没空写了。
T4，一看就是dp，但没有一点思路。就随便写了个状态设计发现是状压，就写了20pts。然后发现m=n很简单，又打了4pts。打完是3h出头。
（做题顺序：T1->T2->T3思路->T4思路->T4代码->T3代码）
估分：100+[80,100]+50+24=[254,274] 。今年ABC都比去年难。
upd on 11.6：出分，100+100+25+20=245，CD都挂了。T3判前缀只用了哈希没判长度，T4数组开小没过 m=n 。

两场考试之间的一些事
AC 扫描线（二维数点），左偏树，数位dp模板
VP远古EDU，只过了四个，E赛后过，F11.??补题
11.??补完CSP-S2025 T3T4
11.15 VP NOIP2020，(100->60)+84+(70->40)+40=224，挂分惨重（怎么在当年还能排那么靠前），T1有些地方忘开int128（应该define），T3没算清楚少写一个优化导致被卡爆。
CSPS炸29，NOIP2020炸70，真的应该注意代码细节，写代码时要用失误率最低的方式（被卡常少十几分，WA就不知道少多少了）
之后信息学上课，讲了些知识点，达成AC500&蓝紫黑100。
洛谷竟然出了模板题集合和NOIP模板题比赛，真好。
11.26 VP NOIP2021，100+（50或65->35）+12+（44->12），差点炸出省一。T2一眼状态设计，差一点就是正解了，然而把自己的思路否定了，写了个状压，因为数组开小（认为2^12=2048）WA三个点。T3不知道为啥没看出来差分。T4一眼32pts bfs，然后想用离线并查集写44pts，代码量超乎想象（4K），写加调两个小时，而且7-8忘了特判导致复杂度挂掉，最终莫名其妙只过了19-21。9-11还会线段树二分，也没空写了。T3但凡看出来差分任意顺序也不至于只有12。
VP NOIP2021 赛后反思：在思维上追求极致，可以冲高分；代码上避免一道题消耗过多时间，优先做性价比高的部分分或正解。11.27写了一些模板和一些绿蓝题。

NOIP

结束前5分钟不要写新代码。记住了，用T4 40分换的教训。
T1一看数据范围一眼贪心，想了一会就会了。写代码。直接开着文件读写测样例。1-5过了，6输出82。思考了一下发现有两点错误（1.大于两个最小值就直接不考虑；2.反悔可能使答案加0/1/2，都要判），改好，七个样例都过了。35min。
开始想T2。发现不对的话一定是一个2卡着买不起得闲，并且前后的1权值和比它小（然而这是错误的，也有可能后面没有1，我因为这个错误在B性质输出2^n。然后会了n^4，会了所有特殊性质（其中B是假的）76分。继续想正解，失败。
三题一起想。T4一开始看错题把全局查询当单点查询，以为自己切了，发现不对。先会A性质（单调队列）（10pts），然后自然的会了qn^2（15pts）和B性质n*32^2（15pts），40分。看T3，一开始把m=2当成菊花图，一眼秒了，发现不对。然后发现m=2是简单的（考虑每个结点是贡献给自己还是祖先），8pts。由此想到了一个四次方还是五次方的dp[u][i][j]：u点子树MEX为i，有j个结点权值小于i的答案。32pts。T3也会了40分。2小时。去厕所。之后想了半小时T2正解和其它部分分，没有成果。
剩2h，开写T2。半小时写完。调了四次方和m=2（输出2^n就不用调了），还剩55分钟，发现m=2n-2也挂了，5分钟没调出来。考虑到只有4分决定放弃。写T4，因为unsigned问题卡了一会，还算了下空间，应该卡过了（静态不到但接近500MiB）。剩5-10min的时候奇迹般地调过了，交。
然后检查了一下文件读写、long long之类的问题。发现OK之后开始写T3的m=2（代码很短，8pts）。非常糟糕地，这几分钟内写完了。然后提交（交到了T4但没发现），再检查，发现输出比答案小1，改好（但没复制）到回收系统，发现还剩10秒，下意识地点开T4尝试复制修改再交，没交上去。结束之后才发现把T3代码交到了T4。
出考场后发现大家分都不高。我误以为性质B答案是2^n，同学和洛谷指出不对后发现前面说的那个bug（但明明调四次方的时候遇到过并解决过）
如果把后三题当成4小时的NOI，这个发挥极其糟糕。
估分：100+52+0+0=152，希望能上省一。
对省选也不抱太多的期望，尽力准备和正常发挥就好。
upd：出分，100+48+0+0，下位省一。
一些反思（自己写了一堆然后删成了100多字）：
正式考试（特别是有部分分/OI赛制），不是要追求会的“理论”分数多高，抓到多少只鸭子，考完再抱怨挂了xx分，没吃到嘴多少，
而是要把自己能力范围内的稳稳拿到，“生的鸭子”（思路）快速“煮熟“（写代码调好），“煮熟的鸭子”（完成的代码）无论如何不要在嘴边飞走。