题目链接：https://codeforces.com/contest/1373/problem/B

题意

给出一个二进制串 $s$，Alica 和 Bob 每次可以选择移去 $s$ 中的一个 $10$ 或 $01$，无法选择者视为输掉游戏，判断最终谁会胜利。（$1 \le t \le 1000, 1 \le |s| \le 100$）

题解一

$s$ 范围较小，$O_{(n^2)}$ 模拟。

代码

#include <bits/stdc++.h>

using namespace std;

void solve() {

    string s; cin >> s;

    int cnt = 0;

    while (1) {

        bool flag = false;

        for (int i = 0; i + 1 < s.size(); i++) {

            if (s[i] != s[i + 1]) {

                s = s.substr(0, i) + s.substr(i + 2);

                ++cnt;

                flag = true;

            }

        }

        if (!flag) break;

    }

    cout << (cnt & 1 ? "DA" : "NET") << "\n";

}

int main() {

    int t; cin >> t;

    while (t--) solve();

}

题解二

在移除所有相邻的不同字符后，字符串最终为连续的 $0$ 或 $1$，即移除了 $0$ 和 $1$ 中的较少者，其个数代表着游戏总共可以进行多少步。

代码

#include <bits/stdc++.h>

using namespace std;

void solve() {

    string s; cin >> s;

    int cnt[2] = {};

    for (char c : s)

        ++cnt[c - '0'];

    int mi = min(cnt[0], cnt[1]);

    cout << (mi & 1 ? "DA" : "NET") << "\n";

}

int main() {

    int t; cin >> t;

    while (t--) solve();

}

巴特西

Educational Codeforces Round 90 (Rated for Div. 2) B. 01 Game（字符串博弈）

题意

题解一

代码

题解二

代码

最新文章

热门文章