CSP-S2024 游寄

上午放松了一下。

中午吃完饭就来到了科技楼，我猛然想起自己忘了 \(\text{tarjan}\) 怎么打，于是赶紧问了智力。

来到考场，发现周围还是有一群 XXS，希望他们可以拉低一下 1= 线。

考前安慰自己：没事没事，出事了也逝不了，只要不保单就行了。。。

T1

智障题。乱搞一下就过了。

用时：3 min

T2

我应该是这个世界上唯一一个不会贪心的人吧。

第一个问题是显然的。第二个问题我猛然意识到好像是哪里见过的贪心题（赛后证明是这样的，我是人机）。但是我不会贪心啊！？

所以该怎么办呢？我寻思着问题就是让每一个 \([l_i,r_i]\) 中都至少存在一个 \(1\)，即 \(sum_{r_i}-sum_{l_i-1}\geq 1\)，这不神笔差分约束嘛？虽然说差分约束是构造解，但是正确性应该还是可以保证的，因为最后得到的 \(sum_0\) 其实就是我们要减去的数。然后就套了前缀和的差分约束，接着就发现最后一个大样例 T 飞了，关于 \(\text{SPFA}\)，它死了。本来想试一下双端队列优化 \(\text{SPFA}\)，但是我还是不会，我嘞个豆，我怎么什么都忘了？？

为了更快，把差分约束的对象离散化之后手搓了几个大样例，发现应该是能稳过 \(80pts\)，剩下的看天命了，只好把它当个好的分数然后跑掉。

赛后发现人均 A 了 T2，欲哭无泪啊。。。

用时：1.5 h，硬要说的话，应该是 2h+ 了，因为 \(\text{SPFA}\) 整 emo 了。

T3

秒了，但是 \(O(Tn\log n)\)。

看到题之后，感觉很典啊！一眼 \(dp_{i,j}\) 表示搞定了前 \(i\) 个数，最后一个与 \(i\) 异色的点在 \(j\) 的最优解。乱玩发现：

• 若 \(j<i-1\)，则 \(dp_{i,j}=dp_{i-1,j}+[a_i=a_{i-1}]\times a_i\)。

• 若 \(j=i-1\)，则 \(dp_{i,j}=\max\{dp_{j,k}+[a_i=a_k]\times a_i\}\)，即 \(dp_{i,i-1}=\max\{dp_{i-1,j}+[a_i=a_j]\times a_i\}\)。

时间复杂度是 \(O(n^2)\) 的。但是可以把 \(dp_i\) 直接拍到一棵线段树上。对于第一类转移直接区间加。对于第二类的转移，最开始愣了一下，然后发现同一种颜色中，下标最靠后的 \(j\) 对应的 \(dp_{i,j}\) 一定是最优的，因此可以存一下每种颜色当前最靠后的位置，但是要注意这个 \(j\) 转移的时候是 \(\leq i-2\) 的。

大样例可以过。但是它不满。但是我不想手搓大样例（为我的 GG 埋下伏笔）。

赛后咸鱼说 T3 会被卡 log，但我寻思着严格的 \(O(Tn\log n)\) 怎么死？可能说的是其它的解法吧。他要卡我 log 不可能只开 \(n=2\times 10^5\)，而且 CCF 的机子很快，根本不怕的好吧。

update：真的寄了，以后再也不随意用 map 了，以后线段树修改的时候再也不跑 \(\Delta=0\) 的修改了QAQ！QAQ！

用时：大约 15 min

T4

没啥好说的，反正我不会。

本场另一个最大的失误就是这道题冲了个伪正解，结果 1h 后发现假了。

最后本来打的是 \(40\) 分的暴力，但是特殊性质 \(B\) 挂了，调不出来，然后就只有 \(28\) 了，我要寄了！！！

用时：你用 4h 减去上面的时间就知道了。

结束

等了半天终于出去了。

估分 \(100+80+60+28=268\)，发现人均 300+，感觉我应该是 ber 中垫底了。

以及我发现人均 T2 是真的，我是 joker 了。。。

我爱 T3。算是给我实打实来了一次直戳人心的教训。