考试:
9:00~9:10
看题:
- T1:很久之前做过,没有什么印象了。
- T2:感觉是广搜,但有可能要爆。
- T3:搜索题,猛加优化。
- T4:不知道是什么类型的题目。
9:10~9:50
写 T1,已经忘了怎么写的,只能当做一道新题来做。
写了个贪心,分了 2 中情况进行讨论,样例和自造样例都过了,但肯定会 WA。
其实在写计算的时候就已经将正解最难的地方写出来了,但没有意识到。
9:50~10:30
写 T2,直接先写了广搜,但发现会 T 飞,于是写了一个记忆化,但好像也会爆。
将每个状态记录了最少到达的次数,每次判断并更新。
考完后发现要用深搜和广搜进行结合,再控制一下 \(dfs\) 的深度,就可以保证空间和时间都不会炸。
10:30~11:00
T3 把广搜和深搜都写了一遍,但都会超时,想着怎么去优化一下时间复杂度。
11:00~11:20
看了一下 T4,没有什么思路,感觉很不妙。
打一下暴搜吧,终于看懂了这里的取模。
写写写,暴搜写挂了。
11:20~11:45
想到了 T3 可以将每个二维状态转换成一维的 string,这样就可以用 map 来去重了。
写写写,但不知道为什么写挂了,找不到原因。算了只能判随机数了。
11:45~11:55
乱写了 T4,然后检查了一下。
今天多半是寄了。
总结:
- 多回家复习以前过了的题目。
- 位运算的常用技巧要知道一些。
- 可以用状态压缩来解决一些递推的题目(判断两个状态是否有联系,无后效性)。