题解 | 2026湖北工业大学校赛题解

Problem A. 奶龙大战贝利亚 II

题目大意

在一个 $n \times m$ 的棋盘上，初始有一枚棋子在左上角 $(1, 1)$ 。两名玩家轮流操作，每次只能将棋子向右或向下移动任意正整数格，不能不移动，不能出界。无法移动者判负。奶龙先手，双方最优策略下判断奶龙是否能获胜。

基本思路

解法一：构造

注意到，每次先手移动后，如果棋子不在终点所在的对角线上，后手就能一步让棋子走到该对角线上，这样最终后手会将棋子走到 $(n,m)$ 而获取胜利。所以只有当 $n \ne m$ 时，奶龙可以将棋子走到对角线上，从而奶龙有必胜法，否则贝利亚有必胜法，时间复杂度 $O(1)$ .

解法二：nim博弈

其实可以发现，每个操作只会影响到一个值，即对行的操作和对列的操作独立，于是该问题和有两堆石子的nim博弈等价。由nim博弈的结论可知：当 $n \oplus m = 0$ 时，后手必胜，否则先手必胜。

考察知识

博弈论
构造

参考实现

#include<bits/stdc++.h>
using i64 = long long;

int main(){
    std::cin.tie(0)->sync_with_stdio(0);
    int T = 1;
    std::cin >> T;
    while(T--){
        i64 n,m;
        std::cin >> n >> m;
        std::cout << (n == m ? "NO" : "YES") << "\n";
    }
    return 0;
}

Problem B. MaxPooling

题目大意

给定一个 $n \times m$ 的矩阵 $A$ 和一个大小为 $p \times q$ 的池化窗口，步长为1滑动。计算并输出每个窗口内元素的最大值构成的新矩阵 $B$ 。

基本思路

在一维数组中，求长度为 $k$ 的滑动窗口最大值，可以使用单调队列在 $O(n)$ 时间内完成

在二维数组中，可以有类似于二维前缀和的思路，对每一行，用单调队列求出长度为 $q$ 的滑动窗口最大值，得到中间矩阵 $C$ 。再对 $C$ 的每一列，用单调队列求出长度为 $p$ 的滑动窗口最大值，得到最终矩阵 $B$ 。时间复杂度 $O(nm)$ 。

需要注意两次单调队列的循环次数以及最后输出维度不要搞错了。

考察知识

单调队列

参考实现

#include<bits/stdc++.h>
using i64 = long long;

int main(){
	std::cin.tie(0)->sync_with_stdio(0);
    i64 n,m,p,q;
    std::cin >> n >> m >> p >> q;
    std::vector<std::vector<i64>> a(n,std::vector<i64>(m));
    std::vector<std::vector<i64>> ta(n),ans(m - q + 1);

    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            std::cin >> a[i][j];
        }
    }

    for(int i = 0;i < n;i++){
        std::deque<i64> dq;
        for(int j = 0;j < m;j++){
            if(!dq.empty() && j - dq.front() >= q) dq.pop_front();
            while(!dq.empty() && a[i][dq.back()] <= a[i][j]){
                dq.pop_back();
            }
            dq.push_back(j);
            if(q <= j + 1) ta[i].push_back(a[i][dq.front()]);
        }
    }
    
    for(int j = 0;j < m - q + 1;j++){
        std::deque<i64> dq;
        for(int i = 0;i < n;i++){
            if(!dq.empty() && i - dq.front() >= p) dq.pop_front();
            while(!dq.empty() && ta[dq.back()][j] <= ta[i][j]){
                dq.pop_back();
            }
            dq.push_back(i);
            if(p <= i + 1) ans[j].push_back(ta[dq.front()][j]);
        }
    }

    for(int j = 0;j < n - p + 1;j++){
        for(int i = 0;i < m - q + 1;i++){
            std::cout << ans[i][j] << " \n"[i == m - q];
        }
    }
	return 0;
}

Problem C. 拉电线

题目大意

一条数轴上 0 点处有电源，有 $n$ 个位置有矿点，现在另外有 $k$ 个额外的中继器可以放置。两个点之间距离 $\le m$ 时即可连通电线。求在合理放置不超过 $k$ 个中继器的情况下，使电源和所有矿点连通的最小距离上限 $m$ 。

基本思路

电线越长时，所需要的中继器越少。所以可以二分电线长度，然后在check里面遍历每个中继器与前一个中继器的距离，贪心的放置中继器，即设第 $i$ 个中继器与第 $i - 1$ 个中继器距离为 $d_i = x_i - x_{i-1}$ ，二分的最大电线长度为 $mid$ 时，需要放置中继器 $\left \lceil \frac{d_i}{mid} \right \rceil - 1$ 个。时间复杂度 $O(n \log n)$ 。

需要注意二分的下界问题，由于每个矿点初始是有一个中继器并且所有矿点的位置不重复，所以电线最短长度是 $1$ ，并非 $0$ ，如果将下界设为 $0$ ，则在check的时候有可能出现除零错误。

