Codeforces 1162E Thanos Nim(博弈)

一道有意思的博弈题。首先我们考虑一种必败情况,那就是有一方拿光了一堆石子,显然对方是必胜,此时对方可以全部拿走其中的n/2,那么轮到自己时就没有n/2堆,所以此时是必败态。我们先对所有石子堆sort,设最少的石子堆a[i]的石子数为a,有b堆这样的石子,当b<=n/2的时候,先手可以将另外一半的石子拿走至与前一半石子堆的数量一致( {a1 a2 ... an/2 a/n2+1... an} 变成 {a1 a2 ...an/2 a1 a2.... an/2} ) ,那么接下来无论对方拿走多少石子,我们都可以模仿对方的策略,显然,对方会先拿控一堆石子走到必败态,那么先手就必赢。在考虑一种情况,当b>n/2时,也就是最少的石子堆数量占一半以上,那么无论先手怎么取,后手都可以将剩下的石子堆保持最少的石子堆有一半以上(无论对方怎么取,我们只需要把n/2个石子堆数量保持与最小的一致),那么此时先手是一定会先拿空一堆石子,那么先手必败。综上,也就是判断最少石子堆数量是否有一半以上即可。

 //      ——By DD_BOND

 //#include<bits/stdc++.h>
#include<functional>
#include<algorithm>
#include<iostream>
#include<sstream>
#include<iomanip>
#include<climits>
#include<cstring>
#include<cstdlib>
#include<cstddef>
#include<cstdio>
#include<memory>
#include<vector>
#include<cctype>
#include<string>
#include<cmath>
#include<queue>
#include<deque>
#include<ctime>
#include<stack>
#include<map>
#include<set> #define fi first
#define se second
#define MP make_pair
#define pb push_back
#define INF 0x3f3f3f3f
#define pi 3.1415926535898
#define lowbit(a) (a&(-a))
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
#define Min(a,b,c) min(a,min(b,c))
#define Max(a,b,c) max(a,max(b,c))
#define debug(x) cerr<<#x<<"="<<x<<"\n"; using namespace std; typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef unsigned long long ull; const ll LLMAX=2e18;
const int MOD=1e9+;
const double eps=1e-;
const int MAXN=1e6+; inline ll sqr(ll x){ return x*x; }
inline int sqr(int x){ return x*x; }
inline double sqr(double x){ return x*x; }
ll __gcd(ll a,ll b){ return b==? a: __gcd(b,a%b); }
ll qpow(ll a,ll n){ll sum=;while(n){if(n&)sum=sum*a%MOD;a=a*a%MOD;n>>=;}return sum;}
inline int dcmp(double x){ if(fabs(x)<eps) return ; return (x>? : -); } int a[MAXN]; int main(void)
{
ios::sync_with_stdio(false); cin.tie(); cout.tie();
int n,cnt=; cin>>n;
for(int i=;i<n;i++) cin>>a[i];
sort(a,a+n);
if(a[]==a[n/]) cout<<"Bob"<<endl;
else cout<<"Alice"<<endl;
return ;
}
上一篇:Codeforces - 662A 思路巧妙的异或


下一篇:My way on Linux - 知识梳理计划