石子游戏

string solve(vector<int> &stones){
    unordered_map<int,int> counts;
    int two=0;
    bool x=stones.size()/2&1;
    for(int i:stones){
        counts[i]++;
        if(counts[i]==2) two++;
        if(two==2||counts[i]==3) return "woman";
        if(i&1) x=!x;
    }
    return x?"man":"woman";
}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <unordered_map>
#include <iostream>

using namespace std;

typedef long long ll;

int main() {
    int T;scanf("%d", &T);
    while(T--) {
        int n;scanf("%d",&n);
        vector<int>vec(n);
        unordered_map<int,int>mp;
        int cnt = 0, zero = 0;
        ll sum = 0;
        for(int i = 0;i < n;i++) {
            cin >> vec[i];
            if(vec[i] == 0) zero++;
            if(mp[vec[i]]) cnt++;
            mp[vec[i]] = 1;
            sum += vec[i];
        }
        sort(vec.begin(), vec.end());
        if(n == 3 && vec[0] == vec[1] + 1 && vec[1] == vec[2]) {
            printf("woman\n");
            continue;
        }
        if(cnt > 1 || sum == 0 || zero >= 2) {
            printf("woman\n");
            continue;
        }
        sum = 0;
        for(int i = 0;i < n;i++) {
            sum += vec[i] - i;
        }
        if(sum % 2 == 0) {
            printf("woman\n");
        } else {
            printf("man\n");
        }
    }
    return 0;
}


楼上的题解没看太懂，而且有些情况也没有考虑到，这里是自己的解法（用例太弱，可能也不完全对）。首先把先手必败的情况给判掉：0的数目大于等于2时，相同数字对数大于1，出现了x,x+1,x+1这种情况，总和为0，这几种情况先手必败。其他情况，可以想到游戏结束的上一个状态一定是0, 1, 2, 3...n - 1这种，谁到了这个状态谁必败，而且因为判掉了先手必败的几个情况（保证了相同数字不大于2且总和不为0），所以一定能出现这种状态。那么只要将数目总和减去最后形成的这个等差数列，就可以知道谁可以领到这个等差数列状态，就可以知道谁必胜了

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        int m;
        cin >> m;
        vector<int> a(m);
        for(int j = 0; j < m; j++) cin >> a[j];
        // 只有一堆, 奇偶决定胜负
        if(m == 1){
            if((a[0] & 1) == 0)cout << "woman\n";
            else cout << "man\n";
            continue;
        }
        
        // 多堆, 需要排序
        sort(a.begin(), a.end());
        
        // 全为零, 先手直接败
        if(a.back() == 0){
            cout << "woman\n";
            continue;
        }
        
        // 排序后, 统计相邻数字相同的对数
        int close_count = 0;
        for(int j = 0; j < m - 1; j++){
            if(a[j] == a[j + 1]) close_count++;
            if(close_count > 1) break;
        }
        // 该数目大于1, 则先手败
        if(close_count > 1){
            cout << "woman\n";
            continue;
        }
        // 如果只有一对, 检查左右是否都只差1
        if(close_count == 1){
            int j;
            for(j = 0; j < m - 1; j++) if(a[j] == a[j + 1]) break;
            if((j - 1 >= 0 && a[j] - a[j - 1] == 1) || (j + 2 < m && a[j + 2] - a[j + 1] == 1)){
                cout << "woman\n";
                continue;
            }
        }
        
        // 一般情况
        bool even = true;
        for(int j = 0; j < m; j++) if(((a[j] - j) & 1) == 1) even = !even;
        if(even) cout << "woman\n";
        else cout << "man\n";
    }
}

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

string solve(vector<int> &stones){
    unordered_map<int,int> cnt;
    int two=0;
    
    // 默认石堆中，石子数目为偶数
    // 最后石子的序列为+1等差序列0，1，2，3，...
    // 所以每堆取石子的个数都为奇数（除了第一个）
    // 那么每两次奇数之和为一次偶数，每次奇数的赢家为先手
    // 因此奇数次后序列变为+1等差序列，因此下一次为后手取，取完后必有相等堆，后手输
    // 为了让第一个堆变成0，第一个堆取偶数次，不参加计数，从第二次开始
    // 即堆数为2、3时，先手赢；4、5时，后手赢；6、7时，先手赢...观察得到规律
    // 默认石堆中石子都为偶数时的赢家为x，可得：
    bool x = stones.size()/2 & 1;
    
    for(int i:stones){
        cnt[i]++;    // 石子数目为i的石堆数量cnt
        if(cnt[i]==2) two++;    // 相同石子数==2(>=2)的石堆
        
        // two==2(>=2), 先手无论如何取，第一次取完最少仍有一组石子数相同的石堆
        // cnt[i]==3同理，因此先手输，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);
        bool allzero=true;
        for(int i=0; i<n; i++){
            cin >> stones[i];
            if(stones[i]) allzero=false;
        }
        if(allzero){
            cout << "women" << endl;
        }else{
            cout << solve(stones) << endl;
        }
    }
    return 0;
}