考察知识

二分答案
贪心

参考代码

#include<bits/stdc++.h>
using i64 = long long;

int main(){
	std::cin.tie(0)->sync_with_stdio(0);
    int T = 1;
    std::cin >> T;
    while(T--){
        i64 n,k;
        std::cin >> n >> k;
        std::vector<i64> a(n + 1);
        for(int i = 1;i <= n;i++){
            std::cin >> a[i];
        }
        std::sort(a.begin(),a.end());
        
        auto check = [&](i64 x) -> bool{
            i64 cnt = 0;
            for(int i = 1;i <= n;i++){
                cnt += (a[i] - a[i - 1] + x - 1) / x - 1;
                if(cnt > k) return false;
            }
            return true;
        };
        
        i64 l = 1,r = a[n],ans = 1;
        while(l <= r){
            i64 mid = (l + r) >> 1;
            if(check(mid)){
                r = mid - 1;
                ans = mid;
            }
            else l = mid + 1;
        }
        std::cout << ans << "\n";
    }
	return 0;
}

Problem D. 神秘城堡

题目大意

穗龙从房间 $0$ 出发，按顺序依次访问房间 $1$ 到 $n$ ，在每个房间都必须选择一种操作：

收集
a) 获得该房间全部水晶
b) 然后扣除一定量水晶
跳过
a) 不获得水晶
b) 然后扣除一定量水晶

约束：不能连续跳过 $3$ 个或更多房间

停止规则：可以在离开任意房间后停止，然后带走收集到的全部水晶（当然也可以不进入任何房间直接离开）

目标：最大化最终带走的水晶数，并在这个前提下保证最早离开城堡

基本思路

动态规划。从房间 $1$ 到 $n$ 依次决定“收集”还是“跳过”。
设 $dp[i][j]$ 表示考虑了前 $i$ 个房间，且当前已经连续跳过了 $j$ 个房间时，口袋里的最大水晶数。
其中 $0 \le i \le n$ ， $0 \le j \le 2$ 。

状态转移时，从状态 $dp[i-1][j]$ 出发，考虑第 $i$ 个房间：

选择收集（连续跳过状态重置）
$dp[i][0] = \max\left(dp[i][0],\ (dp[i-1][j] + w) - \left\lfloor \frac{(dp[i-1][j] + w) \cdot p + 99}{100} \right\rfloor\right)$
选择跳过（仅当 $j < 2$ 时允许）
$dp[i][j+1] = \max\left(dp[i][j+1],\ dp[i-1][j] - \left\lfloor \frac{dp[i-1][j] \cdot k + 99}{100} \right\rfloor\right)$

初始化时水晶数为 $0$ 。

其他：本题此解法空间复杂度为 $3 \cdot n$ ，但注意到任意房间的状态仅与前一房间状态相关，因此空间上可以优化到 $3 \times 2$ ，即 $O(1)$ 的复杂度，时间复杂度为 $O(n)$ 。

考察知识

动态规划

参考代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
typedef long long ll;
const ll INF = -1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll T; cin >> T;
    while (T--) {
        int n, k;
        cin >> n >> k;
        vector<int> w(n + 1), p(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> w[i] >> p[i];
        }
        vector<vector<ll>> dp(n + 1, vector<ll>(3, INF));
        dp[0][0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= 2; j++) {
                if (dp[i - 1][j] < 0) continue;

                // 选择收集
                ll total = dp[i - 1][j] + w[i];
                ll loss = (total * p[i] + 99) / 100;
                ll new_val = total - loss;
                dp[i][0] = max(dp[i][0], new_val);

                // 选择跳过
                if (j < 2) {
                    ll loss_skip = (dp[i - 1][j] * k + 99) / 100;
                    ll new_val_skip = dp[i - 1][j] - loss_skip;
                    dp[i][j + 1] = max(dp[i][j + 1], new_val_skip);
                }
            }
        }
        ll ans = 0;
        int ans_pos = 0;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= 2; j++) {
                if (dp[i][j] > ans) {
                    ans = dp[i][j];
                    ans_pos = i;
                } else if (dp[i][j] == ans && i < ans_pos) {
                    ans_pos = i;
                }
            }
        }
        cout << ans << " " << ans_pos << endl;
    }
    return 0;
}

Problem E. 奶龙的棋局

题目大意

给定数轴上的 $N$ 个递增坐标 $X_i$ 。可以对连续 4 个棋子操作：将中间两个关于两边坐标的中点对称移动。求操作任意次后这 $N$ 个点坐标之和的最小值。

基本思路

假设选择了 $i$ ，则 $M = \frac{X_i + X_{i + 3} }{2}$ ，第 $i + 1$ 的位置变为:

$X'_{i + 1} = X_{i + 1} + 2(M - X_{i + 1}) = X_i + X_{i + 3} - X_{i + 1}$

