CSP2023&NOIP2023游记

CSP（10.21）

早上8：30开考，根据以往的经验，去考场去早了也只能白等着，所以这次差不多8：10才进考场（指的是进学校大门），到的时候发现我们机房的几个同学都先走了。

先是普及组，希望拿个400，还是比较有信心的。

J组

8：30开始考试。先看了一下四道题，前三道都是直接看出了思路，T4感觉有点难度，到时候可能会想一下（但是很庆幸最难的题不是模拟，这让我觉得AK的概率提高了很多）。

先看T1，发现就是一个循环，花了几分钟切了（这里就不得不说一下我考试的时候对面是一个xxs，一直不遵守纪律，工作人员也是提醒了几次都不听，生活中有这种人真的令人无法忍受）。

然后看了下T2，T2不知道是不是以前做过，反正就觉得是贪心（每次走向下一个油费比自己小的点），然后随便证明了一下，就开始写了。写完的时候大概是9：20。

T3是一个中等难度模拟，反正就一直写，写了大概20分钟，然后调错又调了个10分钟，这时候差不多是9：50。

最后一道T4，结合数据范围想了一下，发现是一个 \(nk\) 个点的 \(SPFA\)，于是就花了大概30分钟写完了，结果T4并没有想象中的那么难。过完大样例，看了一眼时间，是10：25，还有足足一个半小时。

接着检查了一下四道题，然后看到T2有一个地方可能会挂，就是如果一个点剩的油已经够走到下一个点了，这时候就不用再买了。如果直接用朴素的向上取整的写法会变成 \(1\)，所以得特判一下（估分时好像@X2H_tato和@anr_uli都因为这个挂成了 \(15\) 分）。

检查了四道题，这个时候还有一个小时，然后就玩了一会儿金山打字通（

普及组估分 \(100+100+100+100=400\)，实际得分 \(100+100+100+100=400\)。

中午睡了个午觉，下午继续打提高组，提高组希望拿个300+。

S组

2：30开始，通读了一下四道题，觉得难度比较正常，觉得应该可以有300分。

先看了下T1，T1就是个暴力，直接枚举 \(1-1e5\) 即可。

然后是T2，T2这种可以两两消除的字符串在暑假集训的时候做过类似的，具体可以看QOJ6504 Flower‘s Land 2 题解。做法就是用矩阵，因为矩阵满足结合律但不满足交换律。于是我写了一会儿就写完了。虽然我考场上思路一下就想出来了，但是在第一次做这种题时我是完全没有想到可以用矩阵，所以在我觉得考场上遇到T2肯定是赚了。写完两道题的时候大概过去了40分钟。(考完后发现有一个写法巨简单的 \(\mathcal{O}(26n)\) 的做法，我还在那写我认为很优秀实际上代码又长，常数又大的做法艹)

看了下T3，是个大模拟，就觉得可以先放一下，所以就看了下T4。T4想了十多分钟，想到了是先二分答案，然后题目就转化为了求一个dfn序，使每个点的dfn都不大于一个数。我先是想到了一个贪心做法，感觉比较正确，然后就开始写了。

写了大概30分钟，突然想到有可能一棵子树走一半再去走另一颗子树，所以贪心就被假掉了，然后又去想了一会儿正解，没有想出来。于是就想把T4先放一下，先写T3，写完之后可以用贪心再写一下T4，觉得CCF数据应该很水说不定能多得好多分。

T3想到了用两种结构体分别来表示每一种结构体类型和变量，操作3就依次访问，操作4就递归。然后就一直写写写，最后写+调用了将近2h，弄完之后还剩大概20分钟。

到最后，本来想冲一下T4，但是感觉有一点麻烦，然后就保守一点选择了检查前三题。看到第二题感觉map过不了 \(2e6\)，然后就把矩阵映射到了一个 \(long long\) 上面，于是就能用unordered_map维护了。

全部看完之后还剩十分钟左右，然后就在电脑上到处乱点，甚至乱删了几个注册表（

提高组估分 \(100+100+100+0=300\)，实际得分 \(100+100+100+0=300\)。

总结

这次考试总体来说发挥的不错，仍需加强的还是思维能力，像T4这种想了很久没想出来比较遗憾。还有时间一定要分配好，这次要不是及时发现了T4的思路假了，估计还要写一会儿，到时候可能T3都写不出来了。

值得一提的是，这次比赛想试一下全程用Linux写，最后发现效果还挺好 （比垃圾Dev好多了）。

第二天知道了S组T2居然是原题，CCF你是真nb啊！

\(\texttt{Updated on 10.29}\)：出成绩了，最后T2居然不会因为没写那个特判挂分？？？CCF数据是拿脚造的实锤了！

NOIP（11.18）

这次的考点在七中高新，和考CSP的时候差不多，也是卡点进的考场。

8：30准时发的密码。先花1分钟扫了一下四道题，发现T1是个签到题，然后就先开始写了。做法就是求出每个字符串能弄出来的最小和最大的字典序，然后比较一下就行了，写T1大概花了30min。

接着仔细地读了一下剩下的三道题，题意都还是比较易懂的，然后就决定先开始想T2。T2可以先模拟每次赋值，最后每个变量要么等于一个确定的值，要么等于另一个变量的初值（或初值取反的值）。然后就可以用并查集维护，如果是 \(a_i=a_j\) 就将 \(i\) 和 \(j\) 合并，如果是 \(a_i=\neg a_j\) 就将 \(i\) 和 \(j\) 看成敌人，有点类似于关押罪犯的做法。最后如果有两个敌人在一个并查集里，或者并查集中某一个是 \(U\)，那么这个并查集就一定全是 \(U\)，所有的这种 \(siz\) 加起来就行了。想+写完T2大概是10：30。

然后看了一眼T3，想到了很明显的35分暴力，接着想优化。当时也不知道怎么想的，我把它看成一个01矩阵，\((i,j) = a_i>b_j\)，然后看能不能从 \((1,1)\) 走到 \((n,m)\)，做法是对的，但是很难优化（我也不知道我当时是脑子抽了还是啥，能想出这个思路）。于是我就一直想了30min，然后放弃了，准备去想T4。

T4也是立马想出了36分 \(\mathcal{O}(n^2)\) 的做法，但是我是二维dp，\(f[i][j]\) 表示现在是第 \(i\) 天，已经连续跑了 \(j\) 天的最高能量值，而不是用 \(f[i]\) 表示第 \(i\) 天不跑的最大值。然后就跟T3一样，一直想优化。最后到11：30，决定先把两个暴力写了再说。

然后就写了30min的暴力，写完后又检查了一下T1T2，最后感觉想不出来了，就摆了一会儿（

出了考场后，发现机房人均300+，大家一致认为今年NOIP比去年简单。最后一道题就是个线段树优化dp的板子，T3也有很简单的75分暴力，所以300分应该是比较好拿的。

NOIP估分：\(100+100+35+36=271\)

实际：\(100+100+35+44=279\)

upd on 11.27：T4部分分把全部贡献大于0的加起来，居然得了8分？？

这是我初中生涯最后的一次NOIP，感觉发挥的不是很好。现在正在全力以赴备战省选，希望能拿个好成绩吧！

最后，如果有想看代码的点这里。