CSP2024 邮寄

CSP-J

开始的时候监考老师把压缩包和 pdf 密码写在白板上，然后我的位置非常神金，大概长这个样子：

只能看见半边密码，然后我大概猜了一下密码后面两个字符，猜对了？？？

好回到正题，花 10 分钟调教 sublime text 之后，我打开 pdf 一看：

这 T1 不是小丑题吗，去重做完了。

这 T2 不是小丑题吗，模拟做完了。

这 T3 不是小丑题吗，分类讨论做完了。

然后 T3 写了个拍子，嗯？？？秒挂。

原因是 200<228。

然后非常轻松去开 T4，看完题我感觉应该是个简单 dp，然后猜测数据范围 n^2 能过级别的，一看：n\le10^5，啊？？？

注意到 r\le100，所以正解应该是 O(nr) 的，看来这题不简单。

观察性质：每一轮每种颜色可以选择的行只可能有 n/n-1/0 行，于是我们记录它不能选哪行即可。

然后莫名其妙被卡常，大样例 1.1s，于是加快读、动态数组换指针，最后卡出来大样例 500ms，应该不会有问题。

座位几乎和 CSP-J 一样，但是往左挪了一位，这下可以看完密码了。

开 T1，T1 还是一如既往的简单，不想写 O(n)，想直接数据结构优化，然后我写了个树状数组上二分（离大谱），赛后发现其实直接 multiset 或者搞个指针扫一遍完事了。

开 T2，嗯这读入量？？？赶紧写快读，然后出现了一件令我赛后特别难受的事情：

就是这样的，赛时我计算 fread 数组大小，我一算，一组数据 4\times10^5 个数，10 组数据开 4\times10^7 应该不会有问题。

结果赛后，maojun 说他开了 6\times10^7，我问为什么，结果发现 T\le20 啊啊啊啊啊啊！！！

回归正题，前面按题意模拟后最后形如：

给你若干个区间，选出最少的点使每个区间内至少有一个点。

结果我一看，这不是经典问题吗，怎么做来着？好像是贪心。

但是我胡不出一个对的贪心，于是去想 dp，dp_i 表示钦定选点 i，转移时 j 能转移 i 当且仅当 \nexists [l,r],j<l\le r<i。

于是记录 f_i 表示右端点不超过 i 的区间的左端点的最大值，dp_i=\min\limits_{j\in[f_i,i)}f_j+1。

注意到 f_i 单调，于是直接单调队列优化即可，然后大样例挂了 1 组数据，我一看，没有车超速，特判就过了。

赛后：单调队列 while(head<tail&&dp[back]>=dp[i])tail--，寄。

这个做法调了我一个多小时，赛后 maojun 说去掉完全包含的区间贪心就对了。

然后看 T3，明显的 dp 题。

设 dp_{i,j} 表示前 i 个数，与 i 异色的末尾是 j（与 i 同色的末尾是 a_i），发现转移形如：全局加、全局 max、单点修改。打 tag 做完了，这 T3 怎么让我感觉比 T2 还简单。

这时候剩 100 分钟左右，开 T4。

哇这 T4 题面好答辩啊。想了比较久会 O(Tn\log^2n) 但是比较难打，直接开码。

90 Minutes Later

我超过样例 1 了，我超过样例 2 了，我超样例 3 寄了，盖亚！！！

然后调调调，剩 1 分钟时绝望地对着电脑屏幕发呆。

但是 A 性质肯定能过的。挂的原因可能是：一堆数组只开了 10^5 而不是 2^{17}。