CSP游记

· · 生活·游记

CSP-J

早上到考场，八点半开始考试，拿到题时先浏览了一遍。

T1：简单贪心。

T2：模拟，实在不行可以 O(1) 做，只不过没必要。

T3：简单的 dp 和贪心，再加个前缀异或优化。

T4：背包，加一点小转换。

花了 10 分钟想出所有题，然后开始做，用了一个小时做完，又花了一个小时检查。

最后一个半小时，闲的没事干，打了一个 LCT 和 AC 自动机的模板，然后比赛就结束了。

估分：100+100+100+100=400

CSP-S

下午两点半开始考试，发现时间居然有 4 个小时。

先看了 T1，发现是匹配问题就直接 dp，发现是 3 维，但仍然执迷不悟，尝试优化到二维再用线段树优化，硬刚了 30 分钟毫无结果。

发现时间不对赶紧来看 T2，一眼就发现 k=10 可以二进制枚举，然后发现时间复杂度不对，又发现 m 条边只有 n-1 条边在后面枚举时有用就先跑了一遍 MST，然后再计算，发现复杂度 1.3e8 有点极限但觉得能过。

::::error[智障错误] 计算时间复杂度时漏了个排序的 log，以为是 O(2^kn)，原本如果发现的话我是能优化掉的，我说为什么比赛时测大样例跑那么久，但是我没发现，唯一想出正解且打出代码的题也没做出来，给我整崩溃了。 ::::

完了发现时间已经过了两个半小时，看了眼 T3T4 的题面，觉得做不出来就回去和 T1 继续硬刚了，然而还是以为 T1 是 dp，仍然没有收获，打了个 O(n^3) 的暴力就走了。

开始做 T3T4 时只剩下 40 分钟，发现 T4 是我最擅长的排列组合，但高兴不起来，实在没时间了就把 T4 全排列的暴力打了，打完只剩下 25 分钟。

原本想打 T3 暴力的，结果看了一眼突然茅塞顿开把正解想出来了，用的是 AC 自动机。我早上才刚打过！

然而剩下 20 分钟也不够打了，挺绝望的，打了个总司令就摆了。

出来后和同学后讨论发现好多人都会 T1，问了才发现是简单贪心，给我干懵逼了，不过发现几乎没人想出 T3，也有点心理安慰。虽然我也没做出来。

然后感觉完了，今年估计与 noip 无缘了。

第二天发现洛谷上已经有题目了，T1 是道绿。真的哭死平常模拟赛蓝题都随便切的。

估分：55+55+0+4=114

总结

虽然这次 S 组失利了，但人总要往前看的，毕竟我现在初二，还有三年机会，也没有太难过。

并且，结合这次比赛和平常模拟赛，发现贪心应该是我的硬伤，到时候得好好练一下贪心。

这还说明了一个道理：千万不要学太多算法，不然就会像我一样 T1 想那么复杂，根本做不出来，不过感觉还是有好处的，毕竟 T3 就用了 AC 自动机。大家好像都没学过。