第15届蓝桥杯国赛JavaA组个人题解-G 异或博弈

题目

从长度为n的数组a中取2个数字, A希望数字异或尽可能大, B希望尽可能小

问, A先选, B后选, 异或为多少? B先选,A后选,异或为多少?

思路

0/1字典树

A先选: 枚举A的选择vA, 从字典树上移除vA, B希望尽可能小, 所以vB从高位开始应该尽可能与vA相同, 在树上查找即可

B先选: 同理,枚举vB, 移除vB, A希望尽可能大, 就要与vB相反

(没时间了, 没码出来, 交了暴力的30%)

代码(仅供参考)

import java.io.*; 

public class Main {
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in), 65535);
    static StreamTokenizer st = new StreamTokenizer(bf);

    static int I() throws IOException {
        st.nextToken();
        return (int) st.nval;
    }
 
/*
4
2 3 5 6

A选6, B需要最小选5, 最小为110^101=3
B选6, A需要最大选3, 最大为110^011=5
输出 3 5
 */

    public static void main(String[] args) throws Exception {
        int n = I();
        int[] a = new int[n];
        Tree tree = new Tree();
        for (int i = 0; i < n; i++) {
            a[i] = I();
            tree.add(a[i]);
        }
        //打表(a);
        int ansAB = Integer.MIN_VALUE, ansBA = Integer.MAX_VALUE;
        int vA, vB;
        for (int i = 0; i < n; i++) {
            // A先选,B后选
            vA = a[i];
            tree.remove(vA);
            vB = tree.find(vA);
            ansAB = Math.max(ansAB, vA ^ vB);
            tree.add(vA);
            //System.out.println("A选" + vA + " B选" + vB + " 最小为" + (vA ^ vB));
            // B先选,A后选
            vB = a[i];
            tree.remove(vB);
            vA = tree.find(~vB);
            ansBA = Math.min(ansBA, vA ^ vB);
            tree.add(vB);
            //System.out.println("B选" + vB + " A选" + vA + " 最大为" + (vA ^ vB));
        }
        System.out.println(ansAB + " " + ansBA);

    }

    static void 打表(int[] a) {
        int n = a.length;
        int ansAB = Integer.MIN_VALUE, ansBA = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            // vAB:A已选定,由B选,B需要选一个最小的
            // vBA:B已选定,由A选,A需要选一个最大的
            int vAB = Integer.MAX_VALUE, vBA = Integer.MIN_VALUE;
            for (int j = 0; j < n; j++) {
                if (j == i) continue;
                int v = a[i] ^ a[j];
                vAB = Math.min(vAB, v);
                vBA = Math.max(vBA, v);
            }
            System.out.println("A选" + a[i] + " B最小 " + vAB);
            System.out.println("B选" + a[i] + " A最大 " + vBA);
            ansAB = Math.max(ansAB, vAB);// A从选择的结果里选最大结果
            ansBA = Math.min(ansBA, vBA);// B从选择的结果里选最小结果
        }
        System.out.println(ansAB + " " + ansBA);
    }

    static class Tree {
        static class Node {
            int cnt = 0;
            Node zero, one;
        }

        Node root = new Node();

        void add(int v) {
            Node p = root;
            for (int i = 31; i >= 0; i--) {
                int bit = (v >>> i) & 1;
                if (p.zero == null) p.zero = new Node();
                if (p.one == null) p.one = new Node();
                p = bit == 0 ? p.zero : p.one;
                p.cnt++;
            }
        }

        void remove(int v) {
            Node p = root;
            for (int i = 31; i >= 0; i--) {
                int bit = (v >>> i) & 1;
                if (p.zero == null) p.zero = new Node();
                if (p.one == null) p.one = new Node();
                p = bit == 0 ? p.zero : p.one;
                p.cnt--;
            }
        }

        int ans;

        int find(int v) {//查找最接近v的路径
            ans = Integer.MAX_VALUE;
            dfs(root, v, 31, 0);
            return ans;
        }

        void dfs(Node p, int v, int level, int curV) {
            if (level < 0) {
                if ((v ^ curV) < ans) ans = curV;//寻找最接近,异或值最小
                return;
            }
            int bit = (v >>> level) & 1;
            if (bit == 0 && p.zero != null && p.zero.cnt > 0) {
                dfs(p.zero, v, level - 1, curV);
                return;
            }
            if (bit == 1 && p.one != null && p.one.cnt > 0) {
                dfs(p.one, v, level - 1, curV + (1 << level));
                return;
            }
            if (p.zero != null && p.zero.cnt > 0) dfs(p.zero, v, level - 1, curV);
            if (p.one != null && p.one.cnt > 0) dfs(p.one, v, level - 1, curV + (1 << level));
        }
    }
}