2024 CSP 游记

2024 CSP 游记

福建，新初三。

中强省偏强校菜鸡选手。

第一轮

只考提高。一周前发现自己什么也没有复习，然后随便学了一点。卷子简单碰了碰运气拿了 75，肯定过了啊。

第二轮

开考前一天打乒乓，暴扣好玩，不过 3:2 险胜，这下 rp 掉光了。

进场看 T1，直接排个序双指针？十五分钟切了，看 T2。感觉直接对每个减速车右端点从大到小排序然后查看在其右边第一个监测点是否会判断其为超速，如果会就考虑已经选的点会不会判断其超速，如果会就不新选监测点，否则就新选一个点。加速车考虑已有点会不会判断其超速，然后看最后一个点会不会判断其超速，如果均会或均不会就不新选监测点，否则新选最后一个点为监测点。感觉很对，开始写。写了 1h，过了所有样例。因为两题都看着像贪心加模拟不好拍就丢了，此时又过了 1h。

看 T3。n^2 动态规划是容易的，直接记 f_{i,j,0/1} 表示当前做到 i 且该点为红或者蓝色，另外一个颜色最近点在 j 的答案，这是个 n^3 转移。然后用一个前缀 max 套一下，尽管是三重循环但是是 n^2 的，然后开始写。调了一下就过大样例前几个点了，就丢了。

还剩一小时看 T4，试图码特殊性质 A，但是失败了，最后勉强求了一个不 RE，答案还奇怪得离谱。

考后出来仔细一想，T2 貌似假了。晴天霹雳啊。卡法就是减速车继续往右边选但是不影响，但是这时候加速车已经超速了，你就不用选 m 号监测点了。但是感觉比较难卡，自信一波数据不会卡太多分，在大样例和数据是一个 gen 的情况下。

考后 10min 就会 T3 了。策略失误也是失误，还是菜了。

考场上一眼 dp 题的如果写出平方或者三方暴力多尝试优化一下，各种数据结构、改状态、挖性质都可以试一试。这回吸取了一半教训，三方优化到了平方。后面题目理解完题意发现不太可做的时候重心前提。

考后估分 100+[60,100]+50+0=[210,250]，希望差上界不要太远。

教练估计能进 noip 初中生约 160 分。我估一等 160\sim 180，进 noip 要 180。