2026年 YNU·KUST-ICPC 联赛题解

A. 73进化论

思路

观察演化规律，发现无论经过多少轮演化，最终字符串始终是 73 的重复：

• 第 0 轮：73
• 第 1 轮：7373
• 第 2 轮：73737373

因此，奇数位置是 7，偶数位置是 3。答案只需判断 的奇偶性即可。

由于 最大可达 （），远超 long long 范围，C++/Java 选手需要用字符串读入 ，判断最后一位的奇偶性。

时间复杂度：

参考代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int m;
    string n;
    cin >> m >> n;
    if((n.back() - '0') % 2 == 0)
        cout << 3 << endl;
    else
        cout << 7 << endl;
    return 0;
}

B. 我也要同步吗？对

思路

给定一个长度为 n 的 A 序列，和一个长度为 m 的 B 序列，两个序列中的值都是非负整数。

我们可以进行以下操作任意次：选择 A 中的任意位置的值 ，和 B 中任意位置的值 ，满足 ，然后重置 和 的值为实数 。

最后，我们要让 最大。

这是一道纯贪心题，如果手玩过一些样例后，不难发现得到最优结果的过程，总是满足下面这种贪心策略：

贪心策略：每次操作，我们可以从 中选择当前最小的可操作数字 ，从 中选择最大的且小于 的可操作数字 ，然后对这两个数字执行操作。重复这一过程，直到没有可操作的数字为止。最终得到的 序列所有数字之和就是最大的。

因此，我们可以考虑对 序列和 序列排序后，进行一次双层遍历即可。

时间复杂度：

参考代码

#include<bits/stdc++.h>
#define i64 long long
#define db double
using namespace std;

i64 n, m;

int main() {
    cin>>n>>m;
    vector<db> a(n), b(m);
    for(int i = 0;i<n;i++) {
        cin>>a[i];
    }
    for(int i = 0;i<m;i++) {
        cin>>b[i];
    }

    sort(a.begin(), a.end(), greater<db>());
    sort(b.begin(), b.end());

    for(int j = 0;j<m;j++) {
        for(int i = 0;i<n;i++) {
            if(b[j] > a[i]) {
                db t = (a[i] + b[j]) / 2;
                a[i] = t;
                b[j] = t;
            }
        }
    }

    db ans = 0;
    for(int i = 0;i<n;i++) {
        ans += a[i];
    }

    cout << ans << endl;
}

C. 神圣庆典

思路

考验码力的签到题。

做法一：

使用两层循环，外层将 i 从 1 遍历到 max(n, m)；内层两个循环，第一个将 j 从 1 遍历到 n，第二个将 j 从 1 遍历到 m。(i, j)的值就是该点坐标，通过 if 语句判断每个位置应该是 .，#还是 。

做法二：

原题目使用内存空间限制不允许这种解法通过，在验题人要求下取消了空间限制。

开启 空间大小数组，默认填充 0。使用循环将 K 和 M 的六条线段填充为 1。再使用字符输出数组。

此解法不提供 AC Code。

参考代码

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

    for (int i = 0; i < std::max(n, m); i++) {
        for (int j = 0; j < n; j++) {
            if (i >= n) {
                cout << ' '; continue;
            }
            if (j + 1 == (n - 1) / 4 + 1) {
                cout << '#'; continue;
            }
            if (j + 1 - ((n - 1) / 4 + 1) == std::abs((n + 1) / 2 - (i + 1))) {
                cout << '#'; continue;
            }
            cout << '.';
        }
        cout << ' ';
        for (int j = 0; j < m; j++) {
            if (i >= m) {
                cout << ' '; continue;
            }
            if ((j + 1) == (m + 1) / 2 && i + 1 >= (m + 1) / 2) {
                cout << '#'; continue;
            }
            if ((m + 1) / 2 - (i + 1) == std::abs((m + 1) / 2 - (j + 1))) {
                cout << '#'; continue;
            }
            cout << '.';
        }
        if (i + 1 < std::max(n, m)) cout << '\n';
    }
}

