三晋七校第一届新生赛（同步赛）2025年题解

D

#include <iostream>
using namespace std;

int main() {
    cout << "Hello Shanxi and XCPC!" << endl;
    return 0;
}

hello world；无需解释

M

实际上是在评估一个多重循环的时间复杂度，其中每个循环的迭代次数对应一个区间的长度。总的迭代次数就是所有区间长度的乘积。 首先读取一个整数 n，表示后续有多少个区间 对于每个区间，读取左右边界 l 和 r 初始化 total = 1 对于每个区间 [l, r]，计算该区间内的整数个数：r - l + 1 将所有区间的可能性数量相乘，得到总的组合数 total 根据 total 的值分为三个等级

• NO TLE：如果 total ≤ 100,000，认为不会超时
• POSSIBLE：如果 100,000 < total ≤ 10,000,000，认为可能超时
• TLE：如果 total > 10,000,000，认为肯定会超时

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    long long total = 1;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        total *= (r - l + 1);
    }
    
    if (total <= 100000) {
        cout << "NO TLE" << endl;
    } else if (total > 10000000) {
        cout << "TLE" << endl;
    } else {
        cout << "POSSIBLE" << endl;
    }
    
    return 0;
}

K

一个特定的位翻转逻辑 整数 n 表示字符串长度 读取字符串 s 表示一个二进制序列 使用一个 flip 变量来跟踪当前的翻转状态 0,1 对于每个字符 将字符转换为整数 bit（0 或 1） 计算输出：out = bit ^ flip（异或操作） 如果输出是 1，就翻转 flip 的状态

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n; string s;
    cin >> n >> s;
    int flip = 0;
    for (int i = 0; i < n; i++) {
        int bit = s[i] - '0';
        int out = bit ^ flip;
        cout << out;
        if (out == 1) flip ^= 1; 
    }
}

L

寻找满足特定模式的最长子串长度 代码在寻找符合以下模式的最长子串 ( # # ... # )

1. 遍历字符串中的每个字符
2. 当遇到 '(' 时：
   • 从下一个位置开始，跳过连续的 '#' 字符
   • 检查跳过 '#' 后是否遇到 ')'
   • 如果找到 ')'，计算当前子串长度并更新最大值
3. 继续遍历直到字符串结束

n = int(input().strip())
s = input().strip()
max_len = 0
i = 0
while i < n:
    if s[i] == '(':
        j = i + 1
        while j < n and s[j] == '#':
            j += 1
        if j < n and s[j] == ')':
            max_len = max(max_len, j - i + 1)
    i += 1
print(max_len)

PYTHON实现

F

一个优化查询的算法，用于找到最佳的旋转偏移量 给定一个数组 a 和多个查询 x，对于每个查询，需要找到一个偏移量 k，使得

• 将数组循环右移 k 个位置
• 计算 a[i] + a[(i+k)%n] 的和等于 x 的对数最多
• 如果有多个 k 得到相同的最多对数，选择最小的 k

unordered_map<int, pair<int,int>> best;
// best[x] = {最佳k, 出现次数}

对于每个可能的偏移量 k (0 ≤ k < n)

1. 统计所有位置 i 的 a[i] + a[(i+k)%n] 的和
2. 使用 cnt 映射记录每个和值出现的次数
3. 更新 best 映射：
   • 如果当前和值 s 的出现次数更多
   • 次数相同但 k 更小
   • 则更新为当前的 k 对于每个查询 x

• 如果 x 在 best 中存在，输出对应的最佳 k
• 否则输出 0

算法复杂度

• 预处理：O(n²) - 对每个k遍历整个数组
• 查询：O(q) - 每个查询O(1)查找

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    unordered_map<int, pair<int,int>> best;
    for (int k = 0; k < n; k++) {
        unordered_map<int,int> cnt;
        for (int i = 0; i < n; i++) {
            int s = a[i] + a[(i + k) % n];
            cnt[s]++;
        }
        for (auto &[s, c] : cnt) {
            auto it = best.find(s);
            if (it == best.end() || c > it->second.second || (c == it->second.second && k < it->second.first)) {
                best[s] = {k, c};
            }
        }
    }
    while (q--) {
        long long x;
        cin >> x;
        if (best.count(x)) cout << best[x].first << "\n";
        else cout << 0 << "\n";
    }
}

