526互联

Codeforces Round 671 (Div. 2) A. Digit Game

发布时间 2023-10-14 16:17:07作者: zsxuan

\(R\) 和 \(B\) 在玩一个数字游戏，给一个含有 \(n\) 位的正整数 \(x\) 。俩人轮流操作， \(R\) 先行动。

在每一步中，\(R\) 可以选择 \(x\) 中一个未被标记的奇数位置并标记，\(B\) 可以选择 \(x\) 中一个未被标记的偶数位置并标记。

当最后只剩下一个未被标记的位置时，让这个数为 \(m\) 。如果 \(m\) 是奇数，则 \(R\) \(win\) ，否则 \(B\) \(win\) 。假设两人都会以最优策略进行游戏。

显然当 \(n\) 为偶数，最后将留下一个偶数位置未标记。于是 \(B\) 可以决定 \(m\) 在哪个位置。若所有偶数位置中存在偶数数字，则 \(B\ win\) ，否则 \(R\ win\) 。

否则最后将留下一个奇数位置未标记。于是 \(R\) 可以决定 \(m\) 在哪个位置。若所有奇数位置中存在奇数数字，则 \(R\ win\) ，否则 \(B\ win\) 。

view 
#include <bits/stdc++.h>
typedef long long ll;
void solve(){
	int n; std::cin >> n;
	std::string s;std::cin >> s;s = " " + s;
	if (~n & 1) {
		int ok = 0; for (int i = 2; i <= n; i += 2) if (~(s[i] - '0') & 1) ok = 1;
		std::cout << (ok ? 2 : 1) << '\n';
	}
	else {
		int ok = 0; for (int i = 1; i <= n; i += 2) if ((s[i] - '0') & 1) ok = 1;
		std::cout << (ok ? 1 : 2) << '\n';
	}
}
int main() {
	int _ = 1; std::cin >> _;
	while (_--) {solve();}
	return 0;
}