首页 > 代码库 > bzoj1982 [Spoj 2021]Moving Pebbles 博弈论
bzoj1982 [Spoj 2021]Moving Pebbles 博弈论
开始还以为要用sg函数。
想了半天想不出来。
后来才发现想错了。
/**************/
显而易见，当n为偶数并且a[i]可以两两配对时，状态为先手必败。
因为无论你做什么操作对方都可以做另外一个操作来抵消你的操作。
其他情况是先手必胜。你总能通过一步变为先手必败的状态。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
inline int read(){
int x=0,f=1,ch=getchar();
while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘){f=-1;}ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
return x*f;
}
int n;
int a[100005];
int main(){
n=read();int i;
if(n&1){
puts("first player");
return 0;
}
for(i=1;i<=n;i++) a[i]=read();
sort(a+1,a+1+n);
for(i=1;i<=n;i+=2)
if(a[i]!=a[i+1]){
puts("first player");
return 0;
}
puts("second player");
return 0;
}
bzoj1982 [Spoj 2021]Moving Pebbles 博弈论
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。