NOIP 2023 游记

· · 个人记录

Before Everything

我的OI生涯，越往后，同行之人越少了。。。

这不，CSP-S 2023 拿了 140pts 卡线省一，然后就来打 NOIp 啦~~~

看了往年的题目，发现 NOIp 比 CSP-S 难不少，就想着是来打酱油的，只是练练手。

比赛前一天

（为啥直接到比赛前一天了呢？因为可恶的期中考试正好在这周的周四周五，然后光忙于复习 whk 了。。。）

好，这天下午 4:30 考完政治，马上滚去济南，到了之后吃了碗拉面，8:30 ，看看板子，然后觉得无聊就切了道区间DP P4170 ，到 10:00 就睡觉了。

比赛开始

大约 7:40 进了历城二中，等了会儿，8:00 进考场，先把缺省源给写上，然后建文件夹，开始等。

顺序开题，先开T1，叫做 $dict$ ，看了题目描述之后有点糊涂，什么 $w_i',t_i,s_i$ 的，就跑去看样例，然后看了样例解释之后才搞懂了题意，就是看一个字符串升序之后的字典序能不能小于其它所有字符串降序之后的字典序，输出 $0$ 或 $1$ 。 看测试点1，既然 $n \le 1$ ，由于 > 对于 $n=1$ 的情况，我们约定：上述性质是自然成立的。 那就直接输出 $1$ ，本次比赛第一个 $10pts$ 到手。然后看测试点2-4，$n \le 26~,~m \le 1$ ，也就是26个字母，稍作推导，得出那就是字典序最小的字母是 $1$ ，其它都是 $0$ ， $40pts$ 到手。 继续思考，其它的就打个 $O(n^2m)$ 的暴力，过掉测试点8，然后继续找性质，看这个数据规模的话是 $O(n^2)$ 的，首先，挨个枚举这个 $n$ 消不掉，然后第二层枚举的 $n$ 好像也消不掉，那就看第3层的比较，经过一番推导，发现只要字符串 $a$ 中存在比字符串 $b$ 字典序小的字符，那就一定有一种方式使得 $a \lt b$ （以字典序比较） ，所以对于每个字符串就只存最大值和最小值就行了，然后注意一下 `<=` ，过样例4，愉快地 AC 啦！ $10:10$ ， $100pts$ 。 开T2。读完题，果断选择去卡特殊性质，看测试点3-4，既然只有赋值语句，那么将初始值设为赋值后的值不就行了，直接统计操作后 $\mathtt{U}$ 的个数就行了，拿下 $20pts$ 。 （然后我看了一眼T3，发现有点难，去上了个厕所，在厕所里突然想起T2还能打个暴力。所以，**厕所是思路的源泉！**） $n \le 10$ ，那就可以暴力枚举所有的可能情况，$\mathtt{dfs}$ 一下，复杂度 $O(3^n \times n)$ ， $n=10$ 大约 $590,490$ ，六百万肯定能跑过，又拿下 $20pts$ 。 忘了时间了 ， $140pts$ 。 开T3，好不容易把题给读懂了，看起来好似很简单，结果一看，没有 $n=m$ ，好吧，不会了。打特殊性质，测试点1 $n,m \le 1$ ，那就是两个字符，如果相等则 $0$ ，否则 $1$ ，$5pts$ 。 测试点2， $n,m \le 2$ ，那就是 $x_1 \lt y_1~,~x_2 \lt y_2$ ，敲完之后想到，如果 $n=1$ 或 $m=1$ 呢？好吧，$n,m \le 6$ 打不了了，把 $n=1,m=2$ 与 $n=2,m=1$ 打完，现在是 $12:20$ ， $150pts$ 。 开T4，读懂题目之后，发现不会qwq。 首先把调试文件都删了，然后挨个代码跑了一遍样例，检查了 n 遍文件名，差不多 $12:45$ ，开摆。 ### 比赛后 没啥，回来之后向老师报备了一下，然后没了。