第一行一个数表示T组数据
每组数据第一行一个数,表示堆石头。
第二行个数,表示每堆中石头的个数。
每组一行如果度度熊获胜,输出“man”,如果牛妹获胜,输出“woman”(输出不包含双引号)。
2 1 0 2 2 2
woman man
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; }