软件学院2026年ACM程序设计竞赛暨ICPC省赛选拔赛题解

难度：D < A < C < G = B < F < E < H

A. 多边形

1. 核心原理

组成一个凸多边形（包括退化的多边形，即边在同一直线上）的必要条件是：
最长边的长度 $L_{max}$ 必须严格小于其余所有边的长度之和 $S_{rest}$ 。

即： $L_{max} < S_{rest}$

如果当前给出的 $n$ 条边无法组成凸多边形，说明当前的最长边 $L_{max}$ 已经大于或等于了其余边之和：
$L_{max} \ge S_{rest}$

2. 解题思路

题目要求我们添加一条边，使得这些边能组成凸多边形。设新增加的边长度为 $x$ 。

为了使 $x$ 最小，我们应该让新边 $x$ 与原有的所有边共同构成一个新的边集。此时有两种情况：

$L_{max}$ 依然是所有边中最长的： 那么必须满足 $L_{max} < S_{rest} + x$ 。
$x$ 变成了新的最长边： 那么必须满足 $x < S_{rest} + L_{max}$ 。

我们要找的是最小的正整数 $x$ （根据输入输出样例，通常这类题目要求最小正整数长度）。

在 $L_{max} \ge S_{rest}$ 的情况下，为了修补这个不等式，最简单的方法就是通过 $x$ 来补足 $S_{rest}$ ，使得：
$x > L_{max} - S_{rest}$
因此，最小的整数 $x$ 为：
$x = L_{max} - S_{rest} + 1$

3. 算法步骤

读取边的数量 $n$ 。
读取所有边的长度，同时记录其中的最大值 $max\_l$ 和所有边总和 $sum\_l$ 。
计算其余边之和： $S_{rest} = sum\_l - max\_l$ 。
判断是否已经满足 $max\_l < S_{rest}$ 。

如果满足，则不需要加边（但根据题意通常是已经不满足才问）。
如果不满足，输出 $max\_l - S_{rest} + 1$ 。

4. 示例代码 (C++)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int n;
    if (!(cin >> n)) return 0;
    long long max_l = 0;
    long long sum_l = 0;
    for (int i = 0; i < n; ++i) {
        long long l;
        cin >> l;
        if (l > max_l) max_l = l;
        sum_l += l;
    }
    long long S_rest = sum_l - max_l;
    if (max_l < S_rest) {
        // 已经可以组成凸多边形
        cout << 0 << endl;
    } else {
        // 计算需要的最小长度
        cout << max_l - S_rest + 1 << endl;
    }
    return 0;
}

B. 吃草莓

操作一：每一位盘子中有草莓的顾客都会吃掉盘子中的一个草莓
操作二：从一位顾客盘子中选择任意数量的草莓放到另一位顾客的盘子中

枚举 操作二 完成后所有盘子中的最大草莓数，然后对每个盘子中的草莓数求其所需的最小 操作二 次数（贪心地，总是分到新盘子上，因为顾客是无限的），加上最后最大草莓数（即 操作一 的次数）取最小值即为答案。

#include<bits/stdc++.h>
using namespace std;
int T = 1 ;
int n ;
void solve(){
    cin >> n ;
    vector<int> a(n + 1,0);
    int ma = 0 ;
    for(int i = 1 ; i <= n ; ++ i ){
        cin >> a[i] ;
        ma = max(ma,a[i]);
    }
    int ans = ma;
    for(int i = 1 ; i <= ma ; ++ i){// 假设最后等待 i 分钟，也就是最后所有盘子中的最大草莓数是 i
        int cnt = i ;
        for(int j = 1 ; j <= n ; ++ j ){
            if(a[j] <= i) continue;
            int tem = ((a[j] - i) + i - 1) / i ;
            cnt += tem;
        }
        ans = min(ans,cnt);
    }
    cout << ans << endl;
}
signed main(){
    cin >> T ;
    while(T --){
        solve() ;
    }
    return 0;

}

