以下的代码均只给出了核心逻辑部分，并不是完整的代码。

同时代码中的 assert() 语句均为 std 编写过程中，充当validator的语句，提交时可以不写。

为了不产生歧义，这里给出以下代码的头文件部分：

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<ll, ll> P;
#define x first
#define y second
#define int long long

const int mod = 1e9 + 7;
const int pp = 998244353;

const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};

ll ksm(ll a, ll b, ll p) {
    ll ans = 1;
    a %= p;
    while(b) {
        if(b & 1) ans = (ans * a) % p;
        b >>= 1;
        a = (a * a) % p;
    }
    return ans % p;
}

A. 小苯的计算器

题意：

给定 ，把 表示成 的形式，满足

知识点：

模拟

题解：

简单模拟题，由于限制了 的范围，因此解是唯一的，即： 为 下取整， 为 。

void solve() {
    int a, b;
    cin >> a >> b;
    assert(a >= b);
    int k = a / b, c = a % b;
    cout << a << "=" << k << "*" << b << "+" << c << endl;
}

时间复杂度：单组

B. 小苯的括号疑问

题意：给定只含有 "" 和 "" 的括号串，其中有一些位置可能被反转了，问把括号复原成合法括号的方案是否唯一。

知识点：

思维

题解：

实际上会发现括号长什么样都无所谓，答案只和括号长度有关。那么容易发现只有长度为 的括号是有唯一解的，即：。

其次奇数一定无解。

再其次大于 的偶数也一定存在形如 "" 和 "" 这样的合法解，因此一定有多解。

代码：

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    if(n & 1) {
        cout << -1 << endl;
    } else if(n == 2) {
        cout << "()" << endl;
    } else {
        cout << "There are multiple solutions" << endl;
    }
}

时间复杂度：单组

C. 小苯的水果园

题意：

给定一个数组，第 秒删除所有出现了恰好 次的 们，问第 秒后数组的长度。

知识点：

前缀和

题解：

1. 期望解：

考虑用 存数字 的出现次数，再用 存所有出现了恰好 次的数字个数，对 数组做前缀和， 此时就变为了：出现次数不超过 的数字个数。此时我们就可以对所有询问 回答了。
需要注意的细节是 的询问需要和 取 。

void solve() {
    int n, q;
    cin >> n >> q;
    assert(n <= 2e5);
    assert(q <= 2e5);
    map<int, int> mp;
    for(int i = 1, x; i <= n; i++) {
        cin >> x;
        assert(x <= 1e6);
        mp[x] ++ ;
    }
    vector<int> cnt(n + 1);
    for(auto & [x, y] : mp) {
        cnt[y] += y;
    }
    for(int i = 1; i <= n; i++) {
        cnt[i] += cnt[i - 1];
    }

    while(q -- ) {
        int d;
        cin >> d;
        d = min(d, n);
        cout << n - cnt[d] << " ";
    }
    cout << endl;
}

时间复杂度：。 会带有 的复杂度。

2. 暴力解（优雅）

根据鸽笼原理，出现次数不同的数字最多 种，即最坏情况是形如：，数字 恰好出现了 次这样的。
因此我们可以对于每个数字只存一个出现次数，对所有的 {出现次数，这个出现次数的数字个数} 这样的对存入数组后排序（这个数组的长度最多 ），接着枚举 到 的每一个 ，直接暴力枚举看这个数组到什么时候会满足出现次数第一次大于 ，把这个位置之前的 "这个出现次数的数字个数" 全部加起来就是这个 的答案。把所有 的答案处理好，再 回答每一个询问。

时间复杂度：

（当然事实上这个暴力做法也可以用双指针来优化后面的枚举，因为注意到随着 的增大，这个 数组每次肯定会走的越来越深，因此是单调的，可以在枚举 时双指针求，依然可以做到 的复杂度，带 因为要排序。）

D. 小苯的数组最值

题意：

给定数组，再给定 个区间加操作，现在区间操作会随机等概的失效一个，求在此情况下数组最大值的期望。

