题解 | #F. 一种异或游戏#

一种异或游戏

https://ac.nowcoder.com/acm/contest/67730/F


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");
                }
            }
        }

    }

}

全部评论
珂朵莉姐姐好厉害😍
1
送花
回复 分享
发布于 2023-10-28 00:36 湖北

相关推荐

6 2 评论
分享
牛客网
牛客企业服务