第 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
- 假设知道某一位上的值,我们就可以根据 encoded 数组,还原出原始的数组 perm。所以考虑怎么找出某一位上的值
- 考虑异或的性质: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) 的值,但是知道这些值有什么用呢
- 如果我们暴力枚举 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]的值
- 得到 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;
}