NOIP 2023 游记

· · 生活·游记

开个坑先。

去年考太烂了，今年能不能考好？

省流：没考哈希。 ## Day 2933256076 颓了一上午。 怎么考前还颓啊？ 听说学校在期中考试，物理水的一批，但是还是不敢想象。 不能颓了。反正模拟也补不出来，不如 [cf](https://codeforces.com/contest/1511)[lg](https://www.luogu.com.cn/paste/3kk8e5vs) 练练手。 ~~考前不要学新东西。~~ 本来想 $O(V^2)$ 骗 $70$，~~不会复杂度分析~~不知道是 $O(V^{\log_23})$ ，竟然直接[草过去了](https://www.luogu.com.cn/record/135353888)。这么巧妙的优化？子集卷积？学一下。子集卷积？学一下。子集卷积？学一下。子集卷积？学一下。子集卷积？学一下。子集卷积？学一下。子集卷积？学一下。子集卷积？学一下。 ~~学不会，算了。~~ # Day 1 JS-0047。越看越难过，怎么 S 考这么差。 昨天没睡好，十二点才睡着。不想吃早饭，很早到了，吹冷风。跟 irris 排一起。 `8:00` 打板和拍子。 `8:10` 打个区间加区间和线段树玩玩。 `8:20` 为啥 noip 的 pdf 叫 day1 啊。 `8:33` 怎么才发密码。好好好，延长五分钟。 `8:37` 看完除了 T3 的题（因为一车数学符号不想看）。开始 T1。 `8:42` 写完 T1。写了个桶排。推了个只比第一位的优秀结论。草稿纸上举几个例子，看上去很正确。 `8:47` 写了个拍子。为啥还没收到大样例？为啥 gen 出来的都是全 1？ `8:51` 拍的全挂了。发现两行写反了。这怎么过的样例 1？调 gen 的参数，n=m=5。 `8:55` 终于拿到了大样例。过了。扔了，拍子弃了。 `9:10` 怎么一直挂？挂了几百次，换了两次写法。最后没写并查集也没写 2-sat。 `9:46` 过了大样例，感觉挺强，扔了。怎么写这么慢！ `9:55` T3T4 随机游走，选择了 T4。随便分析了一下发现了 $n^2$ dp 有 `interval` 优化，有 56。 `10:13` 写完了。考前线段树用上了，高兴。没调就过了大样例，更舒服了。 `10:20` 决策了一下 T3T4，感觉 T3 性价比更高，于是选择 T4/yiw。手搓特殊性质（因为不期望过题）。 `10:25` 发现矩阵做不了性质 A，因为要乘 $m$。但是性质 B 看上去显然。 `10:30` 发现 $r<l$ 也可以相邻。好像不太能贪心。好像也要 dp。好像要离散化。好像还要双指针和线段树优化。不想写。 `10:32` 等等。离散化和线段树优化好像能过题啊。一段区间要么全选要么不选。好像很对。我好像过 T4 了？ `11:05` 搞完 T4。还是有点小细节的。拜谢性质 B。加快读跑了 1.9-2.1s，不管了。56pts 和正解对拍，启动！ `11:10` 这下还有快 2h 做 T3。怎么流鼻血了啊？怎么还没带纸啊？ `11:30` 搞鼻血根本没好好想题。无所谓，过三题了，不慌。感觉 T4 不简单的。先写特殊性质。 `11:45` 测完特殊性质，调了些小错，发现看错性质了！！！赶紧打个暴力 dp吧。 `11:50` 推了推 dp，简单 $n^2$。写完了。这下 35 保底了。 `11:55` 等等。这个 dp 形式……这不网格图吗？nice observation！ `12:00` 对着网格图思考，无果。想特殊性质，无果。 `12:10` 看着性质想到最值分治。推了推，发现有点单调性，不可思议。感觉很离谱，弃了。 `12:30` 脑子不清醒，思路混乱。想回了网格图上最值分治，再推一遍，发现真的有单调性。管它呢，想冲高分就只能写了。网格图牛逼！ `12:45` 第一次写最值分治。写了丑陋 st 表。不管效率了，能多过一点是一点。发现分治里要套二分套 st 表，那就安心了，反正都带 log。 `12:50` 测样例，过了前三个，四五全 0？？？发现第三个 $n$ 是一位数？那也没用啊。摆了。反正也不期望得分。 `12:55` 静态瞪锅。草，$m$ 打成 $n$ 了？再测，样例 $4$ 过了？这么牛的？自嘲地想起一句话，“”我 AK 了？”当然不可能，我带 log。 `12:58` 样例 $5$ 跑一分钟没跑出来第一个结果。就离谱。那就得分随机了。真摆了。 出来发现好像最值分治递归很深啊。好像没开栈？对啊，样例 $4$ 明明都过了的。希望没假。问了一圈好像都没我高。 云斗上测了所有题，没有一个 wa！全是 tle！赢！ 估分 $100+100+[55,75]+100=[355,375]$。这下吊打我的 S 了。 update：T2 到处挂，只剩 $80$ 了，最低可能到 $60$。ccf 求求你了，给满分吧。 update：T3 复杂度假了，不严格的 $n\log n$ 退化成 $n^2$ 了，只有 $45$。最终得分只有 $100+100+45+84=329$，比暴力分 $335$ 还低。