G

简单的判断问题，检查数组元素的和是否能被数组长度整除 对于每组测试数据：

• 输入一个整数 n 表示数组长度
• 输入 n 个数字
• 判断这 n 个数字的和是否能被 n 整除
• 计算所有数字的和 s
• 检查 s % n 是否为 0：
  • 如果 s % n == 0，输出 "Yes"
  • 如果 s % n != 0，输出 "No"

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t; cin>>t;
    while(t--){
        int n; cin>>n;
        long long s=0,x;
        for(int i=0;i<n;i++){cin>>x;s+=x;}
        cout<<(s%n?"No\n":"Yes\n");
    }
}

E

数据结构

• 使用 vector<pair<int,int>> 存储选手数据
• 每个 pair<int,int> 表示一个选手的 (主要分数, 次要分数)

排序规则

sort(a.begin(), a.end(), [](auto &p1, auto &p2){
    if (p1.first != p2.first) return p1.first > p2.first; 
    return p1.second < p2.second; 
});

排序优先级：

1. 主要分数降序：first 大的排在前面
2. 次要分数升序：如果主要分数相同，second 小的排在前面

根据排名百分比划分奖牌等级： gold前 10% (n / 10) silver前 30% (n * 3 / 10) bronze前 60% (n * 6 / 10) iron后 40%

查找特定选手排名

• self = a[0] 保存了要查询的选手（第一个输入的选手）
• 在排序后的数组中查找该选手的位置，计算其排名

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

int main() {
    int n; 
    cin >> n;
    vector<pair<int,int>> a(n);
    for (int i=0;i<n;i++) cin >> a[i].first >> a[i].second;
    auto self = a[0];
    
    sort(a.begin(), a.end(), [](auto &p1, auto &p2){
        if (p1.first != p2.first) return p1.first > p2.first; 
        return p1.second < p2.second; 
    });
    
    int rank = 0;
    for (int i=0;i<n;i++){
        if (a[i] == self){
            rank = i + 1;
            break;
        }
    }
    
    int g = n / 10;
    int s = n * 3 / 10;
    int b = n * 6 / 10;

    if (rank <= g) cout << "gold\n";
    else if (rank <= s) cout << "silver\n";
    else if (rank <= b) cout << "bronze\n";
    else cout << "iron\n";
}

J

路径搜索

• n：节点数量（位置）
• m：火源数量
• s：玩家起始位置
• fire：火源位置数组
• g：无向图的邻接表表示

第一步：计算火势蔓延距离（BFS）

vector<int> fd(n+1,1e9);  // 火到达每个节点的最短时间
queue<int> q;
for(auto x:fire){ fd[x]=0; q.push(x); }
while(!q.empty()){
    int u=q.front(); q.pop();
    for(auto v:g[u]) if(fd[v]>fd[u]+1){ fd[v]=fd[u]+1; q.push(v); }
}

• 从所有火源开始多源BFS
• 计算火到达每个节点的最短时间

第二步：玩家逃生路径搜索（BFS）

vector<int> sd(n+1,1e9);  // 玩家到达每个节点的最短时间
q.push(s);
sd[s]=0;

// 特殊检查：如果起点是叶子节点且没有火，直接成功
if(g[s].size()<=1 && fd[s]>0){ cout<<0; return 0; }

while(!q.empty()){
    int u=q.front(); q.pop();
    for(auto v:g[u]){
        // 关键条件：玩家能比火先到达v，且不会在到达时遇到火
        if(sd[v]>sd[u]+1 && sd[u]+1<fd[v]){
            sd[v]=sd[u]+1;
            // 如果到达叶子节点，逃生成功
            if(g[v].size()==1){ cout<<sd[v]; return 0; }
            q.push(v);
        }
    }
}

