- A. King’s Inspection
- B. Cash Gap
- C. Jet Trains
- D. Cutting Pizza
- E. Unique Solution
- F. Metro 2345
- G. Weight Overflow
- H. Checking Answers to Test
- I. Magic Trick
- J. Superpermutations
- K. Preparing Tests
- A. Attractive Flowers
- B. Blocking the View
- C. Fermat’s Last Theorem
- D. Guess the Path
- E. Hide-and-Seek for Robots
- F. Isosceles triangles
- G. Too Many Hyphens
- H. Planet Nine
- I. Dates
- J. Factory
- K. RotationAlmostSort
- L. Time Travel
题意：有一个$n \times m$个格子，每个位置上放着一个机器人。每个机器人有个朝向，用UDLR表示向上，向下，向左，向右。现在每次你可以选择一个机器人，把朝向顺时针或者逆时针转$90^\circ$。求出最少操作次数，使得不存在一对机器人互相可见。
题解：根据题目视野的限制，只有U和D或者L和R的机器人对可能互相可见，其他对都不可能，于是可以把U和D，L和R分开考虑。
观察可以发现，假设我们最终已经调整好每个机器人，考虑U和D的机器人们。我们一定可以找到一条从第一列到最后一列的分界线，使得分界线上方不存在D的机器人，分界线下方不存在U的机器人。如果假设第$c$列的分界线格子所在行是$border(c)$，那么必有$|border(c)-border(c-1)| \le 1$。对于L和R的机器人也类似。
假设我们找出了U和D的分界线，L和R的分界线，那么那些朝向不合法的机器人肯定可以通过逆时针或者顺时针转一次使得它合法。根据分界线的限制，我们可以DP出来最优的分界线。