同理第 $i + 2$ 的位置变为:

$X'_{i + 2} = X_{i + 2} + 2(M - X_{i + 2}) = X_i + X_{i + 3} - X_{i + 2}$

显然上面两个式子有公共项 $X_i + X_{i + 3}$ ，我们做差消去公共项:

$X'_{i + 1} - X'_{i + 2} = X_{i + 2} - X_{i + 1}$

也就是说操作一次前后 $i + 1$ 和 $i + 2$ 的两个棋子距离不变，变得是 $i + 1$ 与 $i$ 、 $i + 2$ 与 $i + 3$ 棋子之间的距离。

同时可以发现，由于操作前有 $X_{i + 2} > X_{i + 1}$ ，所以 $X'_{i + 1} - X'_{i + 2} = X_{i + 2} - X_{i + 1} > 0$ ，即操作后 $X'_{i + 1} > X'_{i + 2}$ ，这意味着操作后（按升序排列的）的第 $i + 1$ 颗棋子是原先的第 $i + 2$ 颗棋子，操作后（按升序排列的）的第 $i + 2$ 颗棋子是原先的第 $i + 1$ 颗棋子。

令 $d_i$ 表示（按升序排列的）第 $i$ 颗棋子与第 $i + 1$ 颗棋子的间距，操作前有：

$d_i = X_{i + 1} - X_{i}$

$d_{i + 1} = X_{i + 2} - X_{i + 1}$

$d_{i + 2} = X_{i + 3} - X_{i + 2}$

操作后有：

$d'_i = X'_{i + 2} - X_{i} = X_{i + 2} + X_{i + 3} - X_{i + 2} - X_{i} = X_{i + 3} - X_{i + 2} = d_{i +2}$

$d'_{i + 1} = X'_{i + 1} - X'_{i + 2} = X_{i + 2} - X_{i + 1} = d_{i + 1}$

$d'_{i + 2} = X_{i + 3} - X'_{i + 2} = X_{i + 3} - (X_i + X_{i + 3} - X_{i + 1}) = X_{i + 1} - X_{i} = d_{i}$

可以发现，操作一次等价于交换了 $d_i$ 和 $d_{i + 2}$ ，则新目标为最小化 $\sum\limits_{i = 1}^{N} \sum\limits_{j = 0}^{i-1}d_j$ 的值

$\sum\limits_{i = 1}^{N} \sum\limits_{j = 0}^{i-1}d_j = Nd_0 + (N - 1)d_1 + \cdots + d_{N - 1}$

贪心的想，为了取得最小值我们尽量将 $d$ 小的放前面，由于只能交换 $d_i$ 和 $d_{i + 2}$ ，所以分别将奇数位和偶数位（除 $d_0$ 外）从小到大排序然后求和即可。时间复杂度为 $O(n \log n)$ 。

考察知识

差分
贪心
不变量

参考实现

#include<bits/stdc++.h>
using i64 = long long;

int main(){
    std::cin.tie(0)->sync_with_stdio(0);
    i64 n;
    std::cin >> n;
    std::vector<i64> a(n + 1),odd,even;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        if(i == 1) continue;
        if(i & 1) odd.push_back(a[i] - a[i - 1]);
        else even.push_back(a[i] - a[i - 1]);
    }

    std::sort(odd.begin(),odd.end());
    std::sort(even.begin(),even.end());

    for(int i = 3,j = 0;i <= n;i += 2,j++) a[i] = odd[j];
    for(int i = 2,j = 0;i <= n;i += 2,j++) a[i] = even[j];

    i64 ans = 0;
    for(int i = 1;i <= n;i++){
        a[i] += a[i - 1];
        ans += a[i];
    }
    std::cout << ans << "\n";
    return 0;
}

Problem F. 短学期实践

题目大意

要求在假期共 $n$ 天中提交日志，必须保证任意连续 $k$ 天内总提交篇数不少于 $m$ 。求最少总提交篇数。

基本思路

贪心的想，为了让每篇日志的收益最大化，拖到最后一天再一次提交m篇日志，答案即为 $m\left \lfloor \frac{k}{n} \right \rfloor$ .

考察知识

贪心

参考实现

#include<bits/stdc++.h>
using i64 = long long;

int main(){
	std::cin.tie(0)->sync_with_stdio(0);
    int T = 1;
    std::cin >> T;
    while(T--){
        i64 n,k,m;
        std::cin >> n >> k >> m;
        std::cout << n / k * m << "\n";
    }
	return 0;
}

Problem G. 如何成为人类

题目大意

因为你是人类，所以直接输出 I am Human。

基本思路

这是一道签到题，题目描述极为复杂，但是作为人类，直接输出 I am Human 即可。

考察知识

字符串

FUN FACT

出题人在将题目描述扔给文心一言、Deepseek（均未开深度思考）时，都没有选择直接输出 I am Human。

参考代码

PHP

