NOIP2023 游寄

· · 个人记录

10/30

学校开始停课，每天都是模拟赛。

被同龄选手爆杀得没了心态，最后三天放弃了模拟赛补题，开始补弱项。

从经验来看，复习没有啥大用，不如做新题？（雾

Day -2~Day 0

开始做数数、树形dp、字符串的新题。

没关系，啥也没考到也没有任何关系。

于是我们又得到了经验，做新题没有啥大用。

下次赛前试试摆烂。

Day 1

昨天晚上睡得早，今天早上精神好。

$8:30$，先看 $T1$ ，发现最优情况就是其他都倒排，自己正排。只要维护倒排的最小次小再和自己的正排比较就行了。很快就写完了，一遍过编一编过所有样例，感觉有点心不安？ 看$T2,3,4$，一道都没秒掉，慌了。 犹豫再三确定了做题顺序 $T2->T4->T3$。 $T2$ 感觉确定所有变量的最终值后就会非常简单，然后感觉有点像并查集，就在并查集的道路上越走越远。 越想越不对，无论路径压缩与否都是错的，后来意识到每个变量最终值只有可能是如下三类之一： - 一个变量的初值 - 一个变量的初值的非 - 一个确定的值 一段时间后终于醒悟，只要开个数组维护一下每个变量当前是上述的哪一种，最后再扩展域并查集就好了。 写写写，一遍过编一编过所有样例，反而又有点慌，写了个拍挂着。 只过了一个多小时到两个小时，优势在我。于是在 $T3$ $T4$ 之间徘徊。 徘徊的过程中突然想到lhc学长停课时说过：“就怕到时候随机生成器假了，一直在拍一组数据”。于是去检查，发现mt19937好像真的假了，于是换成rand，终于不假了，放心。 $T3$ 翻来覆去只会 $\mathcal{O}(Qn^2)$ 且不会特性，而 $T4$ 的特性似乎唾手可得，于是坚定了做 $T4$ 的信念。 设计了平方的 $dp$，$dp_{ij}$ 表示考虑前 $i$ 天，当前连续打卡了 $j$ 天最大值。 发现对端点离散之后最优解只可能要选就选完整的一段区间，于是这个复杂度其实是 $\mathcal{O}(min(n,m)^2)$ 的。 状态两维不好做，先放了放，去想特性。 $k \le 100$：$j$ 那一维只可能开到 $k$ ，$\mathcal{O}(min(n,m) \times k)

相离：考虑一维 dp_i 表示前 i 段且第 i 段选的最大值。转移应当枚举上一次不选的地方。

等等，那这个一维dp推广到一般情况不是很容易吗？

线段树优化似乎呼之欲出，当时好像还剩 $2h$， 开写！ 终于不是一遍过编一编过所有样例了，大概还剩 $1h+$ 的时候过样例。 回过头来想，好像这就是线段树优化 $dp$ 的经典题？那我是不是也不算有优势？ 想 $T3$，但是还是只会 $35pts$，只能先冲了，一遍过编一编过所有小样例，还剩 $1h$ 不到一点。 多给了自己 $20min$，还是不会，开始检查。 估计是太菜了，不知道为啥没写对拍，开始干瞪眼检查各种易错点，`long long`，数组开小，变量重名，未定义语法。 到最后给 $T4$ 加了个快读，改了一个变量重名的地方，就这样结束了。 估100+100+35+100，感觉要有好多阿克的啊 希望别挂，这样还能有点希望，继续加油哦！ upd：grg学长说T3的 $dp$ 等价于八联通，所以不行的话障碍只能是一横或者一竖或者一个转的L型，接下来就较为容易了。stogrgorz