逃生条件：

1. 时间优势：sd[u]+1 < fd[v] - 玩家到达下一节点的时间必须早于火势
2. 安全边界：到达叶子节点（g[v].size() == 1）即视为逃生成功
3. 起点检查：如果起点就是叶子节点且没有火，直接逃生成功

• 时间复杂度：O(n + m) - 两次BFS遍历
• 空间复杂：O(n + m) - 存储图和距离数组
• 策略：玩家必须始终比火势快一步，最终到达地图边界（叶子节点）

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m,s;
    cin>>n>>m>>s;
    vector<int> fire(m);
    for(int i=0;i<m;i++) cin>>fire[i];
    vector<vector<int>> g(n+1);
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int> fd(n+1,1e9), sd(n+1,1e9);
    queue<int> q;
    for(auto x:fire){ fd[x]=0; q.push(x); }
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(auto v:g[u]) if(fd[v]>fd[u]+1){ fd[v]=fd[u]+1; q.push(v); }
    }
    if(g[s].size()<=1 && fd[s]>0){ cout<<0; return 0; }
    q.push(s);
    sd[s]=0;
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(auto v:g[u]){
            if(sd[v]>sd[u]+1 && sd[u]+1<fd[v]){
                sd[v]=sd[u]+1;
                if(g[v].size()==1){ cout<<sd[v]; return 0; }
                q.push(v);
            }
        }
    }
    cout<<-1;
}

N

计算一个数字与其下一个回文数之差 主要函数 makepal(string s) - 生成大于等于原数的最小回文数 步骤： 镜像构造：将字符串前半部分镜像到后半部分

string t = s;
for(int i=0; i<n/2; i++) t[n-1-i] = t[i];

检查有效性：如果镜像后的数 ≥ 原数，直接返回

if(t >= s) return t;

进位处理：从中间向左边找到第一个非9的数字进行进位

int i = (n-1)/2;
while(i >= 0 && s[i] == '9') { s[i] = '0'; i--; }

特殊情况：如果所有数字都是9（如999），生成100...001

if(i < 0) {
    string r = "1";
    for(int k=0; k<n-1; k++) r.push_back('0');
    r.push_back('1');
    return r;
}

重新镜像：进位后重新构造回文数

s[i]++;
for(int j=0; j<n/2; j++) s[n-1-j] = s[j];

sub(string a, string b) - 大数减法 实现字符串表示的大数减法，处理借位和前导零。

主流程

1. 读取输入数字 n
2. 调用 makepal(n) 得到下一个回文数 p
3. 计算 p - n 的差值 m
4. 输出差值（如果为0输出"0"）

#include <bits/stdc++.h>
using namespace std;
string makepal(string s){
    int n=s.size();
    string t=s;
    for(int i=0;i<n/2;i++) t[n-1-i]=t[i];
    if(t>=s) return t;
    int i=(n-1)/2;
    while(i>=0 && s[i]=='9'){ s[i]='0'; i--; }
    if(i<0){
        string r="1";
        for(int k=0;k<n-1;k++) r.push_back('0');
        r.push_back('1');
        return r;
    }
    s[i]++;
    for(int j=0;j<n/2;j++) s[n-1-j]=s[j];
    return s;
}
string sub(string a,string b){
    int n=a.size(), m=b.size();
    while(m<n){ b = "0"+b; m++; }
    string res="";
    int carry=0;
    for(int i=n-1;i>=0;i--){
        int x=a[i]-'0';
        int y=b[i]-'0';
        int v=x-y-carry;
        if(v<0){ v+=10; carry=1; } else carry=0;
        res.push_back(char('0'+v));
    }
    while(res.size()>1 && res.back()=='0') res.pop_back();
    reverse(res.begin(),res.end());
    return res;
}
int main(){
    string n;
    if(!(cin>>n)) return 0;
    string p=makepal(n);
    string m=sub(p,n);
    if(m.size()==0) cout<<"0\n"; else cout<<m<<"\n";
    return 0;
}