I am Human

C++

#include <iostream>
int main() {
    std::cout << "I am Human";
    return 0;
}

Problem H. 我们是奶龙

题目大意

起初 $1$ 到 $n$ 个节点构成一条连续长链。每次给定 $u, v$ ，若二者在同一条链中，则将所在链截断，取出夹在 $u, v$ 之间的连续片段构成新链，剩余两端的片段头尾接合再次构成一条新链。产生的能量是这两段新链节点数量之积。

基本思路

解法一：线段树

将第 $i$ 个奶龙所在链的最左边奶龙的颜色编号记为 $l_i$ ，记某次操作选择了 $(u,v)$ 两奶龙。如果 $l_u != l_v$ 则两奶龙不在同一条链上，输出 $0$ ；否则，两奶龙再同一条链上，此时在一次操作后，对于 $p \in [u,v]$ 且 $l_p = l_u$ （即 $p$ 和 $u$ 在同一条链上），都有 $l_p := u$ ；而对于 $p \in [u,v]$ 且 $l_p \ne l_u$ （即 $p$ 和 $u$ 不在同一条链上），一定有 $l_p >= u$ 。所以一次操作等价于 $p \in [u,v]$ 进行 $l_p := max(u,l_p)$ 操作。对于每条链最右边的奶龙 $r_i$ 同理。所以可以用线段树维护这样去维护 $l_i$ 、 $r_i$ 的区间 $max$ 赋值，同时维护每条链长度即可，时间复杂度 $O(q \log n)$ 。

不过还有一个需要特判的地方：若 $(u,v)$ 在同一条链上且均不是链的端点，而操作对 $[u,v]$ 外的节点不会有任何影响；但如果修改的点是链的端点,需要修改原来链上的另一半,所以还要维护每个点左右两边点的编号,模拟个链表就行了。

解法二：平衡树

拿个平衡树启发式删除即可。维护每个点所在的平衡树编号，可以模拟题意。

考察知识

线段树
链表
平衡树

参考实现

线段树 + 模拟链表

#include<bits/stdc++.h>
using i64 = long long;

template<class Info,class Tag>
struct SegmentTree{
    int N;
    std::vector<Info> info;
    std::vector<Tag> tag;
    SegmentTree():N(0){};
    SegmentTree(std::vector<Info> _init){init(_init);}
    void init(std::vector<Info> _init){
        N = _init.size() - 1;
        info.assign(4 << std::__lg(N),Info());
        tag.assign(4 << std::__lg(N),Tag());
        std::function<void(int,int,int)> build = [&](int p,int l,int r){
            if(l == r){
                info[p] = _init[l];
                return;
            }
            int m = (l + r) >> 1;
            build(p << 1,l,m);
            build((p << 1) | 1,m + 1,r);
            push_up(p);
        };
        build(1,1,N);
    }
    void push_up(int p){
        info[p] = info[p << 1] + info[(p << 1) | 1];
    }
    void apply(int p,const Tag &v){
        info[p].apply(v);
        tag[p].apply(v);
    }
    void push_down(int p){
        apply(p << 1,tag[p]);
        apply((p << 1) | 1,tag[p]);
        tag[p] = Tag();
    }
    void modify(int p,int l,int r,int x,int y,const Tag &v){
        if(l > y || r < x) return;
        if(x <= l && r <= y){
            apply(p,v);
            return;
        }
        push_down(p);
        int m = (l + r) >> 1;
        modify(p << 1,l,m,x,y,v);
        modify((p << 1) | 1,m + 1,r,x,y,v);
        push_up(p);
    }
    void modify(int l, int r, const Tag &v) {
        return modify(1,1,N,l,r,v);
    }
    Info query(int p,int l,int r,int x,int y){
        if(l > y || r < x) return Info();
        if(x <= l && r <= y) return info[p];
        push_down(p);
        int m = (l + r) >> 1;
        return query(p << 1,l,m,x,y) + query((p << 1) | 1,m + 1,r,x,y);
    }
    Info query(int l,int r){
        return query(1,1,N,l,r);
    }
};

struct Tag{
    int l,r;
    Tag():l(0),r(2e6){}
    Tag(int _l,int _r):l(_l),r(_r){}
    void apply(const Tag &t) & {
        l = std::max(t.l,l);
        r = std::min(t.r,r);
    }
};

struct Info{
    int l,r,siz;
    Info():l(2e6),r(0),siz(0){}
    Info(int _l,int _r,int _siz):l(_l),r(_r),siz(_siz){}
    void apply(const Tag &t) & {
        l = std::max(t.l,l);
        r = std::min(t.r,r);
    }
    
    Info operator+(const Info &other) const{
        Info res = {std::min(l,other.l),std::max(r,other.r),siz};
        if(other.l == l) res.siz += other.siz;
        else if(other.l < l) res.siz = other.siz;
        return res;
    }
};