知识点：

(前缀和、差分/线段树)，逆元，枚举

题解：

由于只有一个区间失效，我们考虑枚举那个失效的区间，因此我们先把所有的操作都操作上去（这里使用差分），再一个个地尝试撤销操作。

撤销时我们发现，如果一个区间完全包含了数组的所有最大值，那么撤销这个操作后一定会改变数组最大值，具体的：区间中的最大值 在撤销后变为了 ，而区间外的最大值不变，且实际上是一个前缀和一个后缀的最大值，即： 和 。此时数组的最大值即为以上三者的最大值。
否则如果当前撤销的区间不包含所有的最大值，那么撤销后是不影响数组最大值的，此时无所谓。

将所有可能的最大值都加起来，再除以 次操作就是期望，即乘上 的逆元。

代码：

void solve() {
    int n, q;
    cin >> n >> q;
    assert(n <= 5e5);
    assert(q <= 5e5);
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        assert(a[i] >= 1);
        assert(a[i] <= 1e9);
    }
    vector<int> b(n + 2);
    vector<int> L(n + 1), R(n + 1), D(n + 1);
    for(int i = 1; i <= q; i++) {
        cin >> L[i] >> R[i] >> D[i];
        assert(L[i] <= R[i]);
        assert(L[i] >= 1 && L[i] <= n);
        assert(R[i] >= 1 && R[i] <= n);
        b[L[i]] += D[i];
        b[R[i] + 1] -= D[i];
    }

    vector<int> pre(n + 1);
    for(int i = 1; i <= n; i++) {
        b[i] += b[i - 1];
        a[i] += b[i];
        pre[i] = max(pre[i - 1], a[i]);
    }
    vector<int> suf(n + 2);
    for(int i = n; i > 0; i--) {
        suf[i] = max(suf[i + 1], a[i]);
    }

    int ans = 0;
    for(int i = 1; i <= q; i++) {
        int l = L[i], r = R[i], d = D[i];
        if(pre[l - 1] == pre[n] || suf[r + 1] == suf[1]) {
          // 说明当前区间没有包含全部的数组最大值
            // cout << "no_cover_mx : " << i << endl;
            ans += pre[n];
        } else {
            ans += max(pre[n] - d, max(pre[l - 1], suf[r + 1]));
        }
        ans %= pp;
    }
    ans *= ksm(q, pp - 2, pp);
    ans %= pp;

    cout << ans << endl;
}

时间复杂度：。

E. 小苯的网络配置

题意：

给定无向图，对于每条边求其是否位于某个 到 的最短路上。

知识点：

图论，枚举

题解：

我们考虑 求最短路中的松弛操作，不难发现：对于每条边 ，如果此边在某条最短路上的话，则一定满足 ，即最短路从 到 ，再从 到 ，再从 到 。或者将 反过来的上式成立。这个条件反过来也成立，因此做法就呼之欲出了。

我们考虑先跑个从 出发的 ，预处理出 到所有点的最短路 ，再跑一个 出发的 ，求出 到所有点的最短路记作 。接着只需要枚举每条边 进行 即可。

代码：

void solve() {
    int n, m;
    cin >> n >> m;
    assert(n <= 3e5);
    assert(m <= 6e5);
    vector<vector<P>> g(n + 1);
    vector<array<int, 3>> edge(m + 1);
    for(int i = 1, u, v, w; i <= m; i++) {
        cin >> u >> v >> w;
        assert(u <= n && u >= 1);
        assert(v <= n && v >= 1);
        assert(w >= 1 && w <= 1e9);
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);

        edge[i][0] = u;
        edge[i][1] = v;
        edge[i][2] = w;
    }

    auto dijkstra = [&](int s) -> vector<int> {
        vector<int> d(n + 1, 1e18);
        priority_queue<P, vector<P>, greater<>> q;
        q.emplace(0, s);
        while(q.size()) {
            auto [dist, u] = q.top();
            q.pop();
            if(d[u] <= dist) continue;
            d[u] = dist;
            for(auto & [v, w] : g[u]) {
                if(d[v] > dist + w) {
                    q.emplace(dist + w, v);
                }
            }
        }
        return d;
    };

    auto d1 = dijkstra(1), dn = dijkstra(n);

    auto check = [&](int u, int v, int w) -> bool {
        return d1[n] == d1[u] + dn[v] + w;
    };

    for(int i = 1; i <= m; i++) {
        int u = edge[i][0], v = edge[i][1], w = edge[i][2];
        if(check(u, v, w) || check(v, u, w)) {
            cout << 1;
        } else {
            cout << 0;
        }
    }
    cout << endl;
}

