CSP-2024游记暨rdfz一日游
Light_Pursuer
·
·
生活·游记
9.21
初赛，j 组稳定 93。（好像比学弟还低）
反正顺利晋级复赛了。
# 9.30
停课。
本来是要十一之后听课的，但是由于时间安排 ~~（其实是不想考政治）~~ 问题，提前到今天了。
# 10.1 ~ 10.23
停课时候真是一点休息时间都没有啊。
打了很多场多校联训，基本上每场挂分都挺多的。
# 10.24
在 llj 的指导下学会了对拍。
感谢 @nicodafagood
# 10.25
打了打板子，打了会 [这个](https://ealex.top/duel/home/)，被 sbj 大佬爆杀。
晚上玩了会 $gartic$，然后就被爆破了，没素质。
# 10.26
早上七点二十起的，吃了西红柿鸡蛋面，就很早来到 $rdfz$ 考 $j$ 组了。
靠前两三分钟虚拟机还死了一次机，差评。
而且薄膜键盘用着是真难受啊。
$j$ 组前 $30$ 分钟做完前三题，去厕所蹲了十分钟后想出 $t4$ 正解，然后到最后连样例都没调出来（滑稽
值得一提的是，我 $jt1$ 交的代码长度是 $0$。。。（大概率是没交上导致的，全国就我这么一个奶糖）
中午我妈给我带的饭。煎牛排，炒圆白菜和蒜蓉虾我吃了好多，然后在车上睡了一个多小时，起来就去考 $s$ 了。
下午精神抖擞，去打 $s$ 组。
话说 $rdfz$ 是只有薄膜键盘吗？差评。
$t1$ 五分钟秒掉，过了大样例就去看 $t2$。
$t2$ 想了五分钟大致思路就出来了，肯定是每个车超速的路程是一个段，把这些段整出来再跑个贪心+二分就 $O(nlogn)$ 糊过去了。
这道题我好像调了 $2h30min$。。。
一些~~常见~~错误：
1.排序按照右端点排序，按照左端点排序会挂飞。
2.精度问题很重要，如果你不确定的话，那就在所有变量后边都 $*1.0$，精度挂了你就挂飞
3.二分是哪个弱智写的 $l+r>>1$？原来是我。
4.注意只有速度 **严格大于V** 时才会被算作超速。
就这些吧。
接着还剩下一个小时左右，开 $t3
先打了 20 分暴力，大概有十分钟。接着想如何使用 dp 获得更多的分数。设计状态为 dp[i][j]，表示第 i 位匹配第 j 位 j<i 的最大价值。不难想到它的转移方式成可以通过原来推到的 所有第j+1个与第j个不匹配的方案数的最大值与预处理出来从 j + 1 到 i - 1 同色的贡献 的和来转移。
这样的话时间复杂度 O(n^2)，空间复杂度同，所有喜提 50pts。
最后 j = 0 +100+100+0=200pts，s=100+100+50=250pts。
讲个笑话：j<s。
完美撒花~