POJ1740 A New Stone Game

题目地址

题解

一般而言，这种题目都需要一定的找规律的技巧。
首先$n=1$，先手必胜，这是显然的。
$n=2$,如果两堆石头一样多，那么先手必败，因为后手可以不断模仿先手的操作来使石头数始终相同，达到自己不败的目的。
如果石头数不相等，那么先手可以转移到石头相同的状态。
$n=3$，可以构造出$2$堆相同的情况，只要去掉最多的那一堆就行。
$n=4$，只要可以拆成$2$个完全一样的子局面，先手就是必败态，其余是必胜态。
归纳一下，$n$是奇数，先手必胜；$n$是偶数，除非局面对称，否则先手必胜。

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}	
int n,a[1005];
void init(){
    
}
void solve(){
    for(;;){
        n=read();
        if(!n)break;
        for(int i=1;i<=n;i++)a[i]=read();
        if(n%2){
            printf("1\n");
            continue;
        }
        sort(a+1,a+1+n);
        int flag=0;
        for(int i=1;i+i<=n;i+=2)
            if(a[i]!=a[i+1]){
                flag=1;break;
            }
        printf("%d\n",flag);
    }
}
int main(){
    init();
    solve();
    return 0;
}