复杂度： （瓶颈在 算法。）

F.小苯的糖果游戏

题意：两个人分别从一段不交的前缀和后缀中选两个子序列，满足子序列的和相同，问有多少种不同的选法。定义两种选法相同，当且仅当两种选法的子序列选择完全相同，同时两种选法的前后缀也完全相同；否则两种选法不同。

知识点：

背包 ，枚举。

题解：

我们考虑枚举最终游戏结束时，两人相邻的终点位置，我们枚举这个位置不妨记作 ，那么问题就变成了：我现在有一个长度为 的数组和一个长度为 的数组，我要从两者中分别取一些数字，使得和相等，有多少种取法，那么就变成了经典的背包，我们可以分解成一前一后两个部分，对前缀和后缀分别做背包，把最终答案加起来。

我们考虑先做一遍前缀的背包，但不滚动数组优化，记录成 ，表示考虑 这段前缀的，取一些数字的和为 的方案数。

记录好后我们再倒着枚举一遍，这一次可以用滚动数组优化了，不妨记作 数组，表示后缀考虑到当前位置时取出来的数字和为 的方案数（当然也是可以不用滚动优化的），正常做好背包后，在每一步都枚举一遍所有的 接着把答案加上一个 即可。

代码：

void solve() {
    int n;
    cin >> n;
    int s = 0;
    vector<int> a(n + 2, 1e9);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        s += a[i];
    }
    vector<vector<int>> dp(n + 1, vector<int>(s + 1));
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++) {
        dp[i] = dp[i - 1];
        for(int j = a[i]; j <= s; j++) {
            dp[i][j] = (dp[i][j] + dp[i - 1][j - a[i]]) % pp;
        }
    }

    ll ans = 0;
    vector<int> f(s + 1);
    f[0] = 1;
    for(int i = n + 1; i > 0; i--) {
        for(int j = s; j >= a[i]; j--) {
            f[j] = (f[j] + f[j - a[i]]) % pp;
        }
        for(int j = 0; j <= s; j++) {
            ans += 1LL * f[j] * dp[i - 1][j] % pp;
        }
    }
    ans %= pp;
    cout << ans << endl;
}

时间复杂度：。

G.小苯的神奇背包

题意：

给定物品(体积，价值) 数组，支持三种操作：

1.单点修物品体积
2.单点修物品价值
3.查询区间中的物品任意放入背包的最大价值
定义背包中物品的体积异或和 不为 就可以放入，总价值为价值的加法和。

知识点：

线段树，位运算（异或）

题解：

注意到物品体积均为非负数，因此加入更多的物品一定会更优，考虑最优情况，我们尝试将区间中所有物品都放入，此时如果区间物品的体积异或和不为 则一定最优，答案就是区间物品的价值和 。

因此贪心的，我们尽量把区间选满，但如果区间中物品的价值异或和恰好为 ，那么根据异或的性质，也容易想到我们只要扔掉一个最小的体积不为 的物品，就一定能改变整体的异或和，那么改变之后肯定不为 了。（如果读者不清楚为什么改变之后不是 ，请读者先学习异或运算性质）。

因此做法就比较明显了，我们用线段树维护：
区间物品的体积异或和 ；

区间物品的价值加法和 ；

以及区间中体积不为 的物品的最小价值 ；

