【 4 / 5 】 Codeforces Round #581 (Div. 2)

【总结】

A

问题：考虑到特殊情况，但没有考虑清楚。
改进：提交前应多造简单样例试错。

B

发挥正常。

C

经过：

题意
给定一条路径，删除多余的点，使得路径所在最短路的长度不变。

思考
大部分时间思考任意点到终点的距离，分别想过实现 dij 、 dfs 、 bfs ，并想以此做决策，但实现困难，且无法很好地解释样例。
（灵光一闪，但闪得太晚）发现拿出三个相邻的点，比较 中间的点到两边的距离之和 与 两边点的最短距离，用 floyd 实现，可以很好地解释样例。

总结
通过数据范围 n <= 100 和关键词 “最短路” ，应该快速往 floyd 上思考，且对于实现麻烦的做法，应尽早舍弃，从新的角度去思考。

问题：在错误的方向上思考太久，在无用的实现上花太多时间。
改进：算法没把握，实现麻烦，应尽快转移方向；注意题目要点（数据范围，关键词）

【补题】

D

题意
给定 01 串 S ，构造 01 串 T ，使得对于任意区间， T 的 LIS 长度等于 S 的 LIS 长度，且 T 中的 0 尽可能多。

题解

1. S 中 0 不变，尽量将 1 变为 0
2. 从后向前考虑，将 1 变为 0 会对后面所有区间造成的影响
   • 对于以 0 为起点的 LIS ，会使 LIS 长度 +1
   • 对于以 1 为起点的 LIS ， LIS 长度不变。
3. 考虑第 i 个位置且 s[i] == 1 ，对于当前的 1 ，如果可更改，应满足，对于后面以 i+1 为起点的所有区间， 1 的个数应始终大于 0 的个数。
4. 实现上，就是从后向前遍历的过程中
   • 遇到 0 ， cnt -= 1
   • 遇到 1 ，如果 cnt < 0 ， cnt += 1 ；否则不变
5. 所以在遇到 s[i] == 1 时，如果 cnt == 0 ，则当前的 1 可更改。

E

to do