CSP2025游记

jzy_CSPJ_AK · 2025-11-04 17:03:32 · 生活·游记

J

8:30

前两题秒切。

8:45

第三题很快想到了正解：

最大复杂度为 O(n log n)，枚举就得 O(n)，那么后面枚举右端点必须是 O(log n) 或常数的。

突然想到贪心策略，对于每个左端点，尽量使右端点靠左是肯定更优的。于是对于每个左端点，使用前缀和+二分即可找到 第一个 满足条件的右端点。

接着就是贪心经典模型【区间覆盖】了。

11：30

l l-1 写反了，调了接近 三个小时。

T4来不及打了，看到有40分dfs，赶快打了。

~居然没看出来是个dp QAQ~

~看出来了也打不完了~

其实还有24分可以骗，来不及了。

11：55

发现 freopen 写错，赶快改了。

出考场了发现一堆人ak了。~悲痛欲绝~

S

2:30

发现T1是板，半小时秒切。简单反悔贪心。

3：00

此时还很自信，3.5h不信拿不到50分。

第二题显然是MST。似乎想到了正解：可以将原图跑一个做小生成树，那么非树边无用，可以删去。接下来就是 O(N*2^K)了，似乎可以实现。于是先打特殊性质：k=0，跑克鲁斯卡尔即可。因为其他的都可以在这上面推广：暴力即是枚举k个村子是否选取。

5：00

打了2.5小时，不知为何一直RE，只好去打T3T4。现在很慌。（其实这里是打错了，我直接将u v 两点之间的距离与 u 到 k_i+v 到 k_i 取了min，正确性有问题，再加上爆long long了，~玄学地~直接RE）

5：30

T4半小时以为骗了 44，后面才发现做法假了，只有 8。

5：25

T3做了半小时，暴力原有 20 分，但是哈希不知为何挂掉了，剩下5分钟。

T2 T3只好输出大样例。

总结：j和s都有一道题并不难，并且有思路，但是调了很久，甚至没调出来。导致后面还有分没有骗到。最大的问题就是代码实现，会的题没调出来，分就不尽人意。

改进：可以每个月抽时间做一两道大模拟，练习代码实现能力。dp是弱点，得多刷题。希望明年能拿到一等吧。

Update

J T2挂了，原因是x y n m 都写反了，居然过了大样例。35分。

S T4多拿了4分。