即可完成本题。

代码：

int n, q;
vector<int> v, w;
struct Node {
    int l, r, sum, mn, xor_sum;
};
vector<Node> tr;

void push_up(int u) {
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    tr[u].xor_sum = tr[u << 1].xor_sum ^ tr[u << 1 | 1].xor_sum;
    tr[u].mn = min(tr[u << 1].mn, tr[u << 1 | 1].mn);
}

void build(int u, int l, int r) {
    if(l == r) {
        if(v[l] == 0) {
            tr[u] = {l, r, w[l], 1000000000000000000LL, v[l]};
        } else {
            tr[u] = {l, r, w[l], w[l], v[l]};
        }
    } else {
        tr[u] = {l, r};
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        push_up(u);
    }
}

void update(int u, int k, int x, int op) {
    if(tr[u].l == tr[u].r) {
        assert(tr[u].l == k);
        if(op == 1) {
            tr[u].xor_sum = x;
            if(tr[u].xor_sum == 0) {
                tr[u].mn = 1e18;
            } else {
                tr[u].mn = tr[u].sum;
            }
        } else {
            tr[u].sum = x;
            if(tr[u].xor_sum) {
                tr[u].mn = x;
            }
        }
        return ;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(k <= mid) {
        update(u << 1, k, x, op);
    } else {
        update(u << 1 | 1, k, x, op);
    }
    push_up(u);
}

Node ask(int u, int l, int r) {
    if(tr[u].l >= l && tr[u].r <= r) {
        return tr[u];
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(r <= mid) {
        return ask(u << 1, l, r);
    } else if(l > mid) {
        return ask(u << 1 | 1, l, r);
    }
    auto L = ask(u << 1, l, r);
    auto R = ask(u << 1 | 1, l, r);
    Node ans = {L.l, R.r, L.sum + R.sum, min(L.mn, R.mn), L.xor_sum ^ R.xor_sum};
    return ans;
}

void solve() {
    cin >> n >> q;
    tr.assign(4 * n + 1, {});
    v.assign(n + 1, 0);
    w.assign(n + 1, 0);
    for(int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }
    build(1, 1, n);
    while(q -- ) {
        int op;
        cin >> op;
        if(op < 3) {
            int k, x;
            cin >> k >> x;
            update(1, k, x, op);
        } else {
            int l, r;
            cin >> l >> r;
            auto res = ask(1, l, r);
            int ans = res.sum;
            if(res.xor_sum == 0) {
                ans -= res.mn;
            }
            ans = max(0LL, ans);
            cout << ans << endl;
        }
    }
}

时间复杂度： 就是朴素不带懒标的线段树的复杂度。

H. 小苯的数字成鸡

题意：

求 区间中满足：除个位数以外的数字的乘积恰好等于个位数位的数字个数。

知识点：数位 ，分类讨论

题解：

首先不难发现一件事，个位数不会超过 ，也就是说前面很多数字的乘积不会超过 ，这实际上是一个比较强的限制，让我们可以直接给出 数组的状态设置： 表示目前填到第 位，前面的数字乘积为 ，最后一个填的数字为 的数字个数。（这里的 是从高位到低位填的。）

可以放心的开成 这样一来状态数不超过 个。

接着我们可能会放心地顺手写出形如： 的记忆化搜索，

（其中 维护当前填的数位的乘积， 维护填的最后一个数位， 表示是否填到顶格， 表示当前是否还在填前导 。）

其中由于 不会超过 ，因此我们可能会有一些形如 的特判。
最终发现也通过了样例，但提交却获得了 的反馈。

事实上这是因为，我们没有考虑 这一类的数字，它同样也是符合要求的，但注意到他的前缀 在考虑到前 位时会得到最坏为 的结果，这样的 被我们上述的 直接跳过了统计，因此我们的答案比正确答案要少。

因此正确的方式是，首先还是先做一次上述的 ，但我们只考虑 的情况，统计出答案后。我们再考虑 的情况，那我们会发现由于 为 ，因此这个数字一定是末尾为 的，我们干脆直接将 去除以 下取整，用这个结果跑一边另一个数位 ，另一个什么数位 呢？
实际上就是：数位中只要含有 就合法。
因此我们实际上要做两个不同的数位 ，并将这两者的答案加起来，由于两者考虑的 值域完全不同，因此一定是不重不漏的。

（当然，验题时也有验题人给出了只需要一次 的做法，读者可以自行思考。）

代码

int dp1[20][11][11], dp2[20][2];

void solve() {
    int L, R;
    cin >> L >> R;

    string s;
    auto dfs1 = [&](auto && self, int u, int mul, int choose, bool limit, bool lead0) -> int {
        if(u == s.size()) {
            return lead0 == 0 && choose != -1 && choose == mul;
        }
        if(limit == 0 && lead0 == 0 && dp1[u][mul][choose] != -1) return dp1[u][mul][choose];
        int ans = 0;
        int up = limit ? (s[u] - '0') : 9;
        for(int i = 0; i <= up; i++) {
            if(lead0 && i == 0) {
                ans += self(self, u + 1, -1, -1, limit & (i == up), 1);
            } else if(i > 0) {
                if(choose == -1) {
                    ans += self(self, u + 1, -1, i, limit & (i == up), lead0 & (i == 0));
                } else {
                    if(mul == -1) {
                        ans += self(self, u + 1, choose, i, limit & (i == up), lead0 & (i == 0));
                    } else if(mul * choose <= 9) {
                        ans += self(self, u + 1, mul * choose, i, limit & (i == up), lead0 & (i == 0));
                    }
                }
            }
        }
        if(limit == 0 && lead0 == 0) dp1[u][mul][choose] = ans;
        return ans;
    };

    auto dfs2 = [&](auto && self, int u, bool zero, bool limit, bool lead0) -> int {
        if(u == s.size()) {
            return lead0 == 0 && zero;
        }
        if(!lead0 && !limit && dp2[u][zero] != -1) return dp2[u][zero];
        int ans = 0;
        int up = limit ? (s[u] - '0') : 9;
        for(int i = 0; i <= up; i++) {
            if(lead0 && i == 0) {
                ans += self(self, u + 1, 0, limit & (i == up), 1);
            } else {
                ans += self(self, u + 1, zero | (i == 0), limit & (i == up), lead0 & (i == 0));
            }
        }
        if(!lead0 && !limit) dp2[u][zero] = ans;
        return ans;
    };

    auto get = [&](int x) -> int {
        s = to_string(x);
        memset(dp1, -1, sizeof dp1);
        int ans = dfs1(dfs1, 0, -1, -1, 1, 1);
        memset(dp2, -1, sizeof dp2);
        s.pop_back(); // x /= 10; 的效果
        ans += dfs2(dfs2, 0, 0, 1, 1);
        return ans;
    };

    cout << get(R) - get(L - 1) << endl;

    // auto check = [&](int x) -> bool {
    //     if(x < 11) return 0;
    //     int mul = 1, back = x % 10;
    //     // if(back == 0) return 0;
    //     x /= 10;
    //     while(x) {
    //         mul *= (x % 10);
    //         x /= 10;
    //     }
    //     // if(mul == 0) return 0;
    //     return back == mul;
    // };

    // // b-f 暴力做法对拍
    // int ans1 = 0;
    // for(int i = L; i <= R; i++) {
    //     if(check(i)) {
    //         ans1 ++ ;
    //         // cerr << i << ", ";
    //     }
    // }
    // cerr << endl;
    // cerr << ans1 << endl;
}

时间复杂度：，复杂度没有展现出第二个 的复杂度，原因是其相当于第一个 几乎可以忽略不计，对于第一个 来说， 是 的数位长度，三个 中的前两个分别是 和 的取值范围，也就是 的状态个数，第三个 是转移的边数。

（这个复杂度实际上也是上限，真实情况跑不到这么多。）

Thanks