题解 | #石子游戏#

1. 按道理是应该用贪心的思想去做（实验的时候也是这样的），但是我们可以换种思路，通过实验然后对原数组不变（不需要移除元素），进行1. 数组折半后的奇数偶数。2. 相同堆有几对。3. 如果是奇数要易主。 4. 如果two==2 或者 cnt[i]==3铁定自己输对方赢。来通过这些规律来判断。

#include <bits/stdc++.h>
using namespace std;

string solve(vector<int>& stones){
    unordered_map<int,int> cnt;//存储数量

    int two = 0;// 有两个堆石子相等的对数

    bool x = stones.size()/2 & 1; //默认我的赢家为x（这个和石子堆的奇数偶数性质有关（总结出来的））

    for(int i :stones){
        cnt[i]++;//记录堆中相同数量堆的出现次数

        if(cnt[i]==2) two++;//出现了一对，所以加1

        // two==2（有两堆相同的了）, 先手无论如何取，第一次取完最少仍有一组石子数相同的石堆
        // cnt[i]==3同理（有三个数都同了，那么必然2个数相同），因此先手输，woman赢
        if(two==2||cnt[i]==3){
            return "woman";
        }

        if(i&1) x = !x;//如果遇到奇数个石头，进行转换。赢家（规律总结）


    }

    return x? "man" : "woman";


}



int main(){

    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;

        vector<int> stones(n);//初始化方式值得学习
        //注意，根据规则，所有都是0，必输
        bool isAllZero = true;

        for(int i =0; i <n; i++){
            cin>>stones[i];
            //注意，根据规则，如果遇到一个不是0
            if(stones[i]) isAllZero =false;

        }

        if(isAllZero){
            cout<<"woman"<<endl;
        }else{
            cout<<solve(stones)<<endl;
        }

    }

    return 0;

}