F. 一种异或游戏

这题卡常，真的没想到, 慎用map，不过可以使用数组hash来代替

这题虽然是披着博弈的皮，但感觉和常规的博弈差别蛮大的.

作为压轴题，带了一点思维，但又不是特别难.

珂朵莉 牛客周赛专栏

珂朵莉 牛客小白月赛专栏

n为Alice的牌数，m为Bob的牌数

先引入几个概念

• 被限定的数，特指 Alice牌中的数，且能在 Bob牌中找到 异或K

• 限定的数，特指 Bob牌中的数，能挤兑Alice牌，构建异或K

我们需要的是

• 被限定的数的总个数，注意是总个数 Hits

• 限定的数的各种种类，注意是种类数 Category

举例：

Alice:  2 2 2 4 3 5

Bob:    2 2 11

其中被限定总个数为4, 分别为 2, 2, 2, 4

限定数为1，即2

再理解以上这几个概念后，后面的分类讨论，基本就这几个概念完成的

• 对于 n <= m

  如果 Hits > 1, 则Alice必输 反之 Alice一定赢，先出完牌也算赢

• n > m

  这边还需要在细分下

  1. n - Hits + 1 >= m, Alice必赢

  2. n - Hits + 1 < m

     m - (n - Hits) < Category, Alice必赢，因为Bob必输

     m - (n - Hits) >= Category, Bob必赢，Alice输了

代码

import java.io.*;
import java.util.*;

public class F {

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));

        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();

        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int[] brr = new int[m];
        for (int i = 0; i < m; i++) {
            brr[i] = sc.nextInt();
        }
        int maxAlice = Arrays.stream(arr).max().getAsInt();
        int maxBob = Arrays.stream(brr).max().getAsInt();

        // 得用数组hash，替代java容器hashmap，卡常
        int[] alice = new int[maxAlice + 1];
        int[] bob = new int[maxBob + 1];
        for (int i = 0; i < n; i++) {
            alice[arr[i]]++;
        }
        for (int i = 0; i < m; i++) {
            bob[brr[i]]++;
        }

        // --------------------------------------

        // 下面是核心代码
        // 计算被限制的数，以及限制数的种类
        int category = 0;
        int hits = 0;
        for (int i = 0; i <= maxAlice; i++) {
            if (alice[i] > 0 && (i ^ k) <= maxBob && bob[i ^ k] > 0) {
                hits += alice[i];
                category++;
            }
        }

        // 胜负规则
        if (n <= m) {
            if (hits > 1) {
                System.out.println("Bob");
            } else {
                System.out.println("Alice");
            }
        } else {
            if (n - hits + 1 >= m) {
                System.out.println("Alice");
            } else {
                if (m - (n - hits) < category) {
                    System.out.println("Alice");
                } else {
                    System.out.println("Bob");
                }
            }
        }

    }

}