Codeforces 142D（博弈）

要点

不难发现问题转化成：n堆石子，每次最多选k堆最少选1堆然后拿走一个石子，谁先没子可拿谁败。本题中撤退不必考虑。
就是记笔记吧，类似nim的博弈，举例：$$k=3,n=4$$$$4堆石子分别是1、2、3、3$$全化为二进制$$01$$$$10$$$$11$$$$11$$然后每一位纵向加和，两位都是$3\%(k+1)==0$，全能整除$(k+1)$则后手胜，否则都是先手胜。PS：我只知道(k+1)应该与那个经典益智问题有关：共有若干火柴，每次最少拿1最多拿k，怎样先手必胜。

int n, m, k;

char s[105];

int ans, val[105];

bool flag1, flag2;

int main() {

	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m >> k;

	rep(i, 1, n) {

		cin >> s;

		val[i] = -1;

		int f1 = -1, f2 = -1, tmp = 0;

		rep(j ,0, m - 1)

			if (s[j] == 'G')	f1 = j;

			else if (s[j] == 'R')	f2 = j;

			else	tmp++;

		if (tmp == 0 || tmp == m)	continue;

		if (f1 >= 0 && f2 >= 0) {

			val[i] = abs(f2 - f1) - 1;

		} else if (f1 < 0) {

			flag2 = 1;

		} else	flag1 = 1;

	}

	if (!flag1 && !flag2) {

		int tmp[10] = {0};

		rep(i, 1, n)

			if (val[i] > 0) {

				int cnt = 0;

				for (int j = val[i]; j; j >>= 1)

					tmp[cnt++] += j % 2;

			}

		rep(i, 0, 9)

			if (tmp[i] % (k + 1) != 0) {

				flag1 = 1;

			}

		cout << (flag1 ? "First\n" : "Second\n");

	} else if (flag1 && flag2) {

		cout << "Draw\n";

	} else	cout << (flag1 ? "First\n" : "Second\n");

	return 0;

}

巴特西

Codeforces 142D（博弈）

要点

最新文章

热门文章