11.12模拟赛总结

时间分配

略读三道题目,T1是之前做过的题目,也基本忘得差不多了,T2是关于字符串的问题,大概好几个月没碰到这种题了,T3是树上的问题,难度较大

因此决定前一个小时做T1和对拍,再一个小时搞T2,搞不动就拿部分分,剩下一小时十分钟搞T3,最后二十分钟检查

T1

  1. 本题因为要保证最小值最大,应使用二分
  2. 对跳跃距离二分,check移走的岩石

问题

  1. 一直不清楚check的复杂度要求,感觉有一次用了DFS来check,本以为不是正解,没想到能过,可能是不符合条件的状态很多,所以时间复杂度大大降低
  2. 做对拍程序的时候需要打一个暴力,但是最近几次打的暴力真的太暴力了,好几分钟都跑不出来答案,根本没法对拍…所以说暴力程序也要保证可接受的时空复杂度

T2

  1. 因为好几个月没处理过字符串了,所以比较生疏,大脑里也没有什么能A的做法,就考虑拿部分分
  2. k=1的情况直接遍历即可,然后对于k=m和其他情况,又分了两种DFS的方法,结果也在预期之内,拿到了4个测试点的分数
  3. 但是没有想到DP会是正解,而且这题的DP也比较复杂,好理解的DP要开4个维度,有较高的思维难度

T3

  1. T3给出了大量的子任务,而我考虑了m=1的情况,即求LCA然后做加减法就可以
  2. 由于时间不够,也没有考虑数据为链的情况,不过即便考后又给了一个小时,也没有想到链状的怎么做

总结

自己做不出题往往是思维难度较高导致的,比如T2的DP,T3的链上前缀和,短时间内思维提升不会很大,但是可以通过经验弥补。

另外,检查十分有用,今天我检查过程中把T2的代码中注释掉了的 freopen 恢复了

11.13模拟赛总结
题解 P2661 【信息传递】