NOIP 2021游记
lzqy_
·
·
个人记录
梦醒了。
# 考试
开考后先顺了一遍题，$\text{T1}$ 应该是送的，$\text{T2}$ 应该是个恶心怪异的计数，$\text{T3}$ 数学结论题，$\text{T4}$ 码农数据结构。
### T1
于是先把最可做的 $\text{T1}$ 秒了，这时比赛已经过去 $30$ 分钟。
-----------
又把题目看了一遍。确认了 $\text{T2}$ 的计数是dp，$\text{T3}$ 推了一下方差的式子后确定超出了能力范围，$\text{T4}$ 口胡了一下，大概是对于每个网格维护一个数据结构然后分裂或合并之类的，也超出了能力范畴。
相当于是确定了 $\text{T3,T4}$ 不可做，于是给自己下了死命令要想出 $\text{T2}$。
### T2
样例解释中先确定的 $S=8$ 给了点启发，考虑用数位dp的方式转移 $S$，然后再随便设计几维去掉后效性。于是一个非常正确的方程就出来了：
$f_{i,j,k,u}:$ $a$ 数组中确定前 $i$ 小的数，$S$ 确定了前 $j$ 位，前 $j$ 位有了 $k$ 个 $1$，向 $(j+1)$ 位进了 $u$ 的价值之和。
然后就考虑怎么插入数 $a_x=j$。明明枚举一下插入的 $j$ 的个数就可以用组合数算出方案了，但还一直nt地想着怎么每次插入一个数。
于是就设了非常窒息的一维：已经有 $z$ 个 $a_x=j$。
从此方案数的计算就不可做了。
当时也没细想，感觉好像可行，就无脑码了个大致代码架构，然后做 $\text{T3,T4}$ 暴力去了。
整整花了 $50$ 分钟，比赛已经过去一个半小时了。
-----
### T3
简单推了一下，发现题目的本质就是给出 $a_1$ 与差分数组 $C$，求一个差分数组的排列，使生成的 $A$ 数列的方差最小。
样例告诉我不是递增或递减，然后就放弃找性质了。
随手打了个模拟退火就滚了。用了 $40$ 分钟。
----
### T4
$\text{T2}$ 看上去就难转移的dp让我没有放弃 $\text{T4}$ 的暴力。
不过 $\text{T4}$ 的暴力确实好打，半个多小时打完。
不过等调对大样例后也用了 $60$ 分钟。
后来还有想过优化的方法，但由于性价比都比较低就放弃了。
此时比赛已经过了三个半小时了。
-------
### T2 again
确定 $\text{T1,T3,T4}$ 能拿的分都拿满之后，回头安心调 $\text{T2}$。
但当我设出了窒息的第 $5$ 维，并顺着这个思路来调的时候。一切就结束了。
不想再回忆了。
满脑子都是 $\text{CSP}$ 的 $\text{T2}$，即使不愿重演但也无能为力。
显而易见地，没有调出来。
更窒息的是，由于一直坚信这个dp是正解（也确实是的），甚至没有打一份暴力保底。
摆烂了。
----------
### 总结
出考场了，$\text{CSP}$ 的窒息感又来了。
一直在反思为什么。也许因为码力不够，也许是dp的熟练度还不够——可是还能怎么样呢。尽力了，真的尽力了。
尤其是洛谷自测出 $100+0+56+44=200$ 的时候更崩溃了。明明离翻盘这么近，但就是没翻。
初中的信奥最终还是被画上了不甘心的句号啊…
--------
不过，也真心谢谢每一个在 $\text{NOIP}$ 安慰过，帮助过我的 OIer。真的挺让人暖心和感动的。
即使不甘 也只能高中再战了。希望终有一天能有所回报吧。
这条路会一直走下去的。谢谢你们。