B

最优成本计算

给定一个数组，需要将所有元素"连接"起来，有两种操作方式：

• 方式A：成本 = 差值 × A（按差值付费）
• 方式B：成本 = B（固定费用 目标是以最小总成本连接所有元素。 第一步：排序

sort(v.begin(), v.end());

将数组排序，这样相邻元素的差值最小，为后续计算做准备。

第二步：计算最小成本

long long ans = min(v[0]*A, B);  // 处理第一个元素
for(int i=1; i<n; i++) 
    ans += min((v[i]-v[i-1])*A, B);  // 处理后续间隔

逻辑解释：

• 第一个元素：从0位置连接到第一个元素 v[0]
  • 方式A：成本 = v[0] × A（假设从0开始）
  • 方式B：成本 = B（固定费用
• 后续间隔：连接相邻元素 v[i-1] 和 v[i]
  • 方式A：成本 = (v[i] - v[i-1]) × A
  • 方式B：成本 = B 对于每个间隔，独立选择更便宜的连接方式：
• 如果间隔很小，使用方式A（按差值付费）更划算
• 如果间隔很大，使用方式B（固定费用）更划算

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n; long long A,B;
    cin>>n>>A>>B;
    vector<long long> v(n);
    for(int i=0;i<n;i++) cin>>v[i];
    sort(v.begin(),v.end());
    long long ans=min(v[0]*A,B);
    for(int i=1;i<n;i++) ans+=min((v[i]-v[i-1])*A,B);
    cout<<ans;
}

C

数论计算，用于找到第k个有序数对并计算其平方和的特定值

代码要解决的核心问题是：找到所有正整数对 (i, j) 按 i×j 排序后的第k对，并计算所有满足 i×j ≤ T 的数对 (i² × j²) 的和模 998244353。 modinv(a, m) - 模逆元计算 使用扩展欧几里得算法计算模逆元，用于除法操作。 sum_sq_mod(n) - 平方和公式 计算 1² + 2² + ... + n² 模 MOD，使用公式：

count_tau(T) - 计算数对数量 计算满足 i×j ≤ T 的正整数对 (i, j) 的数量，即：

使用数论分块优化，避免O(T)复杂度。 sum_tau_m2_mod(M) - 计算平方和

计算所有满足 i×j ≤ M 的数对 (i² × j²) 的和：
同样使用数论分块优化。

shixian 第一步：二分查找找到第k个数对对应的T

while (count_tau(hi) < k) hi <<= 1;
while (lo < hi) {
    ll mid = (lo + hi) / 2;
    if (count_tau(mid) >= k) hi = mid;
    else lo = mid + 1;
}
ll T = lo;

第二步：定位第k个数对

ll c_prev = count_tau(T - 1);
ll r = k - c_prev;  // 在乘积等于T的数对中的排名

第三步：计算结果

ll sum_before = sum_tau_m2_mod(T - 1);  // 所有i×j < T的平方和
ll ans = (sum_before + r * T²) % MOD;   // 加上第k个位置的贡献

复杂度

• 时间复杂度：O(√T log T) - 数论分块 + 二分查找
• 空间复杂度：O(1) - 只使用常数空间

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;
ll modinv(ll a, ll m) {
    ll m0 = m, t, q;
    ll x0 = 0, x1 = 1;
    if (m == 1) return 0;
    while (a > 1) {
        q = a / m;
        t = m; m = a % m; a = t;
        t = x0; x0 = x1 - q * x0; x1 = t;
    }
    if (x1 < 0) x1 += m0;
    return x1;
}
ll sum_sq_mod(ll n) {
    n %= MOD;
    ll a = n * ((n + 1) % MOD) % MOD;
    ll b = (2 * n + 1) % MOD;
    ll inv6 = modinv(6, MOD);
    return a * b % MOD * inv6 % MOD;
}
ll count_tau(ll T) {
    if (T <= 0) return 0;
    ll res = 0;
    ll d = 1;
    while (d <= T) {
        ll q = T / d;
        ll r = T / q;
        res += q * (r - d + 1);
        d = r + 1;
    }
    return res;
}
ll sum_tau_m2_mod(ll M) {
    if (M <= 0) return 0;
    ll res = 0;
    ll d = 1;
    while (d <= M) {
        ll q = M / d;
        ll r = M / q;
        ll sum_d2 = (sum_sq_mod(r) - sum_sq_mod(d - 1) + MOD) % MOD;
        ll s2q = sum_sq_mod(q);
        res = (res + sum_d2 * s2q % MOD) % MOD;
        d = r + 1;
    }
    return res;
}