struct List{
    struct node{
        int l,r;
    };
    std::vector<node> mp;
    List(){}
    List(int n){
        mp.resize(n + 1);
        for(int i = 1;i <= n;i++){
            mp[i] = {i - 1,i + 1};
        }
        mp[1].l = mp[n].r = 0;
    }
    node query(int p){return mp[p];};
    void split(int l,int r){
        int pre = mp[l].l,nex = mp[r].r;
        mp[l].l = mp[r].r = 0;
        mp[pre].r = nex;
        mp[nex].l = pre;
    }
};

int main(){
	std::cin.tie(0)->sync_with_stdio(0);
    int T = 1;
    std::cin >> T;
    while(T--){
        int n,q;
        std::cin >> n >> q;
        std::vector<Info> a(n + 1);
        for(int i = 1;i <= n;i++){
            a[i] = {1,n,1};
        }

        SegmentTree<Info,Tag> st(a);
        List ls(n);
        while(q--){
            int l,r;
            std::cin >> l >> r;
            if(r < l) std::swap(l,r);
            auto [l1,r1,_] = st.query(l,l);
            auto [l2,r2,__] = st.query(r,r);

            if(l1 == l2 && r1 == r2){
                int siz = st.query(l1,r1).siz;
                st.modify(l,r,{l,r});
                if(l1 == l){
                    auto [___,tr] = ls.query(r);
                    if(tr != 0){
                        st.modify(tr,r1,{tr,r1});
                    }
                }
                if(r1 == r){
                    auto [tl,___] = ls.query(l);
                    if(tl != 0){
                        st.modify(l1,tl,{l1,tl});
                    }
                }
                ls.split(l,r);
                int tsiz = st.query(l,r).siz;
                std::cout << (i64)(siz - tsiz) * tsiz << "\n";
            }
            else std::cout << "0\n";
        }
    }
	return 0;
}

Problem I. 十万，哈哈哈，十万

题目大意

给定 $n(1 \le n \le 10)$ 个数，选取其中若干个任意排列，并在相邻之间插入 + 或 *，按顺序运算（无视优先级）。求最终结果恰好为 $100000$ 的不同构造方案数。

基本思路

数据范围极小 ( $n \le 10$ )，并且假设当前已经选了一些数字，它们组成的表达式值已经确定，此时在表达式的最末端增加一个数字，无需考虑之前的表达式是什么顺序和运算符，具有无后效性，可以直接使用 状压dp。

第一维采用位掩码（bitmask）记录已经使用的数字下标，第二维记录值域， $dp[mask][x]$ 表示已经使用了 mask 中二进制为 $1$ 的下标，表达式的值为 $x$ 的方案数，状态更新则是枚举 mask 未选择的下标得到新的位掩码（new bitmask），并考虑 x 与本次选择的数字分别作加法和乘法的值，直接加法转移即可，复杂度 $O(n * 2^n \times 10^5)$ ，难以通过，由于总状态数有 $2^n \times 10^5$ 种，但是其中有大量的无用状态，可以考虑使用 bitset 标记并快速查找有用的状态，此时复杂度为 $O(n * 2^n \times 10^5 / w)$ ，其中 $w$ 代表位宽，可以通过本题。

使用集合（set）或映射（map）保存有用状态也可以稍降复杂度，但复杂度和常数仍然偏大，为了照顾python与java选手，本次比赛的在时限上允许这种做法，因此同时导致C++不使用bitset优化的代码如果常数小也可以通过本题。

考察知识

状压dp
位运算
搜索剪枝

参考代码

#include <bits/stdc++.h>

using ll = long long;
using namespace std;

constexpr int N = 1e5 + 1, mod = 998244353;


void solve() {
    int n;
    cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    using A = array<int, N>;
    using B = bitset<N>;
    std::vector<A> dp(1 << n);
    std::vector<B> v(1 << n);
    for (int i = 0; i < n; i++) {
        dp[1 << i][a[i]] = 1;
        v[1 << i][a[i]] = 1;
    }

    int ans = 0;
    for (int i = 1, lim = 1 << n; i < lim; i++) {
        for (int j = 0; j < n; j++) {
            if (i >> j & 1) continue;
            int t = i ^ (1 << j);
            for (int x = v[i]._Find_first(); x < N; x = v[i]._Find_next(x)) {
                int y = dp[i][x];
                ll w = 1ll * x * a[j];
                if (w < N) {
                    v[t][w] = 1;
                    auto &num = dp[t][w];
                    num += y;
                }
                w = x + a[j];
                if (w < N) {
                    v[t][w] = 1;
                    auto &num = dp[t][w];
                    num += y;
                }
            }
        }
        ans += dp[i][N - 1];
    }
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t;

    while (t--) {
        solve();
    }
}

Problem J. 和异位

题目大意

给定一个长为 $n$ 的数组，求所有有序对 $(i, j), i<j$ 之间的异或结果之和，即 $\sum_{1 \le i < j \le n} (a_i \oplus a_j)$ 。

