首页 > 试题广场 >

石子游戏

[编程题]石子游戏
  • 热度指数:793 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
今天,度度熊和牛妹在玩取石子的游戏,开始的时候有堆石头,第堆有个石头,两个人轮流动作,度度熊先走,在每个回合,玩家选择一个非空堆,并从堆中移除一块石头。如果一个玩家在轮到他之前所有的石碓都是空的,或者如果在移动石头之后,存在两个堆包含相同数量的石头(可能为都为),那么他就会输。假设两人都在游戏时选择最佳方式,度度熊和牛妹谁会赢?如果度度熊获胜,输出“man”,如果牛妹获胜,输出“woman”(输出不包含双引号)。

输入描述:
第一行一个数表示T组数据
每组数据第一行一个数,表示堆石头。
第二行个数,表示每堆中石头的个数。


输出描述:
每组一行如果度度熊获胜,输出“man”,如果牛妹获胜,输出“woman”(输出不包含双引号)。
示例1

输入

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";
}

发表于 2021-08-27 21:27:41 回复(0)
#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),所以一定能出现这种状态。那么只要将数目总和减去最后形成的这个等差数列,就可以知道谁可以领到这个等差数列状态,就可以知道谁必胜了
发表于 2021-09-24 20:44:12 回复(2)
测试用例不太完整,如遇到0,1,2,2,4的情况先手也是必输无疑,此时应该做多一次遍历判断存不存在一个数i出现过两次并且i-1出现过一次。
发表于 2021-07-04 13:12:13 回复(2)
#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";
    }
}

发表于 2022-08-25 19:50:50 回复(0)
#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;
}

发表于 2021-09-06 23:11:54 回复(0)