int main() {
    ll k;
    cin >> k;
    ll lo = 1, hi = 1;
    while (count_tau(hi) < k) hi <<= 1;
    while (lo < hi) {
        ll mid = (lo + hi) / 2;
        if (count_tau(mid) >= k)
            hi = mid;
        else
            lo = mid + 1;
    }
    ll T = lo;
    ll c_prev = count_tau(T - 1);
    ll r = k - c_prev;
    ll sum_before = sum_tau_m2_mod(T - 1);
    ll ans = (sum_before + r % MOD * (T % MOD) % MOD * (T % MOD) % MOD) % MOD;
    cout << ans << "\n";
    return 0;
}

A

递归的索引映射算法 1.问题理解 代码将一个大的索引集合通过递归的方式映射到一个小的输出集合，同时保持某种特定的顺序关系。

• vector<long long> s：存储每一层的大小
• s[0] = n（初始大小）
• 通过递归规则不断计算 s[t] 直到大小 ≤ 3 递归规则 大小计算（main函数中）：

while (s[t] > 3) {
    long long k = s[t] / 5;
    long long r = s[t] % 5;
    long long next_size;
    if (r < 4) {
        next_size = k + r;
    } else {
        next_size = k;
    }
    s.push_back(next_size);
    t++;
}

规则解释：

• 将当前层大小除以5：k = s[t] / 5, r = s[t] % 5
• 如果余数 r < 4，下一层大小 = k + r
• 如余数 r = 4，下一层大小 = k
  索引映射（get_index函数）：

long long get_index(int t, long long i) {
    if (t == 0) {
        return i + 1;  // 基础情况
    } else {
        long long k2 = s[t - 1] / 5;
        long long r2 = s[t - 1] % 5;
        if (i < k2) {
            return get_index(t - 1, 4 + 5 * i);
        } else {
            return get_index(t - 1, 5 * k2 + (i - k2));
        }
    }
}

构建层次结构：从n开始，不断应用规则直到大小 ≤ 3 输出最终大小：s[T] 其中 T 是最后一层 映射索引：对最终集合中的每个索引，递归计算其在原始集合中的对应值

一开始我用的模拟的办法，但是内存限制，python也不行

#include <iostream>
#include <vector>
using namespace std;

int wswg; 

vector<long long> s;

long long get_index(int t, long long i) {
    if (t == 0) {
        return i + 1;
    } else {
        long long k2 = s[t - 1] / 5;
        long long r2 = s[t - 1] % 5;
        if (i < k2) {
            return get_index(t - 1, 4 + 5 * i);
        } else {
            return get_index(t - 1, 5 * k2 + (i - k2));
        }
    }
}

int main() {
    long long n;
    cin >> n;
    s.push_back(n);
    int t = 0;
    while (s[t] > 3) {
        long long k = s[t] / 5;
        long long r = s[t] % 5;
        long long next_size;
        if (r < 4) {
            next_size = k + r;
        } else {
            next_size = k;
        }
        s.push_back(next_size);
        t++;
    }
    int T = s.size() - 1;
    cout << s[T] << endl;
    if (s[T] > 0) {
        for (long long i = 0; i < s[T]; i++) {
            cout << get_index(T, i);
            if (i < s[T] - 1) {
                cout << " ";
            }
        }
        cout << endl;
    }
    return 0;
}