基本思路

异或运算经典优化思路：按位拆解计算。

单独考虑每个二进制位（由于数据范围 $a_i \le 10^8 \le 2^{27}$ ，可以考虑 0 到 30 位）。对于第 k 位，异或产生 1 当且仅当两个数的第 k 位一个是 0，一个是 1。

对于 $0 \le k \le 30$ 的统计当前位 $k$ 上所有的 1 的个数 cnt1 和 0 的个数 cnt0，实际上 $cnt1 + cnt0 = n$ ，因此代码中可以只记录其中一个。它们对最终答案的贡献就是 (1LL << k) * cnt1 * cnt0。将所有位的贡献相加即可。

考察知识

位运算基础
拆位

参考代码

#include <bits/stdc++.h>

using ll = long long;
using namespace std;

constexpr int N = 1e5 + 1, mod = 998244353;


void solve() {
    int n;
    cin >> n;
    std::vector<int> a(n + 1);
    array<int, 31> b{};
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        for (int j = 0; j <= 30; j++) {
            b[j] += a[i] >> j & 1;
        }
    }

    ll ans = 0;
    for (int i = 1; i <= 30; i++) {
        ans += (1ll * (n - b[i]) * b[i]) << i;
    }
    cout << ans << '\n';

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    cin >> t;

    while (t--) {
        solve();
    }
}

Problem K. 马拉松树

题目大意

以类似后序遍历的规则遍历一棵树：递归遍历按编号升序排好的子节点，最后加上自身的字符。判断以每个节点为根的子树遍历生成的字符串是否是回文串。

基本思路

按照题目描述计算出树的dfs序，然后按dfs序得到新字符串 $str$ 。在 $str$ 中，每个子树对于的子串是连续的，所以只要计算出以每个 $str_i$ 为。树的遍历是 $O(n)$ ，求解回文串采用马拉车时间复杂度 $O(n)$ ，也可以采用字符串哈希求解回文串复杂度同样为 $O(n)$

考察知识

树的遍历
马拉车
字符串哈希

参考代码

马拉车

#include<bits/stdc++.h>
using i64 = long long;

std::string change(std::string str){
    std::string temp = "!#";
    for(int i = 0;i < str.size();i++){
            temp += str[i];
            temp += '#';
        }
    return temp;
}

std::vector<int> Manacher(std::string& str){
    int maxright = 0,mid = 0,ans = 0;
    str = change(str);
    std::vector<int> p(str.size());
    for(int i = 1;i < str.size();i++){
        if(i < maxright){
            p[i] = std::min(p[2 * mid - i],maxright - i + 1);
        }
        else{
            p[i] = 1 + (str[i] != '#');
        }
        while(i - p[i] >= 0 && p[i] + i < str.size() && str[i - p[i]] == str[i + p[i]]){
            p[i]++;
        }
        if(i + p[i] - 1 > maxright){
            mid = i;
            maxright = i + p[i] - 1;
        }
        ans = std::max(ans,p[i] - 1);
    }
    return p;
}

int main(){
    std::cin.tie(0)->sync_with_stdio(0);
    int n,idx = 0;
    std::string str = "",s;
    std::cin >> n >> s;

    if(n == 1){
        std::cout << 1 << "\n";
        return 0;
    }

    std::vector<std::vector<int>> edge(n + 1);
    for(int i = 0;i < n - 1;i++){
        int u,v;
        std::cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }

    std::vector<std::array<int,2>> dfn(n + 1);
    auto dfs = [&](auto &self,int u,int f) -> void{
        dfn[u][0] = n;
        std::sort(edge[u].begin(),edge[u].end());
        for(auto v : edge[u]){
            if(v == f) continue;
            self(self,v,u);
            dfn[u][0] = std::min(dfn[u][0],dfn[v][0]);
        }
        dfn[u][1] = ++idx;
        dfn[u][0] = std::min(dfn[u][0],dfn[u][1]);
        str += s[u - 1];
    };
    dfs(dfs,1,1);

    std::vector<int> a = Manacher(str);
    for(int i = 1;i <= n;i++){
        int c = dfn[i][1] + dfn[i][0];
        if(a[c] * 2 - 1 >= dfn[i][1] * 2 - dfn[i][0] * 2 + 3) std::cout << 1;
        else std::cout << 0;
    }
    return 0;
}

字符串哈希

#include<bits/stdc++.h>
using i64 = long long;
static constexpr int base = 37,mod = 1e9 + 9;

