Codeforces 1221F Game With String 思维题

题意：有两个人玩游戏，游戏规则如下：有一个长度为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");

			}

		}

	}

}

巴特西

Codeforces 1221F Game With String 思维题

最新文章

热门文章