Codeforces Round 985 赛后复盘

B. Replacement

本来应该是一道十分钟内能看得出来的氵题，结果因为看错题目中的下标表示想了快一个小时。

CAUTION

• 一定记得看清楚下标表示

C. New Rating

一眼出思路的题目，看到答案支持 check 并且具有重要的 **“单调”** 属性，于是快速反应出这可以通过二分答案来解决，时间复杂度 $\mathrm{\Theta }(n\log n)$

但是，赛后看完题解发现有更优的 动态规划 写法，时间复杂度仅有 $\mathrm{\Theta }(n)$，并且比二分答案好写（一些吧），需要在这当中做取舍的话，现阶段还是选择二分答案好做，毕竟不怎么需要正确性证明。

TIP

看起来不好解决，但是答案可以 check，并且答案单调的题目，基本上都可以考虑二分答案，快速好写。

D. Cool Graph

看起来很简单但是很麻烦，赛时剩一个小时直接放弃不想写，赛后回来看发现还是有很多值得学习的地方：

• 对于操作的处理顺序直接决定了我们使用的数据结构的复杂性，需要花一些时间考虑但是也不能花太多时间在这部分优化上面
• 在筛选无向图的边集的时候，如何避免重复选中的问题：
  • 如果图中没有自环，就可以考虑判断边关联两点的大小关系做到最简单的的筛选（有自环也可以，就是要按照需求写一个特判）
  • 在需要统计单点集的时候，不可以通过删去对应的反向边来实现，这可能会导致边的其中一个端点被计入单点集合当中
  • 再有复杂统计需求的时候，可以考虑使用 DSU（并查集）实现，但是代码量偏大，在简单情况下不建议使用
• 在图和答案集合的储存中，善用不同的 STL 自带数据类型，例如 set，map，tuple，pair，vector 等等，可以节省很多代码量，并且提高代码正确率、降低调试难度
• 对于图的储存和离散化相关技巧还需要在做题中提升