补题链接：https://ac.nowcoder.com/acm/contest/103864以下的代码均只给出了核心逻辑部分，并不是完整的代码。同时代码中的 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 longconst 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 L, R, k = 3;    cin >> L >> R;    assert(L >= 1);    assert(L <= R);    assert(R <= 2000);    assert(k <= 2000);    if(R / k - (L - 1) / k > 0) {        cout << "YES" << endl;    } else {        cout << "NO" << endl;    }}时间复杂度：单组 B. 小苯的迷宫行走题意：给定一个面积为 奇数 的矩阵，要从左上角出发走到右下角，每一步可以走到上下左右四个相邻的位置上，每个点都只能经过最多一次，要求最大化所有走过的点的  的按位或值，求这个最大的按位或是多少。知识点：位运算，构造，贪心题解：实际上，当  和  中任意一个为奇数时，我们总能找到一条路径使得他能把所有点都走过恰好一遍，路径大概长成一个 “”  型，或者是横躺着的 “” 型。而题目限定了面积是奇数，则  都是奇数，因此我们一定可以通过走 “” 把 所有点 经过一次。而位运算  的性质则是越  越大，既然我们有办法将所有格子都走一遍的同时走到终点，因此我们直接将所有输入的数字都  起来即可。代码：void solve() {    int n, m;    cin >> n >> m;    assert(n <= 4000);    assert(m <= 4000);    assert((n * m) & 1);    int ans = 0;    for(int i = 0, x; i < n * m; i++) {        cin >> x;        assert(x <= 1e9);        assert(x >= 0);        ans |= x;    }    cout << ans << endl;}时间复杂度：C.小苯的好数题意：定义  是所有严格小于  的因子之和，例如 ，定义好数是： 是个偶数。知识点：数学，前缀和题解：首先不难发现偶数一定是好数，因为如果  是偶数则  一定是偶数。那么此时我们考虑可能的奇数，这里我们可以将奇数的因子以一对一对的形式写出，例如 。我们会发现，奇数一定是 奇数 奇数 得到的，而由于这些因子都是成对出现，因此如果将  的所有因子相加，其结果应该是 “偶数个奇数” 相加，则结果应该是偶数。但实际上我们会发现特例就在于，如果  是一个奇完全平方数，即存在正整数  使得 ，那么此时上述提到的一对对 奇数 奇数 的总和就会少一个奇数，会使得结果从偶数变成奇数，因此完全平方数是特例。但我们本题天然的会少一个最大的奇数因子，即  本身，因此其结论也是反过来的，也就是说对于奇数 ，当且仅当其是完全平方数，其才是好数。得到了上述的结论，则我们存每个数字是不是好数，用前缀和优化查询即可。代码：void solve() {    int n, q;    cin >> n >> q;    vector<int> s(n + 1);    auto check = [&](int x) -> bool {        if(x % 2 == 0) return 1;        int sq = sqrt(x);        return sq * sq == x;    };    for(int i = 1, x; i <= n; i++) {        cin >> x;        s[i] = s[i - 1] + check(x);    }    while(q -- ) {        int l, r;        cin >> l >> r;        cout << s[r] - s[l - 1] << endl;    }}时间复杂度：。D. 小苯的 题意：给定长度为  的  串，保证只由  和  两种字符构成，至多选择  个位置改变字符从  到 ； 到 ，问最多可以产生多少个不相交的 "" 子串。知识点：题解：不难想到，可以定义  表示考虑到前  个位置的时候，操作了  次最多子串个数。则我们直接枚举  转移即可，这里思考下就会发现，我们可以给  数组加一个限制为：最后一个 "" 子串一定是  这个子串修改得到的，这样一来  的转移将十分简单，我们求出把最后三个字符改成 "" 的花费 ，接着从  的状态转移过来即可，具体的见代码。代码：void solve() {    int n, k;    string s;    cin >> n >> k >> s;    if(n < 3) {        cout << 0 << endl;        return ;    }    s = " " + s;        vector<vector<int>> dp(n + 1, vector<int>(k + 1, -1e9));    dp[0][0] = dp[1][0] = dp[2][0] = 0;    for(int i = 3; i <= n; i++) {        int cost = (s[i - 2] != 'o') + (s[i - 1] != 'v') + (s[i] != 'o');        dp[i] = dp[i - 1];        for(int j = cost; j <= k; j++) {            dp[i][j] = max(dp[i][j], dp[i - 3][j - cost] + 1);        }    }    cout << *max_element(dp[n].begin(), dp[n].end()) << endl;}当然，不要忘记特判  的情况。时间复杂度：（当然，本题可以使用  二分的做法优化到 ，难度不低，这里不详细展开了。）E. 小苯的水瓶题意：给定  个水瓶，每个水瓶一开始装了一些水，现在可以：  任选一些水瓶对 ，把  中的水倒入  中，使用这个操作最多倒出  单位水；  另有一个水壶可以给任意瓶子倒水，使用这个操作最多倒出  单位的水。求装水量最少的瓶子最多能装多少水。知识点：二分，贪心题解：首先不难发现答案有单调性，因此考虑二分答案。那么对于一个答案 ，如何  其是否合法，我们只需要贪心即可，方便起见我们对数组排序，首先把超过  的那些水瓶中的水倒入不够  的那些水瓶中，这一步可以双指针实现，也可以简单枚举实现。接着我们只需要看所有瓶子中不够  的需求量是否在  以内即可，直接枚举一遍就行，如果在  以内则合法。需要注意的是，本题如果无脑倒水的话在实现上可能会爆 ，因此还是建议读者在上述的 ”判断不够  的瓶子中缺的水量是否够  时“ 加上判断，如果超过  可以直接 。（下方的代码中并没有这一点，因此开了  防止爆  了。）代码：void solve() {    int n, m, k;    cin >> n >> m >> k;    assert(n <= 2e5);    assert(m <= 2e14);    assert(k <= 2e14);    vector<int> a(n + 1);    for(int i = 1; i <= n; i++) {        assert(a[i] >= 0 && a[i] <= 1e9);        cin >> a[i];    }    sort(a.begin() + 1, a.end());    auto check = [&](int mid) -> bool {        auto b = a;        int s = 0;        for(int i = n; i > 0; i--) {            s += max(0LL, b[i] - mid);            b[i] = min(mid, b[i]);        }        s = min(s, m);        for(int i = 1; i <= n; i++) {            int sub = max(0LL, mid - b[i]);            if(sub <= 0) continue;            if(s >= sub) {                s -= sub;                b[i] = mid;            } else {                b[i] += s;                s = 0;                break;            }        }        lll K = k; // 注意K有可能会爆longlong        for(int i = 1; i <= n; i++) {            K -= max(0LL, mid - b[i]);        }        return K >= 0;    };    int l = 0, r = 1e16;    while(l < r) {        int mid = (l + r + 1) >> 1;        if(check(mid)) l = mid;        else r = mid - 1;    }    cout << l << endl;}复杂度：，其中  为二分的上限。F.小苯的旅行计划题意：给定一棵带边权树，另有  个点对 ，表示要花费 ，即花费： 走到  最短路路径上的边权和。现在最多可以使得一条边免费，求总花费的最小值。知识点：树上差分，枚举，题解：实际上做法十分明显，我们考虑枚举那个免费的边，想一想其对答案的影响是什么，实际上就是，如果它免费，则答案会减少所有经过它的  点对数  它的边权。它的边权我们已知，那么我们的问题转为了如何求经过一条边的点对数量，这里我们使用  对每个输入的点对做一个树上边差分即可，做好后枚举免费的边，取最优答案即可。难点在于代码实现上的细节，有同学可能只会做树上点差分，实际上边差分是一样的只需要把边权下放给  中更深点的点权即可。代码：void solve() {    int n, m;    cin >> n >> m;    assert(n <= 1e5);    assert(m <= 2e5);    vector<vector<P>> g(n + 1);    struct Edge {        int u, v, w;    };    vector<Edge> edge;    for(int i = 0, u, v, w; i < n - 1; i++) {        cin >> u >> v >> w;        assert(u >= 1 && u <= n);        assert(v >= 1 && v <= n);        assert(u != v);        assert(1 <= w <= 1e9);        g[u].emplace_back(v, w);        g[v].emplace_back(u, w);        edge.push_back({u, v, w});    }    vector<vector<int>> f(20, vector<int>(n + 1));    vector<int> dep(n + 1), sum(n + 1); // sum记录深度和树上前缀的边权和，为了算出任何边都不免费的答案    auto dfs1 = [&](auto && self, int u, int fa) -> void {        dep[u] = dep[fa] + 1;        f[0][u] = fa;        for(int j = 1; j < 20; j++) {            f[j][u] = f[j - 1][f[j - 1][u]];        }        for(auto & [v, w] : g[u]) {            if(v == fa) continue;            sum[v] = sum[u] + w; // 树上边权前缀和            self(self, v, u);        }    };    dfs1(dfs1, 1, 0);    auto LCA = [&](int u, int v) -> int {        if(dep[u] < dep[v]) swap(u, v);        for(int j = 19; j >= 0; j--) {            if(dep[f[j][u]] >= dep[v]) {                u = f[j][u];            }        }        if(u == v) return u;        for(int j = 19; j >= 0; j--) {            if(f[j][u] != f[j][v]) {                u = f[j][u];                v = f[j][v];            }        }        return f[0][u];    };    int cost = 0; // 一条边都不免费的答案    vector<int> s(n + 1);    for(int i = 0, a, b; i < m; i++) {        cin >> a >> b;        assert(a >= 1 && a <= n);        assert(b >= 1 && b <= n);        int lca = LCA(a, b);        s[a] ++ ;        s[b] ++ ;        s[lca] -= 2; // 树上边差分，把边权下放给点        cost += (sum[a] + sum[b] - 2 * sum[lca]); // 算出原本的边权前缀和    }    auto dfs2 = [&](auto && self, int u, int fa) -> void {        for(auto & [v, w] : g[u]) {            if(v == fa) continue;            self(self, v, u);            s[u] += s[v]; // 树上前缀和还原差分的结果        }    };    dfs2(dfs2, 1, 0);    int mx = 0; // 记录免费一条边后减少的价值最大值    for(auto & [u, v, w] : edge) {        if(dep[u] < dep[v]) swap(u, v); // 更深那一个点的点权才是这条边的真实边权        mx = max(mx, s[u] * w);        // s[u] 是 u 被所有朋友经过的总次数，w 是这条边的权，乘起来就是这条边免费后能省下来的钱    }    cout << cost - mx << endl; // 答案就是原本的花费减去省的最多的}时间复杂度：。G.小苯的奇怪最短路题意：给定带权无向图，求  到  的最短路，但最短路定义为经过的边里边权 最小 的边加上边权 最大 的边。知识点：思维，并查集， 最小生成树，枚举，贪心题解：让我们考虑枚举答案中的最大边 ，那么问题变成了最小边如何求。让我们考虑最小生成树的求法，在合并连通块的过程中，如果  连通则我们直接跳过，否则连上边，并给总权加上  的权。在本题中实际上也类似，我们给每个连通块都维护一个当前连通块中的最小边 ，接着正常执行  求最小生成树，如果当前  和  已经连通，则我们就对  所在的连通块的最小边  加上当前边  取  即可，在过程中要一直维护每个连通块中最小边的权 。代码：void solve() {    int n, m;    cin >> n >> m;    assert(n <= 3e5);    assert(m <= 5e5);    vector<int> fa(n + 1), mn(n + 1, 1e18);    iota(fa.begin(), fa.end(), 0LL);    auto find = [&](int x) -> int {        while (x != fa[x]) x = fa[x] = fa[fa[x]];        return x;    };    auto merge = [&] (int u, int v, int w) -> bool {        u = find(u);        v = find(v);        fa[v] = u;        mn[u] = min(mn[u], mn[v]);        mn[u] = min(mn[u], w);        return 1;    };    struct E {        int u, v, w;        bool operator<(const E & e) const {            return w < e.w;        }    };    vector<E> edge;    for(int i = 0, u, v, w; i < m; i++) {        cin >> u >> v >> w;        edge.push_back({u, v, w});    }    sort(edge.begin(), edge.end());        int ans = 1e18;    for(auto & [u, v, w] : edge) {        merge(u, v, w);        if(find(1) == find(n)) {            ans = min(ans, mn[find(1)] + w);        }    }    if(ans > 1e17) ans = -1;    cout << ans << endl;}时间复杂度：。（瓶颈在对边排序）H. 小苯的矩阵变换题意：给定  个  矩阵，计算排列  的个数，满足这些矩阵按照  的顺序放置后，对任意位置都满足：第  号矩阵是由第  号矩阵通过  了某一行或者某一列得到的。并且最后一个矩阵一定是全  的。知识点：模拟建图，状压  计数。题解：首先我们考虑可以两两枚举矩阵建图，如果  可以通过  操作得到 ，则我们建一条  之间的双向边，同时我们找到所有全  矩阵的编号，记作  数组。接着问题变为了，对于  个点的一张无向图，求有多少条哈密顿路径的终点是  中的某个。事实上我们反着考虑，用  中所有点当做起点的效果是一样的。因此我们定义数组：状压  表示目前已经走过的点状态为 ，且最后一个点是  的总方案数，枚举状态和结尾点转移即可，最终答案即为  的所有第二维之和。初始化我们只需要把所有  中的点都当一次起点即可，即：。代码void solve() {    int n, m, k;    cin >> n >> m >> k;    assert(n <= 100);    assert(m <= 100);    assert(k <= 15);    k ++ ;    vector<vector<string>> g(k, vector<string>(n + 1));        vector<int> S;    for(int c = 0; c < k; c++) {        bool white = 1;        for(int i = 1; i <= n; i++) {            string s;            cin >> s;            s = " " + s;            g[c][i] = s;            for(int j = 1; j <= m; j++) {                white &= (g[c][i][j] == '0');            }        }        if(white) {            S.emplace_back(c);        }    }    if(S.empty()) {        cout << 0 << endl;        return ;    }    // vector<vector<int>> adj(k, vector<int>(k));    vector<vector<int>> adj(k);    auto addEdge = [&](int u, int v) -> bool {        vector<vector<int>> mp(n + 1, vector<int>(m + 1));        int sx = 0, sy = 0;        int ex = 0, ey = 0;        int cnt = 0;        for(int i = 1; i <= n; i++) {            for(int j = 1; j <= m; j++) {                int x = ((g[u][i][j] - '0') ^ (g[v][i][j] - '0'));                mp[i][j] = x;                if(sx == 0 && x) {                    sx = i;                    sy = j;                }                if(x) {                    cnt ++ ;                    ex = i;                    ey = j;                }            }        }        if(sx == ex && cnt == m) {            for(int j = sy; j <= ey; j++) {                if(mp[sx][j] == 0) return 0;            }            // adj[u][v] = adj[v][u] = 1;            adj[u].emplace_back(v);            adj[v].emplace_back(u);            return 1;        } else if(sy == ey && cnt == n) {            for(int i = sx; i <= ex; i++) {                if(mp[i][sy] == 0) return 0;            }            adj[u].emplace_back(v);            adj[v].emplace_back(u);            // adj[u][v] = adj[v][u] = 1;            return 1;        }        return 0;    };    for(int u = 0; u < k; u++) {        for(int v = u + 1; v < k; v++) {            if(addEdge(u, v)) {                // cerr << u << "-" << v << endl;            }        }    }        vector<vector<int>> dp(1 << k, vector<int>(k));        for(auto & s : S) {        dp[1 << s][s] = 1;    }    for(int i = 1; i < 1 << k; i++) {        for(int j = 0; j < k; j++) {            if(dp[i][j] == 0) continue;            if((i >> j & 1) == 0) continue;            for(auto & nxt : adj[j]) {                if((i >> nxt & 1) == 0) {                    dp[i | (1 << nxt)][nxt] += dp[i][j];                }            }        }    }    int ans = 0;    for(int e = 0; e < k; e++) {        ans += dp[(1 << k) - 1][e];    }    cout << ans << endl;}时间复杂度：。（只是上限，实际上跑不到最坏情况）Thanks