NOIP 2023 游记

· · 生活·游记

NOIP 2023 游记

赛前：

在机房窝了一整天之后，出校，在外面吃了一顿麻辣烫（理论上来说好像考前不该吃这么辛辣的东西，但是我声称这个麻辣烫并不算辣）。

在酒店摆摆摆，九点半准时睡觉。

酒店的房间莫名很热（兄弟这是11月中旬耶），午夜还醒了一次，差评，感觉不如睡在学校。

赛时：

早上起来感觉精神还行，早餐吃的酒店早餐，还不错。

有点紧张，但是引用撕破伤口丶的一句话：大不了TM就寄呗。瞬间不紧张。

八点准时进校进考点（见到ZJ，寄；见到hfu，赢），顺利进入。考前想睡觉。。。（乐，已经变成生理钟了）

八点半发题，先通看一遍题目，T1，T2 感觉很简单，T3 感觉有点难，T4 好像很难又好像很简单。

T1 不难想到对于当前的字符串应尽量字典序靠前，其他字符串应尽量靠后，可以直接排序。之后需要比较一个字符串与其他字符串的字典序大小，第一眼想到 Trie 树，但是 O(26nm) 感觉很有问题，但我声称能过。

T2 不难想到模拟出最后的情况，由初值等于最终值可以得到若干个等式，形如 x_i=x_j 或者 x_i=\neg x_j 或 x_i=F/T/U 。前两者可以视作 i 到 j 的边权为 0/1 的无向边。最后我们得到一张图，显然若 i 为 U ，则与 i 联通的所有点都必须为 U ；否则都不必为 U 。考虑什么时候必须为 U ，显然当且仅当 x_i=U 或者存在一个权值为 1 的环（此时意味着 x_i=\neg x_i ，显然 x_i 必须为 U ）。然后就做完了，时间复杂度 O(n+m) 。

T3 显然要么 \forall_{i=1}^{10^{100}}x_i<y_i 要么 \forall_{i=1}^{10^{100}}x_i>y_i ，然后如果 x_i 对应 y_{[l_i,r_i]} ，则需要满足对于所有 i ，[l_i,r_i] 与 [l_{i+1},r_{i+1}] 要么不交，要么交于端点一点，且所有 [l_i,r_i] 的并为 [1,m] 。不难想到一个 DP ，设 dp_{i,j} 表示匹配到 x_i 时，能否匹配到 y_j ，有转移 dp_{i,j}=|dp_{i-1,k}(k\leq j\&\&x_i>ymax_{[k,j]}) ，前缀和优化可以简单优化到 O(n^2q) ，有 35pts 。

T4 显然 DP ，设 dp_i 表示第 i 天摆烂的最大能量，初值为 dp_0=0 ，答案为 dp_{n+1} ，有转移 dp_i=max_{j=max(i-k-1,0)}^{i-1}dp_j+j*d+w(j,i)-(i-1)*d ，w(j,i) 表示 j+1 到 i-1 天连续自律回复的能量值。把挑战看做 [x_i-y_i+1,x_i] 的区间权值加 w_i ，则 w(j,i) 为 [j+1,i-1] 的所有子区间权值和。不难想到线段树优化，对于每个挑战在 x_i+1 时将 [0,x_i-y_i] 加上 w_i ，转移即为询问 [max(i-k-1,0),i-1] 的最大值，时间复杂度 O(n\log n)，有 56pts 。

想好了去上个厕所，有点上火（昨天的麻辣烫果然不该吃）。

回来已经过了 2h ，开始实现。

T1 写了 20min，调完发现爆空间了，乐。发现只需要保留其他字符串中最小的那个，复杂度降为 O(nm) ，10min 写完。

T2 写了 20min。

T3 写了 30min。

T4 写了 30min。写完发现只需要直接对所有线段的左右端点和 n+1 转移即可，离散化坐标即可做到 O(m\log m) ，10 min 改完。

此时只剩差不多 30min 了，想了想 T3 的特殊性质想不出来，干脆去检查文件名和 Linux 环境下编译程序了。

出考场一交流，发现都认为今年 NOIP 简单 （CCF不会没钱出题了吧，CSP也这么简单）

赛后：

估分：100+100+35+100=335pts

洛谷：100+100+35+100=335pts

云斗：100+100+25+100=325pts（没开 O2 ）

感觉考得还行(?) ，看来不能放假了，只能继续学了。

（T1 3:0 WBG ，乐，xiaohu 粉难受住了）