[CSP-S 2024] 游记

Naszt · 2024-10-26 20:44:03 · 生活·游记

CSP-S 2024 游记

要退役了，写着玩的。

老师不让报 j 组。

s 组初赛只有 71 分，
几乎只写了单项选择题和完善程序题。

具体懒得说了，太水了。
~~才不是忘了。~~

月考？不存在的！
哈哈哈，老师帮忙请假啦~
打了场模拟赛，AK 虐全场。
~~然后就开始摸鱼了（~~

晚上做了个梦：
梦见我 250 分，卡在了第三题。
现在看来是预言了（

开考 10 分钟切了，我是排序+双指针做的。
听 Mr_yangshu 说答案就是众数的元素个数，想了一下好像没问题。

一两分钟就想到了正解，不过调了 2 小时！
实在不会二分，用的是 lower_broud()。

但是有浮点误差！还得在后面再暴力找几项，烦死了。

我的做法：
因为肯定是连续一段区间超的速，过连续一段区间的测速计，
所以就是问最少几个点使得每个区间都有点。
这是经典问题，把区间按 r 排序再贪心即可。

我需要时间啊……寄。

我的做法：

显而易见，首先可以想到 dp。

令 dp_{i,R,B} 为 [1,i] 项最后的红蓝的值为 R,B 时的最大答案。
好转移，不好优化，想了两三分钟，放弃。

可以发现 R,B 是交错的，最后一定是连续的一段区间。
令 dp_{i,s,0/1} 为 [s,i] 项为颜色 R/B 时的最大答案。

最简单的一种转移是该项和前一项颜色相同：

dp_{i,s,0/1}=dp_{i-1,s,0/1}+A_i[A_i=A_{i-1}]

然后就是该项和前一项颜色不同：

dp_{i,i,0/1}=\max_{s\le i}(dp_{i-1,s,1/0}+A_i[A_i=A_{s-1}])

发现第一维可以不要了，第三维是等价的。

dp_{i}=\max_{s\le i}(dp_{s}+A_i[A_i=A_{s-1}])

dp_{s}=dp_{s}+A_i[A_i=A_{i-1}]

令 P_i 为最大的值使得 A_i=A_{P_i}
注意到：

dp_{i}=\max(dp_{P_i}+A_i,\max_{s\le i}dp_{s})

dp_{s}=dp_{s}+A_i[A_i=A_{i-1}]

然后线段树优化即可。~~好像不需要？~~
但是我没时间写了。

花了半个小时读懂了题面，弃了。
还挤占了 C 题的时间。

估分：100+100+[50,60]+0=[250,260]

我的估分都不带错的，
我当时考完直接宣布的是 260 分。
结果果然是：100+100+60+0=260 分。

马上应该有 7 级钩了罢，终于可以出人头地了？