C.最大正方形

用 $dp(i,j)$ 表示以 $(i,j)$ 为右下角，且只包含 $1$ 的正方形的边长最大值。如果我们能计算出所有 $dp(i,j)$ 的值，那么其中的最大值即为矩阵中只包含 $1$ 的正方形的边长最大值，其平方即为最大正方形的面积。

那么如何计算 $dp$ 中的每个元素值呢？对于每个位置 $(i,j)$ ，检查在矩阵中该位置的值：

如果该位置的值是 $0$ ，则 $dp(i,j)=0$ ，因为当前位置不可能在由 $1$ 组成的正方形中；

如果该位置的值是 $1$ ，则 $dp(i,j)$ 的值由其上方、左方和左上方的三个相邻位置的 $dp$ 值决定。具体而言，当前位置的元素值等于三个相邻位置的元素中的最小值加 $1$ ，状态转移方程如下：

$dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1$

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<char>> matrix(n, vector<char>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> matrix[i][j];
        }
    }
    vector<vector<int>> dp(n, vector<int>(m, 0));
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (matrix[i][j] == '1') {
                int t1 = 0, t2 = 0, t3 = 0;
                if (i - 1 >= 0) t1 = dp[i - 1][j];
                if (j - 1 >= 0) t2 = dp[i][j - 1];
                if (i - 1 >= 0 && j - 1 >= 0) t3 = dp[i - 1][j - 1];
                dp[i][j] = min({t1,t2,t3}) + 1;
                ans = max(ans, dp[i][j]);
            }
        }
    }
    cout << ans * ans << '\n';
    return 0;
}

D.点击赠送AC

直接输出即可，但是要注意换行，

#include<bits/stdc++.h>
using namespace std ;
int T = 1 ;
void solve(){
    cout << "I solemnly promise that I will not cheat in any form during this algorithm competition." << endl ;
    cout << "I will strictly abide by all competition rules and disciplines, uphold the principle of fair competition, complete the competition tasks independently, and not seek help from others, plagiarize code, or use any improper means to obtain advantages." << endl ;
    cout << "If I violate this commitment, I am willing to accept all corresponding penalties imposed by the competition organizer, including but not limited to disqualification and cancellation of results.";
}
signed main(){
    while(T --){
        solve() ;
    }
}

E.Day and Night

根据题意我们可以发现一些特性：

对于一个序列是否秩序，反转操作并不会改变他的秩序与否；

当一个序列反转，0和1的变化只会引起这段序列左右两端是否接着秩序。

看到区间修改，区间查询我们容易想到用线段树来实现。这里我们可以预处理一下原序列，既然所有操作只与相邻两个字符是否相同有关，那么我们规定如果 $S_i=S_{i+1}$ ，则记 $A_i=0$ ；如果 $S_i\neq S_{i+1}$ ，则记 $A_i=0$ 。从而预处理得到 $A$ 序列。这样以来线段树操作就简化为了单点修改、区间查询。

反转操作等同于： $A_{L-1}\leftarrow (1-A_{L-1})$ ， $A_R\leftarrow (1-A_R)$ 。注意边界情况。

查询操作等同于： $A_L=A_{L+1}=\cdots=A_{R-1}=1$ 时为 "Yes"，否则为 "No"。即 $A_L+A_{L+1}+\cdots+A_{R-1}=R-L$ ，答案就是 "是"，否则就是 "否"。

整体时间复杂度为 $O(N\log N)$ 。

同样可以用树状数组来实现，这里提供线段树的一种实现方法：

