526互联

Educational Codeforces Round 90 (Rated for Div. 2) B. 01 Game

发布时间 2023-10-16 01:53:29作者: zsxuan

\(Alice\) 和 \(Bob\) 在玩一个 \(01\) 游戏，一开始有一个 \(01\) 串 \(s\) 。\(A\) 先开始，两人轮流操作。在每一步操作中，玩家可以选择 \(s\) 中两个相邻的不同数并且将他们删除。最后不能删数的玩家将失败。询问 \(Alice\) 是否可以获得胜利。

首先明确，当 \(min(cnt0, cnt1) \geq 1\) 时，总有一对相邻的数不同。于是可进行的轮次为 \(p = min(cnt0, cnt1)\) 。

若 \(p\) 为奇数，则 \(Alice\) 胜利，否则 \(Bob\) 胜利。

view 
#include <bits/stdc++.h>
typedef long long ll;
void solve(){
	std::string s; std::cin >> s;
	int cnt0 = 0, cnt1 = 0;
	for (auto x : s) cnt0 += (x == '0'), cnt1 += (x == '1');
	std::cout << (std::min(cnt0, cnt1) & 1 ? "DA" : "NET") << '\n';
}
int main() {
	int _ = 1; std::cin >> _;
	while (_--) {solve();}
	return 0;
}