D. 内存块拼接

思路

给定 n 个正整数，求这 n 个正整数不能拼凑出多少个 范围内的数字（n 个整数可以重复取）。

这个问题是 同余最短路 相关的经典问题，不过这里更倾向于考察的是 完全背包 做法。

对于背包做法，我们考虑的是范围内所有数字的可达性问题，但这题的 和 范围很大，因此不可能完全用背包算出所有数可不可达，我们需要考虑背包是否有上界。

关键观察：

• 我们考虑只有两个数字 和 时，当 和 互质时，它们的最大不可表示数为 ；若 和 不互质，我们会发现，某一个数字 之后的范围会呈现稳定的规律性，即 的数字一定可达，而 的数字一定不可达。
• 当我们考虑三个以上的数字的时候，这个不规律和规律的边界数字 很难快速精确得到，但我们可以设定一个上界 ，比如 ，这是一个非常安全的上界，它一定比 要大。

算法流程：

1. 对于 范围内的数，我们使用 完全背包 计算可达性
2. 对于 的数字，我们可以通过除法快速得到这个范围内有多少个数字是 给定的 个数字整体 的值 的倍数

时间复杂度：，其中

参考代码

// 完全背包做法
#include<bits/stdc++.h>
#define i64 long long
#define all(x) x.begin(), x.end()
using namespace std;

int main() {
    int n;
    cin>>n;

    int g = -1;
    vector<int> a(n);
    for(int i = 0;i<n;i++) {
        cin>>a[i];
        if(g == -1) g = a[i];
        else g = __gcd(a[i], g);
    }

    i64 m = *min_element(all(a));
    i64 M = *max_element(all(a));
    i64 up = m * M;
    up += g - (up%g);

    vector<bool> dp(up + 5);
    dp[0] = 1;

    for(int i = 0;i<n;i++) {
        for(int j = 0;j<=up - a[i];j++) {
            if(dp[j]) dp[j + a[i]] = 1;
        }
    }

    vector<i64> pre(up + 5);
    pre[0] = 1;
    for(int i = 1;i<=up;i++) {
        pre[i] = pre[i-1] + dp[i];
    }

    auto cal = [&](i64 r) -> i64 {
        if(r < 0) return 0ll;
        i64 res;
        if(r <= up) res = pre[r];
        else res = pre[up] + (r-up)/g;
        return res;
    };

    int q;
    cin>>q;
    while(q--) {
        i64 l, r;
        cin>>l>>r;

        i64 ans = cal(r) - cal(l-1);
        ans = (r-l+1) - ans;

        cout<<ans<<endl;
    }

    return 0;
}

E. AND(S1) | AND(S2)

思路

给定一个包含 n 个非负整数的多重集 S，你需要把 S 划分为两个非空集合 S1 和 S2，使得 AND(S1) | AND(S2) 的结果最大。

核心思路：从高位贪心

我们首先确立贪心策略：从二进制的高位向低位尝试。

原因很简单：在二进制中，更高位的 1 的权重永远大于所有低位 1 的权重之和（例如 ）。

因此，我们维护一个当前最优解 ans（初始为 0），从最高位（例如第 30 位）开始向下遍历到第 0 位。对于每一位 k：

1. 假设我们将第 k 位置为 1，得到一个新的目标值 target = ans | (1 << k)。
2. 验证环节：我们需要判断，是否存在一种分组方式，使得 和 的运算结果能覆盖这个 target。
   • 如果验证通过：说明这一位可以达成，我们更新 ans = target。
   • 如果验证失败：说明这一位若是 1 则会产生矛盾，我们必须放弃这一位（保持为 0）。

验证逻辑：任务包与排斥原理

为了满足 target，我们只关心 target 二进制中为 1 的那些位。

不妨称这些必须为 1 的位为 "任务位"。

