Forethought Future Cup - Final Round (Onsite Finalists Only) C. Thanos Nim 题解（博弈+思维）

题目链接

题目大意

给你n堆石子(n为偶数)，两个人玩游戏，每次选取n/2堆不为0的石子，然后从这n/2堆石子中丢掉一些石子(每一堆丢弃的石子数量可以不一样，但不能为0)，若这次操作中没有n/2堆不为0的石子则输

题目思路

本来以为是nim博弈打sg表什么的，结果其实是一个思维题

结论：如果最小堆的数量小于等于n/2则，先手胜，否则后手胜

我们考虑最小堆数量超过n/2的情况。那么此时先手不管如何选取，都会选到一个最小堆，由于要求每轮取得石子数量大于0 ，那么最小堆的石子数必然会减少，而且此时取完后最小堆的数量就不会超过n/2

然后到了下一轮，那么此时后手可以选择不包含最小堆的n/2堆，把它们全部变成最小堆，那么此时显然最小堆数量又将大于n/2。那么就将进入一个循环。

但是这个循环总会有终止的时刻，也就是当最小堆石子数量为0且堆数超过n/2时，游戏结束，最后操作的人获胜。观察上面的过程，我们发现只有后手才能把最小堆的数量变为超过n/2，而先手只能被动地将最小值变小，所以最后胜利者一定是后手。

代码

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<cmath>

#include<cstdio>

#include<vector>

#include<string>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<unordered_map>

#define fi first

#define se second

#define debug printf(" I am here\n");

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

const ll INF=0x3f3f3f3f3f3f3f3f;

const int maxn=1e4+5,inf=0x3f3f3f3f;

const double eps=1e-10;

int n,a[maxn],mi=inf,cnt;

int main(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++){

        scanf("%d",&a[i]);

        mi=min(mi,a[i]);

    }

    for(int i=1;i<=n;i++){//计算有多少个最小堆

        cnt+=(mi==a[i]);

    }

    bool flag=(cnt<=n/2)?1:0;

    printf(flag?"Alice\n":"Bob\n");

    return 0;

}

参考链接

巴特西

Forethought Future Cup - Final Round (Onsite Finalists Only) C. Thanos Nim 题解（博弈+思维）

题目链接

题目大意

题目思路

代码

最新文章

热门文章