int main(){
    std::cin.tie(0)->sync_with_stdio(0);
    int n,idx = 0;
    std::string str = " ",s;
    std::cin >> n >> s;

    if(n == 1){
        std::cout << 1 << "\n";
        return 0;
    }

    std::vector<std::vector<int>> edge(n + 1);
    for(int i = 0;i < n - 1;i++){
        int u,v;
        std::cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }

    std::vector<std::array<int,2>> dfn(n + 1);
    auto dfs = [&](auto &self,int u,int f) -> void{
        dfn[u][0] = n;
        std::sort(edge[u].begin(),edge[u].end());
        for(auto v : edge[u]){
            if(v == f) continue;
            self(self,v,u);
            dfn[u][0] = std::min(dfn[u][0],dfn[v][0]);
        }
        dfn[u][1] = ++idx;
        dfn[u][0] = std::min(dfn[u][0],dfn[u][1]);
        str += s[u - 1];
    };
    dfs(dfs,1,1);
    
    std::vector<i64> pown(n + 1),hash(n + 1),rehash(n + 2);
    auto Hash = [&](std::string_view str) -> void{
        pown[0] = 1;
        for(int i = 1;i <= n;i++){
            pown[i] = (pown[i - 1] * base) % mod;
            hash[i] = (hash[i - 1] * base % mod + (str[i] - 'a')) % mod;
        }
    };
    
    auto reHash = [&](std::string_view str) -> void{
        for(int i = n;i >= 1;i--){
            rehash[i] = (rehash[i + 1] * base % mod + (str[i] - 'a')) % mod;
        }
    };
    
    auto getHash = [&](i64 l,i64 r){
        return ((hash[r] - hash[l - 1] * pown[r - l + 1] % mod) % mod + mod) % mod;
    };
    
    auto getReHash = [&](i64 l,i64 r){
        return ((rehash[l] - rehash[r + 1] * pown[r - l + 1] % mod) % mod + mod) % mod;
    };
    Hash(str),reHash(str);
    
    for(int i = 1;i <= n;i++){
        i64 l = dfn[i][0],r = dfn[i][1];
        if(getHash(l,r) == getReHash(l,r)) std::cout << "1";
        else std::cout << "0";
    }
    return 0;
}

Problem L. 小学数学题

题目大意

求解 $n!$ 十进制的个位数。

基本思路

当 $n >= 5$ 时， $n!$ 包含 $2$ 和 $5$ ，此时 $n!$ 为 $10$ 的倍数，个位数为 $0$ 。所以只需要特判 $n = 1,2,3,4$ 的情况，其余直接输出0。时间复杂度 $O(1)$ 。

考察知识

阶乘
整除

参考代码

#include<bits/stdc++.h>

int main(){
	std::cin.tie(0)->sync_with_stdio(0);
    int T = 1;
    std::cin >> T;
    while(T--){
        int n;
        std::cin >> n;
        if(n == 3) std::cout << "6\n";
        else if(n < 5) std::cout << n << "\n";
        else std::cout << "0\n";
    }
	return 0;
}

Problem M. 奶龙会拼图

题目大意

在一个存在障碍物的 $n \times m$ 网格上放置至多 $z$ 个不可重叠的 L 形拼图块。L 形的中间位置必须放在横纵坐标之和 $(i+j)$ 为奇数处，并可获得该坐标 $s[i][j]$ 的分数。求最大可获得分数。

基本思路

极其精妙的最大费用流 (MCMF) 图论建模。网络流大部分的题目都在考察建图，只要图建好了，直接跑一遍模板就可以了。关于网络流：网络流就是从源点流向汇点，每条边都有个流量上限，当一条边流量达到上限后，这条边就不允许再有流经过。费用流中，一条流量的费用贡献就是这条路径所有边中最小的流量与这条路径的费用和相乘，最终求得最小费用最大流或者最大费用流的一种算法。

拼图规则指出，中心坐标必然是在 $(i+j)$ 为奇数的格子。一个标准 L 形由于要去掉对角块，其中心块向外延伸的两个侧边一定是“一横一纵”的垂直状态，也就是说延伸的两个点和横坐标一定为一奇一偶，否则就不是 L 型。

所以建图可以分成三部分：

第一部分为有答案贡献的 $(i+j)$ 为奇数的点集合；
第二部分为 $(i+j)$ 为偶数且横坐标为奇数的点集合；
第三部分为 $(i+j)$ 为偶数且横坐标为偶数的点集合。

然后如下建图：

alt

源点 $s$ 向所有 $(i+j)$ 为偶数且横坐标为奇数的点连流量为 $1$ 、费用为 $0$ 的边；
$(i+j)$ 为偶数且横坐标为偶数的点向汇点 $t$ 连流量为 $1$ 、费用为 $0$ 的边；
中间有贡献的第一组点（ $(i+j)$ 为奇数的点）拆点，其边上流量为 $1$ 、费用为 $s[i][j]$ （因为这题是最大费用的板子，所以费用要改成负的）；
每组之间的边只连接那些在原图中相邻的点，因为 L 拼图肯定是相邻的一个整体。

所有的流量都是 $1$ ，跑一个流就会同时消去三组各一个点，且都相邻，这三个点显而易见一定是 L 型。在保证每个流都是一个 L 型的位置后，费用就靠最大费用流的板子来跑就行了，最后直接输出答案。注意流的上限，以及最大流的费用不一定最大，所以要判断退出（也就是拼图不用完的情况）。

