leetcode.cn/problems/W2ZX4X/">A. 符文储备

题意：

给定一个数组，问可以从中选择最多多少个连续的数，使得这些数排序后，相邻两个数的差最多是 1。

数据范围：

• 1 <= runes.length <= 10^4
• 0 <= runes[i] <= 10^4

题解：

值域范围很小，可以直接开一个大小为 10001 的数组，然后统计每个数出现的次数，最后遍历这个数组判断即可。

如果值域范围很大，可以开一个 map 来统计，然后遍历 map 判断即可。

代码：

class Solution {
public:
    int runeReserve(vector<int>& runes) {
        const int MAXN = 10010;
        vector<int> cnt(MAXN, 0);
        
        for (auto u: runes) cnt[u] += 1;
        
        int ans = 1;
        int res = 0;
        for (int i = 0; i < MAXN; ++i) {
            if (cnt[i] == 0) {
                res = 0;
                continue ;
            }
            
            res += cnt[i];
            ans = max(ans, res);
        }
        
        return ans;
    }
};

leetcode.cn/problems/Nsibyl/">B. 城墙防线

题意：

给定一些城墙的区间，按照递增顺序给出，任意两个城墙区间不相交。

现在统一给所有城墙膨胀，每个城墙膨胀数量一样，可以向左向右膨胀，问每个城墙膨胀的最大数量。

数据范围：

• 3 <= rampart.length <= 10^4
• rampart[i].length == 2
• 0 <= rampart[i][0] < rampart[i][1] <= rampart[i+1][0] <= 10^8

题意：

对于最左和最右边的城墙，其可以无限扩张，所以他们不被考虑在内。

考虑有 3 个城墙，对于 2 号城墙，可以将 1 号 到 2 号和 2 号到 3 号中间这部分城墙全部作为其膨胀得到的城墙。

考虑有 4 个城墙，对于 2 号城墙，可以将 1 号 到 2 号城墙中的部分作为其膨胀的部分，而 2 号和 3号中间这部分，就不好界定了。

考虑二分答案，每个城墙可以膨胀的数量，枚举到第 i 个城墙时，其左边还未被膨胀的部分都可以作为其膨胀的部分，然后再从其右边的部分膨胀其需要的值即可。

代码：

class Solution {
public:
    int rampartDefensiveLine(vector<vector<int>>& vec) {
        int l = 0, r = 100000000;
        int n = vec.size();
        auto check = [&](int mid) {
            // 对于每一个，先看其左边可以提供的，左边如果提供足够了，就不考虑右边了，否则看右边提供多少个
            int used = 0;
            for (int i = 1; i + 1 < n; ++i) {
                int left = vec[i][0] - vec[i - 1][1] - used;
                if (left < mid) {
                    int need = mid - left;
                    if (vec[i + 1][0] - vec[i][1] >= need) used = need;
                    else return false;
                } else {
                    used = 0;
                }
            }
            return true;
        };
        
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        return l;
    }
};

leetcode.cn/problems/kjpLFZ/">C. 提取咒文

题意：

给定一个长度为 len 的字符串 mantra 和一个 n * m 的矩阵 matrix，
字符串中的字符和矩阵中的元素均为小写字母，初始在 [0, 0] ，按照字符串的顺序依次走到矩阵中的每个位置，问最少需要走多少次可以走完。

数据范围：

• 0 < matrix.length, matrix[i].length <= 100
• 0 < mantra.length <= 100
• matrix 和 mantra 仅由小写字母组成

题解：

这题赛时被 dp 卡住了，后面才反应过来是三维 bfs。
每次移动和取数都会增加一次操作，移动会修改 x 或者 y，取数会修改 k。
从 (0, 0, 0) 开始 bfs ，当前位置的字符 matrix[x][y] 和 mantra[k] 相等，则说明可以取数。每次可以向上下左右移动 4 次。

每个(x, y, k) 扩展最多 5 次，时间复杂度是 $O(n\times m\times len)$。

代码：

const int INF = 0x3f3f3f3f;
int dist[105][105][105];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

