第 121 场 LeetCode 双周赛题解

A 大于等于顺序前缀和的最小缺失整数

模拟：先求最长顺序前缀的和 $s$ ，然后从 $s$ 开始找没有出现在 $nums$ 中的最小整数

class Solution {
public:
    int missingInteger(vector<int> &nums) {
        unordered_set<int> vis(nums.begin(), nums.end());
        int s = nums[0];
        int i = 0;
        while (i + 1 < nums.size() && nums[i + 1] == nums[i] + 1)
            s += nums[++i];
        while (vis.count(s))
            s++;
        return s;
    }
};

---

B 使数组异或和等于 K 的最少操作次数

枚举：求出 $nums$ 各元素异或和 $tot$ ，对 $tot$ 和 $k$ 的二进制表示按位枚举，若两数某一位不同，则需要增加一次操作数

class Solution {
public:
    int minOperations(vector<int> &nums, int k) {
        int tot = 0;
        for (auto x: nums)
            tot ^= x;
        int res = 0;
        for (int i = 0; i < 32; i++)
            if ((tot >> i & 1) != (k >> i & 1))
                res++;
        return res;
    }
};

---

C 使 X 和 Y 相等的最少操作次数

bfs：相当于求从 $x$ 出发到 $y$ 的最短路，搜素过程中用集合记录已经到达过的数

class Solution {
public:
    int minimumOperationsToMakeEqual(int x, int y) {
        unordered_set<int> vis;
        queue<pair<int, int>> q;
        vis.insert(x);
        q.emplace(x, 0);
        int res;
        while (!q.empty()) {
            auto [v, cnt] = q.front();
            q.pop();
            if (v == y) {
                res = cnt;
                break;
            }
            if (v > y && v % 11 == 0 && !vis.count(v / 11)) {
                vis.insert(v / 11);
                q.emplace(v / 11, cnt + 1);
            }
            if (v > y && v % 5 == 0 && !vis.count(v / 5)) {
                vis.insert(v / 5);
                q.emplace(v / 5, cnt + 1);
            }
            if (!vis.count(v + 1)) {
                vis.insert(v + 1);
                q.emplace(v + 1, cnt + 1);
            }
            if (v > y && !vis.count(v - 1)) {
                vis.insert(v - 1);
                q.emplace(v - 1, cnt + 1);
            }
        }
        return res;
    }
};

---

D 统计强大整数的数目

数位dp + 记忆化搜素：定义 $cmp(x,mx,suf)$ 为不超过 $x$ 且数中各数位不超过 $mx$ 且数的末尾部分是 $suf$ 的数的数目，则题目答案为 $cmp(finish,limit,s)?cmp(start?1,limit,s)$ 。在 $cmp$ 中定义 $p[loc][val][eq]$ 为：当前枚举下标为 $loc$ 且 之前位置对应的数位是否有数字（0：无，1：有）且 之前位置对应的数位的数字形成的前缀是否和 $x$ 对应的前缀相等（0：不等，1：相等），这种情况下末尾部分是 $suf$ 的数的数目，通过记忆化搜素枚举状态转移的过程，最终 $cmp(x,mx,suf)$ 即为 $p[0][0][1]$ ，

class Solution {
public:
    using ll = long long;

    long long numberOfPowerfulInt(long long start, long long finish, int limit, string s) {
        return cmp(finish, limit, s) - cmp(start - 1, limit, s);
    }

    ll cmp(ll x, int mx, string &suf) {
        if (x < stol(suf))
            return 0;
        string s0 = to_string(x);
        int n = s0.size();
        int m = suf.size();
        ll suf0 = stol(s0.substr(n - m, m));//x与suf相同长度的末尾部分
        ll vsuf = stol(suf);
        ll p[n][2][2];
        memset(p, -1, sizeof(p));
        function<ll(int, int, int)> get = [&](int loc, int val, int eq) {//记忆化搜素
            if (p[loc][val][eq] != -1)
                return p[loc][val][eq];
            if (n - loc == m) {//loc已经为suf的第一位
                if (suf0 >= vsuf || eq == 0)
                    p[loc][val][eq] = 1;
                else //末尾若是suf则会大于x，所以不存在这样的数
                    p[loc][val][eq] = 0;
                return p[loc][val][eq];
            }
            p[loc][val][eq] = 0;
            if (val) {//之前位置对应的数位有数字
                if (eq) {//之前位置对应的数位的数字形成的前缀和x对应的前缀相等
                    for (int i = 0; i <= s0[loc] - '0' && i <= mx; i++)
                        p[loc][val][eq] += get(loc + 1, 1, i == s0[loc] - '0' ? 1 : 0);
                } else {//之前位置对应的数位的数字形成的前缀和x对应的前缀不等
                    for (int i = 0; i <= mx; i++)
                        p[loc][val][eq] += get(loc + 1, 1, 0);
                }
            } else {//之前位置对应的数位无数字
                if (eq) {//之前位置对应的数位的数字形成的前缀和x对应的前缀相等
                    p[loc][val][eq] += get(loc + 1, 0, 0);//当前数位没有数字
                    for (int i = 1; i <= s0[loc] - '0' && i <= mx; i++)
                        p[loc][val][eq] += get(loc + 1, 1, i == s0[loc] - '0' ? 1 : 0);
                } else {//之前位置对应的数位的数字形成的前缀和x对应的前缀不等
                    p[loc][val][eq] += get(loc + 1, 0, 0);//当前数位没有数字
                    for (int i = 1; i <= mx; i++)
                        p[loc][val][eq] += get(loc + 1, 1, 0);
                }
            }
            return p[loc][val][eq];
        };
        return get(0, 0, 1);
    }
};