和 必须分工合作，把这些位撑起来。每一个任务位，要么由 负责（意味着 全体在这一位都是 1），要么由 负责。

排斥特性：对于任意数字 ，如果 在第 位是 0，那么 绝对不能进入负责第 位任务的那个组。否则，该组在第 位的 AND 结果就会变成 0，任务失败。

冲突导致的连通：如果一个数字 同时在两个任务位 和 上都是 0，那么为了给 留一条活路，任务 和任务 必须由同一个组来负责（这样 就可以去另一个不负责 和 的组"避难"）。

算法实现：并查集 (DSU)

基于上述逻辑，我们可以把验证过程转化为图的连通性问题：

1. 节点：target 中所有为 1 的位。
2. 边：对于数组中的每个数字，如果它在位 和位 都是 0，则在 和 之间连一条边（使用并查集 Union）。

通过并查集处理后，这些位会聚集成若干个 "连通分量" (即大任务包)。

最后的合法性检查：

1. 能力检查：对于每一个连通分量（大任务包），数组 中必须至少存在一个数字，它在这个分量包含的所有位上全是 1。

2. 分组检查：

   • 情况 A：有 2 个或以上的连通分量 → 可以分配
   • 情况 B：只有 1 个连通分量 → 所有任务位必须全部由一组负责，此时需要满足总数字个数 （必须分出非空的另一组）

整体时间复杂度 ，其中

参考代码

#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;

class DSU{
private:
    vector<int> fa;

public:
    void init(int n){
        for(int i = 1;i<=n;i++){
            fa[i] = i;
        }
    }

    int find(int x){
        return x == fa[x] ? x : (fa[x] = find(fa[x]));
    }

    void unity(int x, int y){
        int fx = find(x), fy = find(y);
        if(fx == fy)return;
        fa[fx] = fy;
    }

    DSU(int n){
        fa = vector<int>(n+1);
        init(n);
    }
};

int BIT = 30;

bool check(int tar, const vector<int>& a){
    vector<int> bits;
    for(int i = 0;i<30;i++){
        if((tar>>i) & 1){
            bits.push_back(i);
        }
    }

    if(bits.empty()) return 1;

    int m = bits.size();
    DSU dsu(m);

    for(auto x:a){
        int pidx = -1;
        for(int i = 0;i<m;i++){
            if(!((x>>bits[i]) & 1)){
                if(pidx == -1) {
                    pidx = i;
                } else {
                    dsu.unity(pidx, i);
                }
            }
        }
    }

    map<int, vector<int>> mp;
    for(int i = 0;i<m;i++){
        mp[dsu.find(i)].push_back(bits[i]);
    }

    for(auto [x, tar_bits]:mp){
        bool f = 0;
        for(auto i:a){
            bool ok = 1;
            for(auto bit:tar_bits){
                if(!((i>>bit) & 1)) {
                    ok = 0;
                    break;
                }
            }

            if(ok){
                f = 1;
                break;
            }
        }

        if(!f){
            return 0;
        }
    }

    if(mp.size() == 1) return a.size() > 1;
    if(mp.size() > 1) return 1;

    return 0;
}

void solve() {
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i = 0;i<n;i++) cin>>a[i];

    if(n == 1) {
        cout<<0<<endl;
        return;
    }

    int ans = 0;
    for(int k = 29;k>=0;k--){
        int tar = ans | (1 << k);
        if(check(tar, a)){
            ans = tar;
        }
    }

    cout<<ans<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

F. 语言模型的Bug

思路

这题定位是签到，其实是一个经典栈模拟问题。

本题中 不同的删除顺序可能会得到不同的最终结果 其实就是迷惑人的一句话。仔细想想不难发现，这跟大家玩开心消消乐不一样，不同删除顺序其实是殊途同归的。

那么比较容易想到和实现的一种删除方式就是：从前往后遍历字符串，遇到与栈顶相同的字符就弹出栈顶（相当于删除），否则入栈。最终栈的大小即为答案。