考察知识

二分图匹配概念
最大费用流建模 (MCMF) / SPFA 增广算法

参考代码

#include <bits/stdc++.h>
using ll = long long;
using namespace std;

constexpr int N = 1e5 + 1, mod = 998244353;

template<class T>
struct MinCostFlow {
    struct _Edge {
        int to;
        T cap;
        T cost;
        _Edge(int to_, T cap_, T cost_) : to(to_), cap(cap_), cost(cost_) {}
    };
    int n;
    std::vector<_Edge> e;
    std::vector<std::vector<int>> g;
    std::vector<T> h, dis;
    std::vector<int> pre;
    bool dijkstra(int s, int t) {
        dis.assign(n, std::numeric_limits<T>::max());
        pre.assign(n, -1);
        std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>, std::greater<std::pair<T, int>>> que;
        dis[s] = 0;
        que.emplace(0, s);
        while (!que.empty()) {
            T d = que.top().first;
            int u = que.top().second;
            que.pop();
            if (dis[u] != d) {
                continue;
            }
            for (int i : g[u]) {
                int v = e[i].to;
                T cap = e[i].cap;
                T cost = e[i].cost;
                if (cap > 0 && dis[v] > d + h[u] - h[v] + cost) {
                    dis[v] = d + h[u] - h[v] + cost;
                    pre[v] = i;
                    que.emplace(dis[v], v);
                }
            }
        }
        return dis[t] != std::numeric_limits<T>::max();
    }
    MinCostFlow() {}
    MinCostFlow(int n_) {
        init(n_);
    }
    void init(int n_) {
        n = n_;
        e.clear();
        g.assign(n, {});
    }
    void addEdge(int u, int v, T cap, T cost) {
        g[u].push_back(e.size());
        e.emplace_back(v, cap, cost);
        g[v].push_back(e.size());
        e.emplace_back(u, 0, -cost);
    }
    std::pair<T, T> flow(int s, int t) {
        T flow = 0;
        T cost = 0;
        h.assign(n, 0);
        while (dijkstra(s, t)) {
            for (int i = 0; i < n; ++i) {
                h[i] += dis[i];
            }
            //
            if (h[t] > 0)  break;
            //
            T aug = std::numeric_limits<T>::max();
            for (int i = t; i != s; i = e[pre[i] ^ 1].to) {
                aug = std::min(aug, e[pre[i]].cap);
            }
            for (int i = t; i != s; i = e[pre[i] ^ 1].to) {
                e[pre[i]].cap -= aug;
                e[pre[i] ^ 1].cap += aug;
            }
            flow += aug;
            cost += aug * h[t];
        }
        return std::make_pair(flow, cost);
    }
    struct Edge {
        int from;
        int to;
        T cap;
        T cost;
        T flow;
    };
    std::vector<Edge> edges() {
        std::vector<Edge> a;
        for (int i = 0; i < e.size(); i += 2) {
            Edge x;
            x.from = e[i + 1].to;
            x.to = e[i].to;
            x.cap = e[i].cap + e[i + 1].cap;
            x.cost = e[i].cost;
            x.flow = e[i + 1].cap;
            a.push_back(x);
        }
        return a;
    }
};


void solve() {
    int n, m, k, z;
    cin >> n >> m >> k >> z;
    std::vector a(n + 1, std::vector<int>(m + 1, 0));
    std::vector b(n + 1, std::vector<int>(m + 1, 0));

    for (int i = 1; i <= k; i++) {
        int x, y;
        cin >> x >> y;
        b[x][y] = 1;
    }
    MinCostFlow<int> flow(2 * n * m + 3);

    int st = 2 * n * m + 1, en = 2 * n * m + 2;
    flow.addEdge(st, 0, z, 0);

    array<int, 4> dx{0, 1, 0, -1}, dy{1, 0, -1, 0};
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (b[i][j]) continue;
            int u = (i - 1) * m + j;
            if ((i + j) & 1) {
                flow.addEdge(u, u + n * m, 1, -a[i][j]);
                for (int d = 0; d < 4; d++) {
                    int tx = i + dx[d], ty = j + dy[d];
                    if (1 <= tx && tx <= n && 1 <= ty && ty <= m && !b[tx][ty]) {
                        int v = (tx - 1) * m + ty;
                        if (tx & 1) {
                            flow.addEdge(v, u, 1, 0);
                        } else {
                            flow.addEdge(u + n * m, v, 1, 0);
                        }
                    }
                }
            } else if (i & 1) {
                flow.addEdge(0, u, 1, 0);
            } else {
                flow.addEdge(u, en, 1, 0);
            }
        }
    }
    auto [fl, co] = flow.flow(st, en);
    cout << -co << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t;

    while (t--) {
        solve();
    }
}