T1
用时:30min
问题类型:复杂度分析
看完题一眼秒了二分,发现没有单调性,而数据范围很小,应该可以直接枚举答案,大样例 900ms 极限卡过。
在 2h 的时候回来看了一眼,加了两个剪枝,不加只有 55pts。
总结:遇到时间复杂度比较满的的题,能多加剪枝就多加,不然会出现这种被卡常的情况。
T2
用时:1h
问题类型:贪心
先假定每个 ? 都是 0,不断把 0 变成 1,分讨一段连续问号的两端是什么情况,贪心去计算即可。
总结:这种分讨+贪心的题最好把思路梳理好在开写,一遍写完。
T3
用时:2h
问题类型:线段树分治、并查集。
想到把边类似线段树分治一样加到 0/1 Trie 上,用并查集维护。
然而打并查集时没带脑子,写了个路径压缩,调了 20min。
总结:带撤销的并查集只能按秩合并,不能路径压缩,下次写的时候要注意。
T4
用时:30min
问题类型:DP
毫无头绪,一直在想正解,其实 40pts 的暴力是简单的。
总结:遇到正解不会的题,可以先写暴力。