CSP2022-S游记

· · 个人记录

csp2022-S游记

day-?

差点停课

day-1,0

期中考炸了

day1

2:27

下发了密码

2:50

看完所有题。感觉T2比较水，st表维护正/负数中的最大/小值，然后分类讨论一下就行了

敲敲敲

3:10

敲出来了。大样例没有过

3:30

发现预处理\log部分出错了：

const int L=19,N=100005;

for(int i=2;i<=L;++i) lo[i]=lo[i>>1]+1;//原来的代码
for(int i=2;i<=N;++i) lo[i]=lo[i>>1]+1;//正确的代码

然后过了样例

3:50

发现T1可以先预处理每个点到1号点的前三优的中转点，枚举第2/3个点，则第1/4个点一定是2/3到1号点中前三优的中转点

开始敲

4:10

敲完。一遍过了所有大样例

开始打对拍

4:30

什么也没拍出来

开始想T4

想了一下预处理$dp[x]$表示根到$x$节点的路径的答案，则答案为$dp[s]+dp[t]-2dp[lca]

举出了无数个反例

莫队？？

发现只能往右端点加 ，而且cspS应该不会考这种东西吧？

数据随机显然可以乱搞（因为树高度在\log级别）

4:50

T4什么都没想出来

开始想T3

想了亿下，发现只要约束2满足，那么约束1一定也满足 现在问题变成了维护点的出度 想了各种数据结构，啥都没想出来 ~~（没有想到哈希，我智障了）~~ 由于删/加边$O(\log n)$，删/加点$O(点的入度)$，因此特殊性质1可以过 **5:10** 开始敲T3 **5:30** 终于敲完了。样例没过 **5:40** 发现一堆细节错误，改完之后过了前3个样例（最后一个大样例跑了3s） 开始敲T4 **5:55** 终于敲完了 样例二没过 手算了无数遍，没有发现什么问题。严重怀疑大样例错了 **6:05** 发现$k=3$的时候可以绕着走 改完之后过了样例2、3，没过样例4 又算了无数遍，检查代码无数遍 **6:15** 发现可以连续绕多次。 再开一个dp数组维护在与该点相连的点的答案就可以了 **6:20** 终于过了所有样例 打了一下T2暴力，没来得及造数据生成器，于是手捏了一个数据，没有问题。 **6:26** 检查了无数遍freopen **6:27** 比赛提前3mins结束 估分100+100+[50,60]+76=[326,336] 实际336 感觉题目难度和去年差不多，但是部分分给得很多 ## 总结 敲代码时一定要仔细。T2如果细心一点，就不会因为这种弱智错误浪费20mins的时间。 思维/经验都不够。从来没有见过哈希能这么用 祝大家CSP2022RP++