时间复杂度：

参考代码

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    vector<char> stk;
    for(char c : s) {
        if(!stk.empty() && c == stk.back())
            stk.pop_back();
        else
            stk.push_back(c);
    }
    cout << stk.size() << endl;
    return 0;
}

G. 小镇通信网

思路

这题思路其实并不难想到，主要就是考验一下代码实现能力。下面提供一种最容易的构造思路：

构造策略：

1. 先构造直径：建立一条长度为 的链作为树的"主干"（节点 ）
2. BFS 填充剩余节点：从主干上的非端点节点开始，尽可能向外扩展：
   • 优先从主干中间位置的节点扩展（保证不超过直径）
   • 每个节点最多连接 条边
   • 新加入的节点也可以继续扩展（深度限制为不超过直径的一半）

无解判断：

• 若 ：直径本身需要的节点就超过总节点数
• 若 ：每个节点最多连 1 条边，只能构造 2 个节点的树（）
• 若 ：只能构造链状结构，需要
• 若剩余节点无法全部挂到树上：说明即使每个节点都用满 个度数，也容纳不下所有节点

时间复杂度：

参考代码

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, d, k;
    cin >> n >> d >> k;

    // 无解判断
    if(d + 1 > n) {
        cout << -1 << endl;
        return 0;
    }
    if(k == 1) {
        if(n == 2 && d == 1)
            cout << "1 2" << endl;
        else
            cout << -1 << endl;
        return 0;
    }
    if(k == 2) {
        if(n == d + 1) {
            for(int i = 1; i <= d; i++)
                cout << i << " " << i + 1 << endl;
        } else
            cout << -1 << endl;
        return 0;
    }

    // 构造直径主干
    vector<pair<int, int>> edges;
    vector<int> deg(n + 1, 0);
    for(int i = 1; i <= d; i++) {
        edges.push_back({i, i + 1});
        deg[i]++;
        deg[i + 1]++;
    }

    // BFS 填充剩余节点
    int cur = d + 2;
    queue<pair<int, int>> q; // {节点, 最大扩展深度}
    for(int i = 2; i <= d; i++) {
        int max_depth = min(i - 1, d + 1 - i);
        q.push({i, max_depth});
    }

    while(!q.empty() && cur <= n) {
        auto [u, depth] = q.front();
        q.pop();
        if(depth == 0) continue;

        int can_add = k - deg[u];
        for(int i = 0; i < can_add && cur <= n; i++) {
            edges.push_back({u, cur});
            deg[u]++;
            deg[cur]++;
            if(depth > 1)
                q.push({cur, depth - 1});
            cur++;
        }
    }

    // 检查是否所有节点都加入了
    if(cur <= n) {
        cout << -1 << endl;
        return 0;
    }

    for(auto [u, v] : edges)
        cout << u << " " << v << endl;

    return 0;
}

H. 消息中转

思路

题目要求计算：

暴力枚举所有点对求 LCA 的复杂度为 ，无法通过。核心优化思路是转换枚举顺序：不枚举点对，而是枚举每个节点作为 LCA 时的贡献。

方法一：直接枚举 LCA

关键观察：对于节点 ，只有当 分属 的不同子树时，。

算法流程：

1. DFS 序 + 重链剖分：预处理每个节点的子树区间 和重儿子
2. DSU on Tree（树上启发式合并）：
   • 先递归处理所有轻儿子，算完后清空
   • 再递归处理重儿子，保留其信息
   • 遍历轻儿子 的子树：将 子树内的点与已有点（重儿子+之前的轻儿子）配对，这些点对的 LCA 就是 ，贡献计入答案并乘
   • 将当前节点 与子树内所有点配对，LCA 也是 ，贡献乘
3. 树状数组优化绝对值差：
   • 维护 tr0[x]（ 值为 的节点个数）和 tr1[x]（ 值为 的节点 值之和）
   • 对于节点 ，其与已有节点的 之和拆分为：
     • ：
     • ：

