A

考察点： $scanf$ 格式化输入

签到题，直接输入输出即可。

时间复杂度: $O(1)$

ACcode

#include <iostream>
#define endl '\n'
using namespace std;
int main(){
    int a, b, c;
    scanf("%d-%d-%d", &a, &b, &c);
    cout << a << ' ' << b << ' ' << c << endl;
    return 0;
}

B

考察点：for循环暴力、字符串

循环暴力遍历所有的四个字符，如果能拼成"ming"就给答案+1，输出答案即可。

时间复杂度： $O(n^4)$

ACcode

#include <iostream>
#define endl '\n'
using namespace std;
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    string s;
    cin >> s;
    int n = s.size();
    int cnt = 0;
    for(int i = 0; i < n - 3; i++){
        for(int j = i + 1; j < n - 2; j++){
            for(int k = j + 1; k < n - 1; k++){
                for(int l = k + 1; l < n; l++){
                    if(s[i] == 'm' && s[j] == 'i' && s[k] == 'n' && s[l] == 'g'){
                        cnt++;
                    }
                }
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

C

考察点：构造、思维、贪心

单调不增包含单调递减，只需将这个排列逆序输出，就能保证 $a_{i-1} > a_{i}\ ( 1 < i \leq n)$ ，符合题目条件。

时间复杂度： $O(n的总和)$

ACcode

#include <iostream>
#define endl '\n'
using namespace std;

void solve(){
    int n;
    cin >> n;
    for(int i = n; i > 0; i--) cout << i << ' ';
    cout << endl;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

D

考察点：排序、贪心

任取一个长度为 $k$ 的子序列就是在数组中任取 $k$ 个数，想让和最大，只需贪心取最大的 $k$ 个数，将数组排序后输出后 $k$ 个数的和即可。

时间复杂度: $O(n)$

ACcode

#include <iostream>
#include <algorithm>
#define endl '\n'
using namespace std;

int a[1000005];

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, k;
    cin >> n >> k;
    long long sum = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    sort(a, a + n);
    for(int i = n; i >= n - k; i--) sum += a[i];
    cout << sum << endl;
    return 0;
}

E

考察点：前缀和

取长度为 $k$ 的子数组就是在数组中取一段长度为 $k$ 的区间，遍历所有可能的区间左端点（右端点），用前缀和来计算区间和，每次更新最大区间和即可。

时间复杂度: $O(n)$

ACcode

#include <iostream>
#include <algorithm>
#define endl '\n'
using namespace std;

int a[1000005];
long long pre[1000005];

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, k;
    cin >> n >> k;
    long long res = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }
    for(int i = 0; i <= n - k; i++){
        res = max(res, pre[i + k] - pre[i]);
    }
    cout << res << endl;
    return 0;
}

F

考察点：结构体、sort

用一个三个元素的结构体表示每道菜，创建一个结构体数组，输入 $n$ 道菜的信息，然后按题意要求（按美味值从高到低排，如果美味值相同，按饱腹值从低到高排）写排序函数， $sort$ 排序，然后遍历一遍数组，看饱腹值能不能吃当前食物，能吃就把价值加到答案即可。

注意：如果一道菜吃不下就看小明想吃的下一道，而不是直接不吃，所以这个时候不能直接将循环 $break$ ，一定要把数组遍历完。

时间复杂度： $O(n)$

ACcode

#include <iostream>
#include <algorithm>
#define endl '\n'
using namespace std;

struct Food{
    int a, b, c;
}p[200005];

bool cmp(Food a, Food b){
    if(a.a == b.a) return a.b < b.b;
    return a.a > b.a; 
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >>m;
    for(int i = 0; i < n; i++){
        cin >> p[i].a >> p[i].b >> p[i].c;
    }
    sort(p, p + n, cmp);
    int sum = 0;
    long long res = 0;
    for(int i = 0; i < n; i++){
        if(sum + p[i].b <= m){
            sum += p[i].b;
            res += p[i].c;
        }
    }
    cout << res << endl;
    return 0;
}

G

考察点：二分答案

一眼二分答案，答案的右边界初步计算 $n^2$ 会爆 $int$ ，那就在 $long long$ 的范围( $0$ ~ $10^{18}$ )搜， $check$ 函数就是遍历每个打包员，看其在 $mid$ 分钟能打包多少个快递（ $a[i]* n^2 = x \Rightarrow n = \sqrt {x / a[i]}$ ），看所有的打包员总共能打包的快递数是否 $\ge m$ 即可，如果满足条件就继续向左找（ $r = mid$ ），看看还有没有分钟数更少的方案。

时间复杂度: $O(log(10^{18})\times n)$

ACcode

#include <iostream>
#include <algorithm>
#include <cmath>
#define endl '\n'
using namespace std;

int n, m;
int a[200005];

bool check(long long x){
    long long sum = 0;
    for(int i = 0; i < n; i++){
        sum += sqrt(x / a[i]);
        if(sum >= m) return true;
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    long long l = 0, r = 1e18;
    while(l < r){
        long long mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}

H

考察点：数学、贪心

这题的数字可以用整形输入，然后用 $while$ 循环把数的一位一位取出来，存到 $vector$ 或数组里，再翻转，但比较麻烦，其实可以直接用字符串表示这个数。从右到左找到第一个 $a[i] < a[i + 1]$ 的地方，如果找不到就直接输出 $-1$ ，把这个位置存下来。从这个位置往后遍历，把最后一个比 $a[i]$ 大的数字和 $a[i]$ 交换，然后把后面所有的数升序排列，这个时候的数就是题里的答案。

时间复杂度: $O(T \times n.size())$

ACcode1

#include <iostream>
#include <algorithm>
#include <cmath>
#define endl '\n'
using namespace std;

void solve(){
    string a;
    cin >> a;
    int n = a.size();
    int pos1 = -1, pos2 = -1;
    for(int i = n - 2; i >= 0; i--){
        if(a[i] < a[i + 1]){
            pos1 = i;
            break;
        }
    }
    if(pos1 == -1){
        cout << -1 << endl;
        return;
    }
    for(int i = n - 1; i > pos1; i--){
        if(a[i] > a[pos1]){
            pos2 = i;
            break;
        }
    }
    swap(a[pos1], a[pos2]);
    sort(a.begin() + pos1 + 1, a.end());
    cout << a << endl;
}   

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

这题还有一种巧妙的解法，用 $<algorithm>$ 库中的 $next\_permutation$ 函数，这个函数会尝试将给定范围内的元素调整为字典序的下一个排列。

如果存在下一个排列，它会返回 $true$ ，并且将元素排列成下一个字典序排列。

如果不存在下一个排列（即当前排列已经是字典序的最大排列），它会返回 $false$ ，并将元素排列成最小排列（即升序排列）。

时间复杂度: $O(T \times n.size())$

ACcode2

#include <iostream>
#include <algorithm>
#define endl '\n'
using namespace std;

void solve(){
    string a;
    cin >> a;
    if(next_permutation(a.begin(), a.end())){
        cout << a << endl;
    } 
    else{
        cout << -1 << endl;
    }
}   

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

I

考察点：模拟、STL、字符串

按题意模拟，小明喜欢的课和喜欢程度用 $map$ ，看一门课选没选过可以用 $set$ 或 $map$ ，课表可以用数组或 $vector$ 存，按题意处理每次查询、改变对应的信息即可。

时间复杂度: $O((n + m)logn)$

ACcode

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define endl '\n'
using namespace std;

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    vector<vector<string>> a(8, vector<string>(6, "None"));
    map<string, int> ma;
    set<string> se;
    int n, m;
    cin >> n >> m;
    vector<string> s(n);
    for(int i = 1; i <= 7; i++){
        a[i][5] = "SYUCTACM";
    }
    for(int i = 1; i <= 5; i++){
        a[6][i] = "SYUCTACM";
    }
    a[7][1] = a[7][2] = "SYUCTACM";
    a[3][3] = a[3][4] = "SYUCTACM";
    for(int i = 0; i < n; i++){
        cin >> s[i];
    }
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        ma[s[i]] = x;
    }
    for(int i = 0; i < m; i++){
        string t;
        int b, c;
        cin >> t >> b >> c;
        if(!ma.count(t)) continue;
        if(se.count(t)) continue;
        if(a[b][c] == "SYUCTACM") continue;
        if(a[b][c] == "None"){
            a[b][c] = t;
            se.insert(t);
        }
        else{
            if(ma[a[b][c]] < ma[t]){
                se.erase(a[b][c]);
                a[b][c] = t;
                se.insert(t);
            }
        }
    }
    for(int i = 1; i <= 7; i++){
        for(int j = 1; j <= 5; j++){
            cout << a[i][j] << ' ';
        }
        cout << endl;
    }
    return 0;
}

J

考察点：vector去重排序、双指针/二分

这道题可以先将小明的手牌全部存到 $vector$ 里，再去重排序一下，问题就转化成了：求满足 $a[r]-a[l] - (r - l) \le k$ 的最长子数组 $a[l]$ ~ $a[r]$ ,暴力显然做不了，可以用双指针或二分来进行优化。

双指针解法： $i$ 指针遍历区间右端点， $j$ 指针遍历区间左端点，每次满足条件时用区间长度更新答案即可。

时间复杂度: $O(n)$

ACcode1

#include <iostream>
#include <algorithm>
#include <vector>
#define endl '\n'
using namespace std;

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    n = a.size();
    int res = 0;
    for(int i = 0, j = 0; i < n; i++){
        while(j < i && a[i] - a[j] - (i - j) > k){
            j++;
        }
        res = max(res, i - j + 1);
    }
    cout << min(res + k, m) << endl;
    return 0;
}

二分解法： $for$ 循环遍历每个位置作为左端点，二分查找第一个满足条件的右端点的位置，用区间长度更新答案即可。

时间复杂度: $O(nlogn)$

ACcode2

#include <iostream>
#include <algorithm>
#include <vector>
#define endl '\n'
using namespace std;

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    n = a.size();
    int res = 0;
    for(int i = 0; i < n; i++){
        int l = i, r = n - 1;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(a[mid] - a[i] - (mid - i) <= k) l = mid;
          	else r = mid - 1;
        }
        res = max(res, l - i + 1);
    }
    cout << min(res + k, m) << endl;
    return 0;
}

沈阳化工大学ACM2025春季队内赛题解

A

B

C

D

E

F

G

H

I

J