CSP-J&S

· · 生活·游记

CSP-J

比赛前一天到达考点不用上whk真爽

提前二十分钟进入考场，写好了代码模板，调好了编译器设置。

T1 T2 T3 一个小时左右写完。T4看了一眼没思路，遂开始打爆搜。用时20分钟打完暴力+测完样例。然后开始考虑能不能用DP解决。大概剩下一个半小时时想出了一种奇怪的DP思路，用了十分钟编码额，二十分钟测样例+对拍。最后一个小时对拍了一千组数据。

CSP-S

T1贪心看了一眼感觉可做，没有直接打暴力，用时40分钟做完（蒟蒻第一次场切绿）。

看了一眼T2是图论瞬间两眼一黑，没有任何思路，想了想决定二进制枚举+prim拿50分，打完大概用时一个小时，中间出了各种各样的问题。打完想到一个优化，把时间复杂度从 O(2^{k}\times (kn+m) \times \log_{2}n) 优化到了 O(2^{k}\times kn \times \log_{2}n) 能多得30分，考场本来想到了Kruscal+归并的正解做法但是把prim的时间复杂度记成了 O(n \log_{2} n) 所以认为优化过后的暴力已经是正解了，所以就没打。但是因为优化后的暴力最多一秒钟也只有1e9次操作，所以评测姬好的话可能卡常卡过，因此得分区间[80,100]

打完T2已经只剩15分钟了，T3 T4 都没打暴力，最终估分100+[80,100]=[180,200]就这样七级勾彻底无缘了，明年再战！