时间复杂度：

方法二：容斥推导（数学优化）

定义 为节点 的子树内所有点对的 之和，通过容斥原理推导：

其中根节点 的系数为 （父节点权值视为 ）。

先用 DSU on Tree 计算每个节点的 ，再用上述公式累加即可。此方法避免了在 DFS 过程中直接枚举 LCA，代码结构更清晰。

参考代码

这边提供方法一的参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int M = 2e5 + 10;
const int mod = 998244353;

template <typename T>
struct Fenwick
{
    int n;
    vector<T> w;

    Fenwick(int n) : n(n), w(n + 1) {}

    void add(int x, T k)
    {
        for (; x <= n; x += x & -x)
            w[x] = (w[x] + k) % mod;
    }

    T ask(int x)
    {
        auto ans = T();
        for (; x; x -= x & -x)
            ans = (ans + w[x]) % mod;
        return ans;
    }

    T ask(int x, int y)
    {
        return (ask(y) - ask(x - 1) + mod) % mod;
    }
};

unsigned long long a[N], b[N], res;
vector<int> edge[N];
int sz[N], son[N], l[N], r[N], node[N], dfncnt;
Fenwick<unsigned long long> tr0(M), tr1(M);

void dfs1(int u, int fa)
{
    sz[u] = 1;
    l[u] = ++dfncnt;
    node[dfncnt] = u;
    for (auto v : edge[u])
    {
        if (v == fa) continue;
        dfs1(v, u);
        if (sz[v] > sz[son[u]]) son[u] = v;
        sz[u] += sz[v];
    }
    r[u] = dfncnt;
}