#include <bits/stdc++.h>
using namespace std;
const int N = 500000 + 10;
int n, q, tr[N << 2];
string s;
void upd(int p, int v, int id, int l, int r) {
    if (r - l == 1) {
        tr[id] = v;
        return;
    }
    int m = (l + r) >> 1;
    if (p < m) upd(p, v, id << 1, l, m);
    else upd(p, v, id << 1 | 1, m, r);
    tr[id] = tr[id << 1] + tr[id << 1 | 1];
}
int qry(int ql, int qr, int id, int l, int r) {
    if (ql <= l && r <= qr) return tr[id];
    int m = (l + r) >> 1, res = 0;
    if (ql < m) res += qry(ql, qr, id << 1, l, m);
    if (m < qr) res += qry(ql, qr, id << 1 | 1, m, r);
    return res;
}
int get(int p) {
    return qry(p, p + 1, 1, 0, n + 1);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q >> s;
    for (int i = 0; i < n - 1; ++i)
        if (s[i] != s[i + 1])
            upd(i + 1, 1, 1, 0, n + 1);
    while (q--) {
        string op;
        int l, r;
        cin >> op >> l >> r;
        if (op == "spell") {
            upd(l - 1, 1 - get(l - 1), 1, 0, n + 1);
            upd(r, 1 - get(r), 1, 0, n + 1);
        } else {
            cout << (qry(l, r, 1, 0, n + 1) == r - l ? "Yes\n" : "No\n");
        }
    }
    return 0;
}

F.找零

一个A买了煎饼后你会积累50元钱
一个B买了煎饼后需要你找零50元钱

说明在一个B买煎饼前至少需要一个 $A$ 买过煎饼，那么我们就可以把 $A$ 看为左括号， $B$ 看为右括号，那么这个问题就可以转化为问你有多少种括号匹配，这是卡特兰数的经典应用场景。

这道题目就是主要是考察了卡特兰数，如果你学过这个知识点就能很容易解决，当然用常规 dp 也可以写，但这里就只展示卡特兰数的写法，直接套公式即可，

但是注意这道题目还需要取模，所以记得取逆元，中间结果还可能会爆 long long，所以要小心处理

#include<bits/stdc++.h>
using namespace std ;
int T = 1 ;
int MOD = 998244353;
void solve(){
    int n ;
    cin >> n ;
    vector<long long> dp(n+1,0);
    dp[0] = 1 ;
    vector<long long> res(n + 2);
    res[1] = 1;
    for(int i = 2;  i <= n + 1 ; ++ i){// 这里是线性求逆元，当然你用快速幂也可以
        res[i] = (MOD - MOD / i) * res[MOD % i] % MOD;
    }
    for(int i = 1 ; i <= n ; ++ i){
        dp[i] = ((dp[i-1] * (4*i-2)) % MOD * res[i+1]) % MOD;
    }
    cout << dp[n] << endl ;
    return;
}
signed main(){
    while(T --){
        solve() ;
    }
}

G.匹配优化

要用二分法直接二分答案，只需要找到最小匹配质量X，而不需要考虑选择的方案，当X越来越大时，满足条件的玩家数会越来越多，可承受的房间数会越来越少，整体呈现单调性，所以我们直接二分X。

首先将A、B两个序列排序，对答案X进行二分。

对于一个X，可通过二分找到满足条件的玩家和可承受的房间的数量，然后判断是否符合条件即可。

可以使用 lower_bound 和 upper_bound 函数简化代码。

也可使用双指针等其他方法，这里提供二分法的一种实现方法：

#include<bits/stdc++.h>
using namespace std;
void solve()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (int i = 0; i < n; i ++) cin >> a[i];
    for (int i = 0; i < m; i ++) cin >> b[i];
    int l = 0, r = 1e9 + 10;
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    while (l + 1 < r) {
        int mid = (l + r) >> 1;
        int gamer = upper_bound(a.begin(), a.end(), mid) - a.begin();
        int room = b.end() - lower_bound(b.begin(), b.end(), mid);
        if (gamer >= room)
            r = mid;
        else
            l = mid;
    }
    cout << r << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int _ = 1;
    //cin >> _;
    while (_--)
        solve();
    return 0;
}