CF1972B 简证

· · 个人记录

证：每轮操作后 U 数量奇偶性不变

只有三种情况：

UUU
UUD
DUD

分别对应：减少三个，减少一个与增加一个；每轮操作选择两个做，所以奇偶性不变。

最后一种情况数量上界是 O(n)，因此操作有穷。