void dfs2(int u, int fa, bool keep)
{
    for (auto v : edge[u])
        if (v != fa && v != son[u])
            dfs2(v, u, false);

    if (son[u])
        dfs2(son[u], u, true);

    for (auto v : edge[u])
    {
        if (v != fa && v != son[u])
        {
            for (int i = l[v]; i <= r[v]; i++)
            {
                int x = node[i];
                res = (res + (tr0.ask(1, b[x]) * b[x] % mod - tr1.ask(1, b[x]) % mod + mod) % mod * a[u]) % mod;
                res = (res + (tr1.ask(b[x], M - 1) % mod - tr0.ask(b[x], M - 1) * b[x] % mod + mod) % mod * a[u]) % mod;
            }
            for (int i = l[v]; i <= r[v]; i++)
            {
                int x = node[i];
                tr1.add(b[x], b[x]);
                tr0.add(b[x], 1);
            }
        }
    }

    int x = u;
    res = (res + (tr0.ask(1, b[x]) * b[x] % mod - tr1.ask(1, b[x]) % mod + mod) % mod * a[u]) % mod;
    res = (res + (tr1.ask(b[x], M - 1) % mod - tr0.ask(b[x], M - 1) * b[x] % mod + mod) % mod * a[u]) % mod;
    tr0.add(b[x], 1);
    tr1.add(b[x], b[x]);

    if (!keep)
    {
        for (int i = l[u]; i <= r[u]; i++)
        {
            int x = node[i];
            tr0.add(b[x], -1);
            tr1.add(b[x], (-b[x] + mod) % mod);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }

    dfs1(1, 0);
    dfs2(1, 0, 1);
    cout << res << endl;

    return 0;
}

I. 滇池传说

思路

给定一个范围 ，求这个范围内数字根为 的数字的数量。

此题是签到题，暴力即可，复杂度 。

当然，数字根问题也有加速方法，容易发现范围内数字的数字根是从 1 到 9 不断循环的 (0 除外)，因此可以通过除法快速统计答案，复杂度为 。

的原理涉及到 九余数定理，感兴趣的同学可以去看一下。

时间复杂度：

参考代码

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

auto get(int x, int k) -> int {
    return x / 9 + (x % 9 >= k);
}

int main() {
    int x, y, k;
    cin >> x >> y >> k;
    k %= 9;
    cout << get(y, k) - get(x - 1, k);

    return 0;
}

J. 有环竞赛图计数

思路

给定一个节点数 n，请你输出由这 n 个节点可能构成所有的竞赛图中，图中有环的竞赛图数量 的结果。

首先，我们知道由 个节点构成的竞赛图的方案总数为 ，其中一部分方案有环，一部分方案无环。

根据无环图拓扑序唯一，我们知道，如果前 个顶点的图是无环的，那么加入第 个顶点也无环的方案数是 ，因为这第 个顶点的拓扑序位置可以在序列 中的任何位置，位置数为 。

因此有递推关系 ，其中 表示由 个点构成的完全无环图的方案数，即 。

因为 ，这是一个质数。

因此答案就是 。

注意到 后，，因此对于 ，只需要计算 即可。

而对于 的询问，初始化 （ 从 到 的值），这样每次查询同样可以快速计算出结果。

时间复杂度：（快速幂）

参考代码

#include<bits/stdc++.h>
#define i64 long long
using namespace std;

const int mod = 1e6+3;

i64 powmod(i64 a, i64 b) {
    i64 res = 1;
    while(b) {
        if(b&1) res = res * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return res;
}

int main() {
    i64 n;
    cin>>n;

    i64 m;
    if(n&1) {
        m = (n-1)/2 % (mod-1);
        m = m * (n % (mod-1)) % (mod-1);
    } else {
        m = n/2 % (mod-1);
        m = m * ((n-1) % (mod-1)) % (mod-1);
    }
    int ans;
    i64 t = 1;

    if(n >= 1e6+3) {
        ans = powmod(2, m);
    } else {
        for(int i = 2;i<=n;i++) {
            t = t * i % mod;
        }
        ans = powmod(2, m) - t + mod;
        ans %= mod;
    }

    cout<<ans;

    return 0;
}

K. 环路激活

思路

题目要求最多能进行多少次环路激活操作，每次操作需要选择一个包含至少一条未激活边（权值为0）的环。

核心观察：我们希望最大化操作次数，即尽可能多地找到包含未激活边的环。贪心策略是：

• 先用所有已激活的边（权值为1）构建基础连通性
• 对于每条未激活的边（权值为0），按顺序考虑：
  • 如果该边连接的两个节点已经连通，说明加入这条边会形成环，可以进行一次操作
  • 否则，将这条边加入连通关系（此时不足以构成环，不计数；若后续有边能与它形成环，会在那条边处计数）

证明正确性： 当一条权值为0的边的两端已经连通时，说明存在一条不经过该边的路径连接两端。这条路径加上当前边就构成了一个环，且该环至少包含一条权值为0的边（当前边），满足操作条件。将该边加入后，后续的边仍然可以继续寻找新的环。

使用并查集维护连通性即可。

时间复杂度：，其中 是反阿克曼函数

参考代码

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

struct DSU {
    vector<int> fa;

    DSU(int n) {
        fa.resize(n + 1);
        iota(fa.begin(), fa.end(), 0);
    }

    int get(int x) {
        while (x != fa[x]) {
            x = fa[x] = fa[fa[x]];
        }
        return x;
    }

    bool merge(int x, int y) {
        x = get(x), y = get(y);
        if (x == y) return false;
        fa[y] = x;
        return true;
    }

    bool same(int x, int y) {
        return get(x) == get(y);
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    DSU dsu(n);
    vector<pair<int, int>> edges0;

    for(int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        if(w == 1)
            dsu.merge(u, v);
        else
            edges0.push_back({u, v});
    }

    int res = 0;
    for(auto [u, v]: edges0) {
        if(dsu.same(u, v))
            res++;
        else
            dsu.merge(u, v);
    }

    cout << res << endl;

    return 0;
}