AcWing 894. java同学
原题链接
简单
作者:
季之秋
,
2021-02-08 15:19:54
,
所有人可见
,
阅读 306
import java.util.*;
public class Main{
static int f[]=new int[110];
static int n;
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
int res=0;
Arrays.fill(f,-1);//自然数没有-1
for(int i=0;i<n;i++){
res^=sg(sc.nextInt());
}
System.out.println(res==0?"No":"Yes");
}
static int sg(int x){//为0表示必败局面,不为0表示必胜局面
if(f[x]!=-1) return f[x];//同一个x的sg值是确定的,所以防重复
Set<Integer> set=new HashSet<>(); //因为在sg里面定义的set,所以每次递归都会刷新
for(int i=0;i<x;i++){//新状态只能更小0 --> x-1
for(int j=0;j<=i;j++){ //两堆石子,j<=i防止出现 7 9和9 7
set.add(sg(i)^sg(j)); //按照Nim定理,异或结果代表必胜和必败局面,
//和多个图一个原理,有n个状态 结果就是n个sg异或
}
}
for(int i=0;;i++){//找不在set中的最小自然数
if(!set.contains(i)) //
return f[x]=i;
}
}
}