NOIP 2023 游记

· · 个人记录

Day 0

体育课真的是类似了。800\operatorname m 跑了 3:53。

Day 1

早上七点起来，吃完早餐，奔赴广大附中。

CSP 考完就没再停课。班上只剩下我一个信息组的在上文化课。感觉这次考试要寄。

八点钟进了考场。

这考生须知，，没新意。

看 A。哦哦哦，任意次交换，那不就是重排整个序列。 那不就是这个字符串正序，其它字符串反序吗。 哦哦哦，切了。 嗯？RE 了？ 哦，`freopen("dict.in","w",stdin);` 差点 $-100$ 了。。。 诶诶诶，不要 `sort`，不要带 $\log$。换桶排，好了。 看 B。啥？只有非运算？ 那不就是 2-SAT。会 tarjan 就行$_\textsf{伏笔 1}$。 上个厕所，开打！ 打完 tarjan，发现自己好像做麻烦了$_\textsf{照应 1}$。/doge 这 `U` 怎么转移都是 `U`，而 `T` 和 `F` 怎么转移都不会变成 `U`。 哦哦哦，这不是只用 dfs 一下就行了吗？ 把样例 123 过了。样例 4 RE 了。 WTF？ 发现 `dfs` 到七万多层的时候寄了。 哦哦哦，栈开的不够大。 啊？跑了 $0.8\operatorname s$？ 加了个快读$_\textsf{伏笔 2}$（原来是 `scanf`），压到了 $0.3\operatorname s$。/doge 此时大概是 $10:00$。 然后看了看 CD。 先想 C，一眼搞出一个 $\Theta(n^2q)$ 的做法，写写写，$35$ 分到手。 然后这特殊性质……什么（）玩意，这有什么意义吗$_\textsf{伏笔 3}$？先去看 D 了。 D 题，一看这 B 性质不是送的吗，但是先不着急打（ 上来还是直接想 dp！ 很快想出来一个 $\Theta(T(n^2+m))$ 的 dp。 （起初以为复杂度是 $\Theta(T(n^2+nm))$，但是一想可以双指针优化掉。） 写的时候发现好像有点像个什么线段树优化$_\textsf{伏笔 4}$……但是还是先把 $36$ 分敲掉了。 然后又把 B 性质敲了，$8$ 分到手。 然后发现 `run5` 跑了 $1.5\operatorname s$……咋搞的？ 上快读，$1.5\operatorname s\to0.7\operatorname s_\textsf{照应 2}$。感叹 `scanf` 的垃圾。 然后看了看 D 的其他部分分，感觉不太好写，就回去想 C 了。此时大概是 $11:30$。 想着构造这样一个序列相当于两个指针 $i,j$，每次选择一个跳一步，要求时刻满足 $a_i>b_j$，问是否能跳到 $i=n,j=m$。 然后发现，例如跳 $i$，每次肯定跳到一个前缀最大值，否则肯定不优。 那不是维护一个前缀最大值不就行了吗？！（和 $b$ 的前缀最小值）正解了？！ 然后开写。 写完先测样例 4，WC 怎么全是 $1$？ 回去测样例 2，错了！ 咋搞的？看到 $n,m$ 只有 $6$，把错的询问抓下来！ 然后还抓错了 /kk 抓完了然后（手动）离散化。 发现刚才的做法是假的！！！因为最后一个数不一定是最大值，所以当一个跳到最后时另一个可能跳不到最后！！！ 但是当**最后一个数是最大值**，也即特殊性质的时候，它是对的$_\textsf{照应 3}$！ 然后感觉这个做法可以扩展一下然后 $100$ 分。 然后不管了，已经 $11:20$ 了，只求把能过特殊性质的代码调对。 然后调到了 $11:40$，把样例 $4$ 过了。 看看输入量，虽然跑样例时间不长，但是还是加了个快读$_\textsf{照应 2}$。 然后检查了一下文件，然后等待比赛结束。 --- 估分：$100+100+70+44=\lfloor100\pi\rfloor$。 考完试出来，同学们纷纷给出了估分： csl：$100+100+35+36=\lfloor100e\rfloor$。（貌似是大众分） yry：$100+100+0+36=236$。（有点忘了，等下确认一下） yjl：$100+100+100+100=400$。（AK 爷拜谢） --- 下午被我妈强制带去公园。 晚上打 ABC，做完六题发现 G 题两个人过，直接弃了。 有人说 D 题正解就是线段树优化 DP$_\textsf{照应 4}$，我去我场上往这块想了但是没细想是吧。 搞了代码在洛谷测，前两题 $100$，没挂！后两题民间数据还没出来。 云斗估分 $100+100+70+36$，我 D 题咋挂了 $8$ 分。 # Day 2 小图灵 $100+100+95+36$，C 题只 WA 了最后一个点 信友队 $100+100+90+36$，C 题怎么没 WA 然后 T 了两个。~~那 CCF 岂不是要给我过了。~~ 洛谷数据终于全了，$100+100+60+36$，好好好我 C 特殊性质怎么还挂了十分。 CCF，你的 C 题数据准备好迎接我代码的挑战了吗（ # Day 7 通过【】查到了分： $$100+100+70+44=314$$ 好好好，C 题数据还行，但是 D 题这不随便 hack？！这是怎么过性质 B 的。 《民间数据处处 $36$，CCF $44$》 和出场估分一模一样可还行？ ```plain 17 1 2 2 1 1 1 1 114 2 1 514 ``` ```plain 17 1 2 2 1 1 1 1 114 2 1 514 ``` ```plain 17 1 2 2 1 1 1 1 114 2 1 514 ``` ```plain 17 1 2 2 1 1 1 1 114 2 1 514 ``` ```plain 17 1 2 2 1 1 1 1 114 2 1 514 ```