题解：P11219 【MX-S4-T3】「yyOI R2」youyou 的序列 II

引理

先手获胜当且仅当先手可以在忽略后手的情况下操作完整个区间，且后手可操作的部分的长度小于等于 \(c1\)。

注：后手可操作的部分指后手能操作的最靠左的点到后手能操作的最靠右的点的距离。

证明

充分性：

在满足以上条件的情况下，先手只需要利用任意次操作将后手无法处理的区间染色，之后用一次操作染完后手可操作的部分，先手获胜，得证。

必要性：

反证法：假设存在一种不满足以上条件的情况，使得先手能够获胜。

分两种情况讨论：

• “先手可以在忽略后手的情况下操作完整个区间”不成立，则先手无论如何也无法将整个区间变成红色，得证。

• “后手可操作的部分的长度小于等于 \(c1\)”不成立：

  设后手可操作部分为 \([L, R]\)。假设先手现在已经将所有后手无法操作的区间变成红色，现在操作了区间 \([l_1, r_1]\)。

  1. \(l_1 = L\)，则后手将 \(L\) 变为蓝色。下一回合，先手无法同时将 \(L\) 和 \(R\) 都变为红色。

  2. \(r_1 = R\)，同理，后手将 \(R\) 变为蓝色。下一回合，先手无法同时将 \(L\) 和 \(R\) 都变为红色。

  3. \(L < l_1\) 且 \(r_1 < R\)，无论后手如何操作，下一回合，先手无法同时将 \(L\) 和 \(R\) 都变为红色。

  因为先手无法同时操作 \(L\)，\(R\) 两个点，所以无论如何也无法将整个区间变成红色，得证。