题解 CF1221E 【Game With String】

首先，对于一个连续的`.`序列我们将其分离出来考虑。 这样，我们就得到若干个**互相独立**的小线段。 我们尝试将这些小线段分类，设其长度为$l$： 1. 双方都不能操作的**无用**线段，当且仅当$l < b$ 2. 仅可能后手操作的线段，而先手不能操作，当且仅当$ b \leq l < a $ 3. 先手和后手都只能操作$1$次的线段，当且仅当$a \leq l < 2b $ 4. 其他线段，$l \geq 2b$ > 引理$1$ ： 如果存在$1$条及以上的$2$类线段，那么先手必输。 后手至少可以比先手多$1$个额外的能够操作的地方，如果后手某一次不能在其他地方操作了，他可以在$2$类线段上操作，而先手不能。如果此时先手仍能操作，那么之前后手必然不会去使用这些$2$类线段。 > 引理$1$的推论 ： 如果存在$2$条及以上的$4$类线段，那么先手必输。 首先，后手可以有$1$步的代价将$1$条$4$类线段变成$2$类线段，即只在前部分保留一段长为$l' \in [b,a)$的线段。显然，先手在比后手优势在可以先行动，他最多只能化解$1$次这样的情况。如果$4$号线段数目大于等于$2$那么先手就必输了。 > 引理$2$ ： 若无$2,4$线段,如果$3$线段的数目为奇数，先手必胜，否则先手必败。 由于$1$号线段是无用线段，所以本引理显然成立。 利用上述结论，现在我们所需要处理的是先手能否将$1$条$4$线段做一次操作让后手必败。 显然，这样的操作只要存在，那么先手必胜，否则先手必败。 我们可以用$O(n)$的时间复杂度来枚举先手将这条长为$l\geq 2b$的线段分成$t1 , t2$两部分的可能性，使得切分完毕后不存在$2,4$线段，且存在**偶数个**$3$线段。 所以本题的时间复杂度为$O(n)$ 代码奉上。 ```cpp #include <bits/stdc++.h> using namespace std; const int N = 3e5 + 10; int a, b; char s[N]; vector<int> v; bool work() { int cnt = 0, ret = 0, len; int sz = v.size(); for (int i = 0; i < sz; i++) { if (v[i] >= b && v[i] < a) return false; if (v[i] >= 2 * b) cnt++, len = v[i]; if (v[i] >= a && v[i] < 2 * b) ret++; } if (cnt > 1) return false; if (!cnt) return (ret & 1); for (int i = 1; i <= len - a + 1; i++) { int t1 = i - 1, t2 = len - i - a + 1; if (t2 >= 2 * b || t1 >= 2 * b || (t1 >= b && t1 < a) || (t2 >= b && t2 < a)) continue; int add = (t1 >= a && t1 < 2 * b) + (t2 >= a && t2 < 2 * b); if ((ret + add) % 2 == 0) return true; } return false; } int main() { int T; scanf("%d", &T); while (T--) { scanf("%d%d%s", &a, &b, s); v.clear(); int n = strlen(s); for (int i = 0; i < n; i++) { if (s[i] == 'X') continue; int j = i; while (s[j] == '.' && j < n) j++; j--; v.push_back(j - i + 1); i = j; } puts(work() ? "YES" : "NO"); } return 0; } ```