AcWing 893. 集合-Nim游戏
原题链接
简单
作者:
巨鹿
,
2020-03-24 15:14:27
,
所有人可见
,
阅读 1103
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main {
static int M = 105,N = 10010,m;
static int s[] = new int[M];
static int f[] = new int[N];
public static void main(String[] args) {
Arrays.fill(f, -1);
Scanner scanner = new Scanner(System.in);
m = scanner.nextInt();
for(int i = 0 ; i < m ; i ++) s[i] = scanner.nextInt();
int n = scanner.nextInt();
int res = 0;
while(n-->0) {
int x = scanner.nextInt();
res ^= sg(x);//将每一堆石子sg值异或起来
}
System.out.println(res!=0?"Yes":"No");
}
private static int sg(int x) {//sg值指的是,有向图中,一个点的下级点sg值中,最小的不存在的值,就是这个点的sg值,终点的sg值是0
if(f[x]!=-1) return f[x]; //算是做优化,将已经算好的sg值保存,下次见到,不必重新计算
Set<Integer> set = new HashSet<>();
for(int i = 0 ; i < m ; i ++) {//枚举每一步的选法
if(x>=s[i]) set.add(sg(x-s[i])); //若这一步可以走,将下级点的sg值加入集合
}
for(int i = 0;i <= N; i++) {//在集合中找,最小的不存在的值
if(!set.contains(i)) {
return f[x] = i;//找到,保存,返回
}
}
return 0;
}
}