题意:有两个人玩游戏,游戏规则如下:有一个长度为n的字符串,这个字符串由 . 和 X 构成,Alice可以选择a个连续的 . 把它们变成X, Bob可以选择连续的b个 . 把它们变成X。题目中保证a > b, Alice先手,问双方都不放水的情况下谁会赢?
思路:注意到a > b这个关键条件,这个条件是本题的突破口。因为a > b, 我们可以把由 . 构成的区间分成四类:1:长度小于b的区间,这种区间谁都无法填充,不用考虑。2:长度大于等于b小于a的区间,这种区间只有b可以填充。3:长度大于等于a小于2 * b的区间。这种区间双方都可以填充,但是这种区间无法变成类型2的区间。4:长度大于等于2 * b的区间。这种区间可以一步变出类型2的区间。首先我们发现,如果存在类型2的区间,Alice一定赢不了,因为Bob才能填充这个区间。并且,如果类型4的区间大于1个,Alice也必输,因为Bob只需选择类型4区间中的一个,变出一个类型2的区间,Bob就必胜了。那么还剩下2种情况:1:没有类型4的区间。这种情况胜负就和类型3的区间数目相关了。2:只有一个类型4的区间,这时Alice还有可能补救一下。我们只需枚举Alice怎么填充,然后判断这样填充是否能必胜即可。
代码:
#include <bits/stdc++.h> using namespace std; const int maxn = 300010; char s[maxn]; int cnt[5], a, b; int get(int len) { if(len < b) return 1; else if(len >= b && len < a) return 2; else if(len >= a && len < 2 * b) return 3; else if(len >= 2 * b) return 4; return 0; } int main() { int T, re; scanf("%d", &T); while(T--) { scanf("%d%d", &a, &b); scanf("%s", s + 1); memset(cnt, 0, sizeof(cnt)); int n = strlen(s + 1); int len = 0; for (int i = 1; i <= n; i++) { if(s[i] == '.') len++; else { cnt[get(len)]++; if(get(len) == 4) { re = len; } len = 0; } } cnt[get(len)]++; if(get(len) == 4) { re = len; } if(cnt[2] > 0) { printf("No\n"); continue; } if(cnt[4] > 1) { printf("No\n"); continue; } if(cnt[4] == 1) { bool flag = 0; for (int i = 0; i <= re - a; i++) { int len1 = i, len2 = re - (i + a), tmp = 0; if(get(len1) == 2 || get(len1) == 4 || get(len2) == 2 || get(len2) == 4) continue; if(get(len1) == 3) tmp++; if(get(len2) == 3) tmp++; if((cnt[3] + tmp) % 2 == 0) { printf("Yes\n"); flag = 1; break; } } if(flag == 0) { printf("No\n"); } } else { if(cnt[3] % 2 == 1) { printf("Yes\n"); } else { printf("No\n"); } } } }