class Solution {
public:
    int extractMantra(vector<string>& matrix, string mantra) {
        int n = matrix.size(), m = matrix[0].size(), len = mantra.size();
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                for (int k = 0; k <= len; ++k)
                    dist[i][j][k] = INF;
        
        dist[0][0][0] = 0;
        queue<tuple<int, int, int>> q;
        q.emplace(0, 0, 0);
        
        int ans = INF;
        while (!q.empty()) {
            auto [x, y, k] = q.front(); q.pop();
            if (k == len) {
                ans = min(ans, dist[x][y][k]);
                continue ;
            }
            
            if (matrix[x][y] == mantra[k]) {
                if (dist[x][y][k + 1] > dist[x][y][k] + 1) {
                    dist[x][y][k + 1] = dist[x][y][k] + 1;
                    q.emplace(x, y, k + 1);
                }
            }
            
            for (int i = 0; i < 4; ++i) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny][k] > dist[x][y][k] + 1) {
                    dist[nx][ny][k] = dist[x][y][k] + 1;
                    q.emplace(nx, ny, k);
                }
            }
        }
        
        return ans == INF ? -1 : ans;
    }
};

leetcode.cn/problems/qoQAMX/">D. 生物进化录

题意：

给定一棵树，从根开始，构造这棵树的生成方式，用 0 表示父节点生成一个子节点，用 1 表示从子节点回到父节点，用 0 和 1 表示生成方式，求所有生成方式的最小字典序，注意，生成完树中所有节点后，不用回到根节点。

• 1 <= parents.length <= 10^4
• -1 <= parents[i] < i (即父节点编号小于子节点)

题解：

一个直观的生成方式，dfs 得到每棵子树的最小字典序生成方式，然后按照字典序排序输出。复杂度是正确的，但是不会证明。

首先每个子树会被 sort 一次，即除了根外都会 sort 一次，总共 sort 的元素数是 $O(n)$，但是内部的字符串长度是不定的，但是注意，sort 中两个字符串比较取决于较小的长度，即完全 k 叉树的情况会得到最大的 sort 复杂度，如此以完全二叉树为例，$2^{14}=16384$，同时深度最大时，比较最小，最多比较 14 层。故粗略的估计复杂度为 $O(n\log n\times 14)$。

代码：

class Solution {
public:

    string dfs(int u, vector<vector<int>>& g) {
        vector<string> vec;
        for (int v: g[u]) {
            vec.emplace_back(dfs(v, g) + "1");
        }
        sort(vec.begin(), vec.end());
        string res;
        for (auto& s: vec) {
            res += "0" + s;
        }
        return res;
    }

    string evolutionaryRecord(vector<int>& parents) {
        if (parents.size() == 1) return "";

        int n = parents.size();
        vector<vector<int>> g(n);

        for (int i = 1; i < n; ++i) {
            g[parents[i]].push_back(i);
        }
        string ans = dfs(0, g);
        while (!ans.empty() && ans.back() == '1') ans.pop_back();
        return ans;
    }
};

leetcode.cn/contest/season/2023-spring/problems/ryfUiz/">E. 与非的谜题

题意：

给定一个长度为 n 的数组 arr，以及k 个操作，第 i 个操作 operations[i] = [type, x, y]，每个操作有两种类型：

• type = 0，表示修改操作，arr[x] = y
• type = 1，表示运算操作，将 y 进行 x * n 次与非操作，第 i 次与非运算为：y = y NAND arr[i % n]。

最后将所有运算操作的 y 的异或值返回。

数据范围：

• 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 的操作

题解：

对于位运算的题，位之间是独立的，考虑拆位，即单独考虑每一位。

对于两个位之间的与非操作，有四种情况：

• !(1 & 1) = 0
• !(1 & 0) = 1
• !(0 & 1) = 1
• !(0 & 0) = 1

可以发现，当任意一个位为 0 ，答案为 1，那么对于查询操作，最后一个 0 操作后，位变成 1，只需要考虑最后一个 0 的位置。

