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

ゞ浴缸里的玫瑰 2024-03-29 15:11 72阅读 0赞

[Problem - 1373B - Codeforces][]

题意：

给定一个01字符串，两个人玩游戏，一方可以去掉两个不同的相邻元素，不能取的人失败，问胜方是谁

思路：

对于一个”序列“，如果它有序，就去考虑它的顺序的特殊性，否则就考虑哈希（因为是无序的，肯定看成集合）

这里的顺序无关紧要，因为对于一个01串一定存在相邻的不同元素

因此考虑哈希，统计0和1的个数，胜负和这个有关

然后去考虑决策对哈希的贡献，每次决策0和1的个数都会减1，因此和0和1的个数的最小值有关

如果这个最小值是奇数，就是先手赢，不然就是后手赢

Code：

#include<bits/stdc++.h>
    using namespace std;
    #pragma GCC optimize(2)
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    int t;
    string s;
     
     
    int main()
    {
        ios::sync_with_stdio(false);
        cin>>t;
        while(t--){
            cin>>s;
            int ans=0;
            int a0=0,a1=0;
            for(int i=0;i<s.size();++i){
                if(s[i]=='1') ++a1;
                else ++a0;
            }
            ans=min(a0,a1);
            if(ans&1) cout<<"DA"<<"\n";
            else cout<<"NET"<<"\n";
        }
        return 0;
    }

**总结：**

**对于一个”序列“，如果它有序，就去考虑它的顺序的特殊性，否则就考虑哈希（因为是无序的，肯定看成集合）**

[Problem - 1373B - Codeforces]: https://codeforces.com/problemset/problem/1373/B