在永恒之森中，封存着有关万灵之树线索的卷轴，只要探险队通过最后的考验，便可以获取前往万灵之树的线索。
探险队需要从一段不断变化的谜题数组中找到最终的密码，初始的谜题为长度为 n 的数组 arr（下标从 0 开始），数组中的数字代表了 k
位二进制数。破解谜题的过程中，需要使用 与非（NAND） 运算方式，operations[i] = [type,x,y] 表示第 i
次进行的谜题操作信息： - 若 type = 0，表示修改操作，将谜题数组中下标 x 的数字变化为 y； - 若 type = 1，表示运算操作，将数字 y 进行 x*n 次「与非」操作，第 i 次与非操作为 y = y NAND arr[i%n]； >
运算操作结果即：y NAND arr[0%n] NAND arr[1%n] NAND arr[2%n] ... NAND arr[(x*n-1)%n]
最后，将所有运算操作的结果按顺序逐一进行 异或（XOR）运算，从而得到最终解开封印的密码。请返回最终解开封印的密码。 注意: -
「与非」（NAND）的操作为：先进行 与 操作，后进行 非 操作。 > 例如：两个三位二进制数2和3，其与非结果为 NOT ((010) AND (011)) = (101) = 5 示例 1： > 输入: > k = 3 > arr = [1,2] >
operations = [[1,2,3],[0,0,3],[1,2,2]] > > 输出: 2 > > 解释： > 初始的谜题数组为
[1,2]，二进制位数为 3， > 第 0 次进行运算操作，将数字 3(011) 进行 2\2 次「与非」运算， > 运算操作结果为 3 NAND 1 NAND 2 NAND 1 NAND 2 = 5 > 第 1 次进行修改操作，谜题数组的第 0 个数字变化为 3，谜题变成 [3,2] > 第
2 次进行运算操作，将数字 2(010) 进行 2\2 次「与非」运算， > 运算操作结果为 2 NAND 3 NAND 2 NAND 3 NAND 2 = 7 > 所有运算操作结果进行「异或」运算为 5 XOR 7 = 2 > 因此得到的最终密码为 2。 示例 2： > 输入: >
k = 4 > arr = [4,6,4,7,10,9,11] > operations = [[1,5,7],[1,7,14],[0,6,7],[1,6,5]] > 输出: 9 > 解释: > 初始的谜题数组为
[4,6,4,7,10,9,11], > 第 0 次进行运算操作，运算操作结果为 5； > 第 1 次进行运算操作，运算操作结果为 5； > 第 2
次进行修改操作，修改后谜题数组为 [4, 6, 4, 7, 10, 9, 7]； > 第 3 次进行运算操作，运算操作结果为 9； >
所有运算操作结果进行「异或」运算为 5 XOR 5 XOR 9 = 9； > 因此得到的最终密码为 9。 提示: - 1 <= arr.length, operations.length <= 10^4 - 1 <= k <= 30 - 0 <= arr[i] < 2^k - 若 type = 0，0 <= x < arr.length 且 0 <= y < 2^k - 若 type = 1，1 <= x < 10^9 且 0 <= y < 2^k - 保证存在 type = 1 的操作

Problem: LCP 81. 与非的谜题

[TOC]

思路

看到大量的与非操作，肯定不可能去真的计算。所以肯定有规律可循。

与非和异或不同，异或具备结合律，可以快速减少运算；与非不符合结合律。

仔细观察单个bit的与非运算，会发现如下规律：

和0做与非运算，结果一定是1。
和1做与非运算，原来是0就变1，原来是1就变0。

由此可知，海量的与非运算中，决定最终结果的是「最后一个0之后的1的个数」（如果不存在0那么答案就取决于1的总个数和y的该bit上的数值）。

因此，只需要维护某个数据结构，目的是快速计算arr数组各个bit上的「最后一个0之后的1的个数」。或者说是「最后一个0的位置」。

虽然与非运算的次数是x*n次，但由于与非的特性，只要有一个0存在，那么不管运算几轮n都等价于一轮n。

解题方法

用一个有序集合维护arr每个bit位上所有0的位置。我用的vector<set<int>>。

首先根据初始arr计算出这个数据结构。

然后每当遇到操作0，就将被操作的那个arr[x]的每个值为0的bit位从该数据结构移除，然后将新的y值的每个值为0的bit位保存到该数据结构中。

每当遇到操作1，就将该数据结构每个bit上最大的那个下标（也就是最后的0的位置）找出来，再根据该下标到n之间间隔的距离，就知道了该bit位的x*n个与非操作后的结果。如果某bit位上arr贡献了n个1，那么一共就是x*n个1。也就是y在该bit位上改变了x*n次。故计算x*n的奇偶性就行了。

复杂度

时间复杂度: O(knlog(n) + mklog(n))这里m是操作个数。
空间复杂度: O(n*k)

Code

[]

class Solution {
public:
    int getNandResult(int k, vector<int>& arr, vector<vector<int>>& operations) {
        int ans = 0;
        int n = arr.size();
        vector<set<int>> arrZeroPos = calcZeroPos(arr, k); // arrZeroPos[i] 表示第 i 个 bit，在 arr 里的 0 的出现下标。

        for (auto &op : operations) {
            int type = op[0];
            int x = op[1];
            int y = op[2];
            if (type == 0) {
                for (int i = 0, bit = 1; i < k; i++, bit <<= 1) {
                    if (!(arr[x] & bit)) {
                        arrZeroPos[i].erase(x);
                    }
                }
                for (int i = 0, bit = 1; i < k; i++, bit <<= 1) {
                    if (!(y & bit)) {
                        arrZeroPos[i].insert(x);
                    }
                }
                arr[x] = y;
                // if (!compareAll(calcZeroPos(arr, k), arrZeroPos)) {
                //     cout << "DIFFERENT! type=" << type << ", x=" << x << ", y=" << y << endl;
                // }
            } else {
                int nowAns = 0;
                for (int i = 0, bit = 1; i < k; i++, bit <<= 1) {
                    int b = ((y & bit) >> i);
                    if (arrZeroPos[i].empty()) { // 全 1，有 x * n 个
                        if (x & n & 1) {
                            b = 1 - b;
                        }
                    } else { // 存在 0
                        b = 1;
                        int lastZeroPos = *--arrZeroPos[i].end();
                        if ((n - lastZeroPos - 1) & 1) {
                            b = 1 - b;
                        }
                    }
                    if (b) {
                        nowAns |= bit;
                    }
                }
                // cout << "nowAns=" << nowAns << endl;
                ans ^= nowAns;
            }
        }
        return ans;
    }
    vector<set<int>> calcZeroPos(const vector<int> &arr, int k) {
        int n = arr.size();
        vector<set<int>> arrZeroPos(k);
        for (int i = 0, bit = 1; i < k; i++, bit <<= 1) {
            for (int j = 0; j < n; j++) {
                if (!(arr[j] & bit)) {
                    arrZeroPos[i].insert(j);
                }
            }
        }
        return arrZeroPos;
    }
};

LCP 81-与非的谜题

思路

解题方法

复杂度

Code