AcWing
  • 首页
  • 题库
  • 题解
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

AcWing 893. 集合-Nim游戏

作者: 作者的头像   行者晓路 ,  2021-02-26 22:11:21 ,  阅读 11


0



import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    static int N = 110,M = 100010;
    static int[] s = new int[N];// s 表示集合里的数字
    static int[] f = new int[M];// f表示sg的值
    static int n,m;
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int res = 0;
        Arrays.fill(f,-1);
        for(int i=0;i<n;i++)
        {
            s[i] = sc.nextInt();
        }
        m = sc.nextInt();
        for(int i=0;i<m;i++)
        {
            int x = sc.nextInt();
            res ^= sg(x);
        }

        if(res!=0) System.out.println("Yes");
        else System.out.println("No");
    }

    static int sg(int x)//求每堆石子的sg值
    {
        if(f[x]!=-1) return f[x];//记忆和搜索,如果搜索过了直接return
        Set<Integer> S = new HashSet<>();
        for(int i=0;i<n;i++)
        {
            int sum = s[i];//每次取sum个石子, 剩余的石子个数为x - sum
            if(x>=sum ) S.add(sg(x-sum));
        }
        for(int i=0;;i++)//mex集合中没出现过的最小的非负整数
        {
            if(!S.contains(i))
                return f[x] = i;
        }
    }


}

0 评论

你确定删除吗?

© 2018-2021 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息