poj1740 A New Stone Game

时间:2020-12-25 05:59:18

题意:对于n堆石子,每堆若干个,两人轮流操作,每次操作分两步,第一步从某堆中去掉至少一个,第二步(可省略)把该堆剩余石子的一部分分给其它的某些堆。

真是好♂题,代码不长就是好♂题。

首先考虑两堆相同的石子,先手一定必输,因为若是我操作第一堆,则后手也可以对第二堆做对称决策。

其实,其他情况,一定是先手必胜。

第一种情况:奇数堆。

我们可以将最大堆的石子分配给其他堆让他们两两配对,如下图所示:

poj1740 A New Stone Game

显然,红色部分绝壁不会超过第五个 石子的高度。

第二种情况:偶数情况

我们可以把最大堆和最小堆先配对,剩余的那段照样拿来和n-2堆石子配用。

poj1740 A New Stone Game

呆玛:

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
int n,f[],x;
int main(){
while (scanf("%d",&n)&&n){
int cnt=;
memset(f,,sizeof f);
for (int i=;i<=n;i++){
scanf("%d",&x);
if (!f[x]) cnt++,f[x]=;
else cnt--,f[x]=;
}
if (!cnt) printf("0\n");
else printf("1\n");
}
}