第 44 场双周赛 5647. 解码异或后的排列

rank 146

Desciption

给你一个前 n 个正整数的排列数组 perm，且 n 是个奇数（3 <= n < 10^5） 定义 encoded[i] = perm[i] XOR perm[i + 1] 。比如 perm = [1,3,2] ，那么 encoded = [2,1]  给你 encoded 数组，请你返回原始数组 perm 。题目保证答案存在且唯一

Solution

  1. 假设知道某一位上的值，我们就可以根据 encoded 数组，还原出原始的数组 perm。所以考虑怎么找出某一位上的值
  2. 考虑异或的性质：a XOR b XOR b = a。我们现在知道了 perm[1] ^ perm[2]，perm[2] ^ perm[3]，进而可以知道 perm[1] ^ perm[3] 的值，从而可以知道所有 perm[1] ^ perm[i] (2 <= i <= n) 的值，但是知道这些值有什么用呢
  3. 如果我们暴力枚举 perm[1] 的值，肯定是会超时的。这时候看到题目是关于 异或的，可以考虑在 二进制的每一位的值，进行操作枚举，肯定不会超时。看到 n 是个奇数，容易想到在 1 - n 中，二进制最低位的 0 和 1 的个数肯定是不相等的，且个数是固定的。我们可以枚举最 perm[1] 的二进制最低位是不是0，根据异或值可以统计出其他的数的最低位是0还是1，看和 1 - n 的最低位的 0 和 1 的个数是否相等，如果相等，则 perm[1] 的最低位是 0，否则肯定是 1。同理继续枚举 perm[1] 的其他二进制位的值是 0 还是 1，就可以得到 perm[1]的值
  4. 得到 perm[1] 的值后，根据异或值，得出其他 perm[i] 的值

Code

    public static int[] decode(int[] encoded) {
        int n = encoded.length + 1;
        if (n == 1) {
            return new int[] {1};
        }
        int[] num = new int[20];
        Arrays.fill(num, 0);
        for (int i = 1; i <= n; ++i) {
            int val = i;
            for (int j = 0; j < 20; ++j) {
                num[j] += val & 1;
                val >>= 1;
            }
        }

        int[] f = new int[n];
        f[1] = encoded[0];
        for (int i = 2; i < n; ++i) {
            f[i] = f[i-1] ^ encoded[i-1];
        }

        int st = 0;
        for (int i = 0; i < 20; ++i) {
            int x = 1 << i;
            int num1 = 1;
            for (int j = 1; j < n; ++j) {
                int val = (f[j] ^ x) & x;
                if (val > 0) {
                    num1++;
                }
            }
            if (num1 != num[i]) {
                x = 0;
            }
            st += x;
        }
        int[] ans = new int[n];
        ans[0] = st;
        for (int i = 1; i < n; ++i) {
            ans[i] = st ^ f[i];
        }
        return ans;
    }