对于连续的 1 ，上述考虑 1 的变换，!(x & 0) => !x，即取反，那么只需要考虑连续 1 的个数为奇数还是偶数即可。

因此，我们的任务转换为了求每一位的最后一个 0 的位置，但是注意，我们还会修改值，因此需要一个快速删除和查询极值的数据结构，线段树或者set都可以。

代码：

set 实现

// set
class Solution {
public:
    int getNandResult(int k, vector<int>& arr, vector<vector<int>>& operations) {
        int n = arr.size();
        
        vector<set<int>> vec(k);
        for (int i = 0; i < arr.size(); ++i) {
            for (int j = 0; j < k; ++j) {
                if (arr[i] >> j & 1) continue ;
                vec[j].insert(i);
            }
        }
        
        int ans = 0;
        for (auto& op: operations) {
            int type = op[0], x = op[1], y = op[2];
            if (type == 0) {
                for (int j = 0; j < k; ++j) {
                    if ((arr[x] >> j & 1) == (y >> j & 1)) continue ;
                    if (!(y >> j & 1)) vec[j].insert(x);
                    else vec[j].erase(x);
                }
                arr[x] = y;
            } else {
                int res = 0;
                for (int j = 0; j < k; ++j) {
                    int start = y >> j & 1;
                    int odd = 1;
                    if (vec[j].empty()) {
                        if (x % 2 == 0 || n % 2 == 0) {
                            odd = 0;
                        }
                    } else {
                        start = 1;
                        
                        int last = n - 1 - *(vec[j].rbegin());
                        if (last % 2 == 0) {
                            odd = 0;
                        }
                    }
                    if (odd) start ^= 1;
                    if (start) res |= 1 << j;
                }
                ans ^= res;
            }
        }
        return ans;
    }
};

线段树实现：

// 线段树
const int N = 10010;
struct Node {
    int l, r, p;
}tr[30][N << 2];

vector<int> a;
int n;

void pushup(Node tr[], int u) {
    tr[u].p = max(tr[u << 1].p, tr[u << 1 | 1].p);
}

void build(Node tr[], int k, int u, int l, int r) {
    tr[u] = {l, r};
    if (l == r) {
        if (a[l] >> k & 1) tr[u].p = -1;
        else tr[u].p = l;
        return ;
    }
    int mid = (l + r) >> 1;
    build(tr, k, u << 1, l, mid);
    build(tr, k, u << 1 | 1, mid + 1, r);

    pushup(tr, u);
}

void modify(Node tr[], int k, int u, int x, int y) {
    if (tr[u].l == tr[u].r) {
        a[x] = y;
        if (a[x] >> k & 1) tr[u].p = -1;
        else tr[u].p = x;
        return ;
    }

    int mid = (tr[u].l + tr[u].r) >> 1;
    if (x <= mid) modify(tr, k, u << 1, x, y);
    else modify(tr, k, u << 1 | 1, x, y);
    pushup(tr, u);
}

class Solution {
public:

    int getNandResult(int k, vector<int>& arr, vector<vector<int>>& operations) {
        a = arr;
        n = a.size();
        for (int i = 0; i < k; ++i) build(tr[i], i, 1, 0, n - 1);

        int ans = 0;
        for (auto& u: operations) {
            int type = u[0], x = u[1], y = u[2];
            if (type == 0) {
                for (int i = 0; i < k; ++i) modify(tr[i], i, 1, x, y);
            } else {
                int res = 0;
                for (int i = 0; i < k; ++i) {
                    int last = tr[i][1].p;
                    int start = y >> i & 1;
                    int odd = 1;
                    if (last == -1) {
                        if (x % 2 == 0 || n % 2 == 0) {
                            odd = 0;
                        }
                    } else {
                        start = 1;
                        if ((n - 1 - last) % 2 == 0) {
                            odd = 0;
                        }
                    }
                    if (odd) start ^= 1;
                    if (start) res |= 1 << i;
                }
                ans ^= res;
            }
        }
        return ans;
    }
};

F. 万灵之树

鸽了