CF 思维题随记

发布时间 2023-12-12 20:04:56作者: 御坂夏铃

CF1487B Cat Cycle

首先小猫 A 的行动是确定的,我们可以算出它走的圈数和最后的位置。然后根据 \(n\) 分情况讨论:

  • 偶数不会相遇,直接做。
  • 奇数。如果猫 A 不动那么猫 B 每圈只需要走 \(n-1\) 步。现在猫 A 会动其实就是猫 A 每多走一圈,它们就多相遇一次,猫 B 就少走一步。将猫 A 走的圈数加到猫 B 的总步数里即可,注意判断最后一圈是否会相遇。

CF1487C Minimum Ties

把所有球队看成一个环,方便我们下面处理。

对于球队数量为奇数的情况,每支球队都钦定打不过后面一半的球队,打得过前面一半的球队即可。

偶数比较麻烦,因为多输一次相当于平局两次,所以每支球队恰好平局一次最优。钦定相邻的球队两两平局,对于剩下的关系,奇数的情况就不能直接套用了。考虑到相邻球队编号奇偶性不同,所以只需要根据两支球队异或后最后一位为 \(0\) 还是 \(1\) 决定胜负即可。