2025--ACM&TC第三次招新赛题解

题目难度：

签到：9、12

简单：2、5、8、11

中等：3、4、7

困难：1、6、10

题解

1、中位数

题目给出的n为奇数，那么最终的中位数一定是中间的那个数，于是我们可以二分答案，不断地去枚举答案

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

int a[200005];
int n, k;

bool check(int x) {
    int sum = 0;
    int m = (n + 1) / 2; 
    for (int i = m; i <= n; i++) {
        if (a[i] < x) {
            sum += x - a[i];  
            if (sum > k) return 1; 
        }
    }
    return sum > k;  
}

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

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n); 

    int l = a[(n + 1) / 2], r = 1e18;  
    while (l + 1 < r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            r = mid; 
        } else {
            l = mid; 
        }
    }
    cout << l << '\n';  

}

2、怕挂科的George

这题考的就是结构体的排序，也是看看一些人补没补题，如果第一场招新赛的第 4 题没写出来但补了的话，这一题也是肯定能写出来的。然后就是平均数记得开float或者double，感觉会有很多人开int然后WA好多发（学长赛前预测），学长出题的时候专门手搓了几个卡 int 的数据，嘿嘿~。

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"

struct stus{
    int s,a;
}stu[105];

bool cmp(stus c,stus d){
    return c.s<d.s;
}

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
    int n,m;
    cin>>n>>m;
    double sum=0;
    for(int i=1;i<=n;++i){
        cin>>stu[i].s>>stu[i].a;
        sum+=stu[i].a;
        if(stu[i].s==m&&stu[i].a<60)
            stu[i].a=60;
    }
    double avg=sum/n;
    for(int i=1;i<=n;++i){
        if(stu[i].s!=m&&stu[i].a>=avg){
            stu[i].a=max(stu[i].a-2,0);
        }
    }
    sort(stu+1,stu+n+1,cmp);
    for(int i=1;i<=n;++i){
        cout<<stu[i].a<<" ";
    }
    cout<<endl;
    return 0;
}

3、位运算终于来了

这道题你首先要清楚 异或运算是什么，当前位相同为0，不同为1，这样根据这个规律我们可以在a的当前位与b的当前位不同时让a去异或2的当前位次幂(1,10,100,1000....)，比如a：(1001), b: (110),当枚举到第1位（从后往前）a为0，b为1那需要让a异或2的1次方，可以让a的当前位变为1，这样你会发现当到达当前位枚举过的位都是相同的，如果枚举到2的k次方大于a，那么不可能让a最终等于b，当然还有别的做法

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

int ksm(int a, int b){
    int ans = 1;
    while(b){
        if(b % 2){
            ans = ans * a;
        }
        b = b / 2;
        a = a * a;
    }
    return ans;
}
void solve(){
    int a, b;
    cin >> a >> b;
    if(a == b){
        cout << 0 << '\n';
        return;
    }
    int aa = a;
    vector<int> ans;
    string s;
    for(int i = 0;; i++){
        if (a == 0 && b == 0) break;
        int x = ksm(2, i);
        if((a & 1) != (b & 1)){
            ans.push_back(x);
            if(x > aa){
            cout << -1 << '\n';
            return;
        }
        }
        a = a >> 1;
        b = b >> 1;
    }
    cout << ans.size() << '\n';
    for(auto t : ans){
        cout << t << ' ';
    }
    cout << '\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while(t--){
        solve();
    }
}

4、我要打瓦！颗秒！！棒棒棒棒！！！

这题考的就是你们高中学的n的平方的前n项和通项公式（不知道你们老师有没有让背过，大部分老师应该都让背过）。不要觉得这题很奇怪，数学在计算机及 ACM 中很重要，说白了对于 ACM 来说编程语言只是工具，解题思路大部分都是靠数学思维，包括你们学的高数，和以后学的线代、离散、概率论等都会是 ACM 的考点（我记得去年招新赛，我们学长给我们出了一道二项式定理，感兴趣的自己可以看一下），计算机和数学相关性很大的，比如数学中的离散和计算机中的数据结构重合度很高，内容大部分都一样。这题的题解废话有点多了，主要也是想要让你们了解一下数学和计算机的关系，下面是正式题解：

随便举几个例子画画图就能知道移动的路线尽可能往中间靠才能让 ans 最大化，所以使 ans 最大化的路线就是先向右再向下，这样一直循环到 (n,n) 。通过下面两个重要的数学公式，可以推导出答案为：n * (n + 1) * (4 * n - 1) / 6。需要注意此题除法放在最后，避免前面没除尽，出现小数造成误差，模数 2022 最后可以和分母 6 约分成 337 ；还有就是边运算边取模，因为计算过程中会超出 long long 的范围 1e18 ；以及n也需要开long long ，因为n参与下面ans的计算了。具体计算过程见下图，黄线和就是n的平方的前n项和通项公式，橙线和则可以拆成等差数列的前n项和通项公式与n的平方的前n项和通项公式的和。

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"

const int mod=1e9+7;

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        long long n;
        cin>>n;
        long long ans=337*n%mod*(n+1)%mod*(4*n-1)%mod;
        cout<<ans<<endl;
    }
    return 0;
}

5、带派不老铁?

起始位置由 ( 0 , 0 ) 到 ( x , y ) ，其结果只有三种情况。
1.输出结果为-1：当x=y或x=y+1或y=1时，此时一定不满足题目要求，输出-1；
2.输出结果为2：满足y>x即可
3.输出结果为3：剩下的情况都是3步

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int x,y;
        cin>>x>>y;
        if(x==y||x==y+1||y==1)
            cout<<-1<<endl;
        else if(x<y)
            cout<<2<<endl;
        else
            cout<<3<<endl;
    }
    return 0;
}

//
// ⠀⠀⠀             ⠀⢸⣿⣿⣿⠀⣼⣿⣿⣦⡀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠀⠀⠀ ⠀⢸⣿⣿⡟⢰⣿⣿⣿⠟⠁
// ⠀⠀⠀⠀⠀⠀⠀⢰⣿⠿⢿⣦⣀⠀⠘⠛⠛⠃⠸⠿⠟⣫⣴⣶⣾⡆
// ⠀⠀⠀⠀⠀⠀⠀⠸⣿⡀⠀⠉⢿⣦⡀⠀⠀⠀⠀⠀⠀ ⠛⠿⠿⣿⠃
// ⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⠀⠀⠹⣿⣶⡾⠛⠛⢷⣦⣄⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣧⠀⠀⠈⠉⣀⡀⠀ ⠀⠙⢿⡇
// ⠀⠀⠀⠀⠀⠀⢀⣠⣴⡿⠟⠋⠀⠀⢠⣾⠟⠃⠀⠀⠀⢸⣿⡆
// ⠀⠀⠀⢀⣠⣶⡿⠛⠉⠀⠀⠀⠀⠀⣾⡇⠀⠀⠀⠀⠀⢸⣿⠇
// ⢀⣠⣾⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⢀⣼⣧⣀⠀⠀⠀⢀⣼⠇
// ⠈⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡿⠋⠙⠛⠛⠛⠛⠛⠁
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⡿⠋⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⢾⠿⠋ 
//

6、搜索板子题

和题目名一样，就是搜索板子题， BFS 和 DFS 都能写，这里放的是 BFS 的AC码，主要就是让学会搜索的人都能AC，所以也没涉及任何思维，就纯板子。考虑到这是你们培训讲的最难的算法，估计有好多人还没学，所以归到了困难题。

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"

typedef pair<int, int> pii;

int w, h;
char graph[1001][1001];
bool visited[1001][1001];

int cnt = 0;

void bfs(int startx, int starty) {
    queue<pii> q;
    q.push({startx, starty});
    visited[startx][starty] = true;
    cnt++;

    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};

    while (!q.empty()) {
        int currentx = q.front().first;
        int currenty = q.front().second;
        q.pop();

        for (int i = 0; i < 4; ++i) {
            int newx = currentx + dx[i];
            int newy = currenty + dy[i];

            if (newx >= 0 && newx < h && newy >= 0 && newy < w && graph[newx][newy] == '.' && !visited[newx][newy]) {
                q.push({newx, newy}); 
                visited[newx][newy] = true;
                cnt++;
            }
        }
    }
}

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

    int startx, starty;
    cin >> w >> h;

    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cin >> graph[i][j];
            if (graph[i][j] == '@') {
                startx = i;
                starty = j;
            }
        }
    }

    bfs(startx, starty);
    cout << cnt << endl;

    return 0;
}

7、数好数字

这题是一个简单数论，虽然难度不高，但由于是数论我们还是把它归为了中等题。

大概就是根据好数的周期性，以210为周期，每个210内的好数数量都一样。

先计算一下 2 到 r 的好数数量，再计算一下 2 到 l 的好数数量，然后一减就是 l 到 r 的好数数量。

注意开long long！！！

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

const int LCM = 210; // 2*3*5*7=210

// 判断一个数是否不被2、3、5、7中的任何一个整除
bool good(int x) {
    return x % 2 > 0 && x % 3 > 0 && x % 5 > 0 && x % 7 > 0;
}

// 计算[0, x)范围内满足good条件的数字数量
int get_naive(int x) {
    int ans = 0;
    for (int i = 1; i <= x; ++i) {
        if (good(i)) {
            ans++;
        }
    }
    return ans;
}

// 优化计算：利用210是2、3、5、7的最小公倍数，减少重复计算
long long get(long long r) {
    return (r / LCM) *48 + get_naive(r % LCM);
}  

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

    while (t--) {
        long long l, r;
        cin >> l >> r;
        // 计算[l, r]范围内满足条件的数字数量
        cout << get(r) - get(l-1) << endl;
    }

    return 0;
}

8、什么？你...你竟然是尊贵的传奇王者？

简单数学题，由奇+奇=偶、偶+偶=偶、奇+偶=奇，所以只需统计一下奇偶数量，如果奇偶数量相等，则就能恰好分割，则输出 “ Yes ” ，否则输出 “ No ” 。

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"

int a[205]={};

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int cntj=0,cnto=0;
        int n;
        cin>>n;
        for(int i=0;i<2*n;++i){
            cin>>a[i];
            if(a[i]%2==1)
                cntj++;
            else
                cnto++;
        }
        if(cntj==cnto)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;

    }
    return 0;
}

9、这是什么图形

这是一道小学题，正方形的性质可知对角线相等，那么一半都相等

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int l, r, d, u;
        cin >> l >> r >> d >> u;
        if (l == r && d == u && l == d) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
    return 0;
}

10、haxin学姐的旅程规划

让我们把陈述中给出的等式变形重新写成 $c{i+1}−b{c{i+1}}=c{i}−b{c{i}}$ 。这意味着我们旅行计划中路径上的所有城市将具有相同的 $i−b_{i}$ 值，即索引值减去对应的美丽值，这个性质可以通过上面那种对题目中的等式进行变形得到，也可以通过画图得知，就自己画两个线段然后就能琢磨出来。

这题用到C++的一个map容器，没学过的学一下，这个容器挺重要的，大概就是能将两个量关联起来。这一题的思路就是先遍历一遍数组b，并用map的第一个参数放 $i−b{i}$ 值，将 $i−b{i}$ 值相同的元素的值累加起来存到第二个参数中，这样就把 $i−b{i}$ 值和与它相对应的美丽值之和关联在一起了，通过第一个参数的值就能直接访问到与之对应的第二个参数的值。此外，把数组从头遍历到尾，就是满足了题目中序列严格递增的要求。最后再遍历一遍map，map中最大的第二个参数值就是答案，即最大美丽值。另外，数据范围上，虽然n和 $b{i}$ 都没超过 int 范围，但是答案有可能将 n 个 $b_{i}$ 相加，这就超过了 int 范围，所以要开long long，map的第二个参数和 ans 都要开 long long。

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"

int b[200050]={};

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
    int n;
    cin>>n;
    map<int,long long>mapp;
    for(int i=1;i<=n;++i){
        cin>>b[i];
    }
    int x;
    for(int i=1;i<=n;++i){
        x=i-b[i];
        mapp[x]+=b[i];
    }
    long long ans=0;
    for(auto p:mapp){
        if(p.second>ans)
            ans=p.second;
    }
    cout<<ans<<endl;
    return 0;
}

11、挑剔的猫

思路：在开始之前，我们先求出所有元素的绝对值，因为它们的符号并不重要。然后，如果数组的第一个元素等于或小于数组的[n/2]+1最小元素，则答案是可能的。否则，答案就是不可能的

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

const int N=1e5+10;
int a[N];

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n;scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        int f=abs(a[1]);
        int cnt=0;
        for(int i=2;i<=n;i++){
            int z=abs(a[i]);
            if(z<=f)
                cnt++;
        }
        if(cnt+1<=(n/2+1))
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    return 0;
}

12、这是啥博弈？

诈骗题，提示里也提醒了，输出获胜者名字的第一个字母，而两个人的第一个字母都是 ’ B ‘ ，所以直接输入n，然后直接输出 ’ B ‘ 就行了。但对于这题来说，也可以不用输入 n ，直接输出 ’ B ‘ ，因为AC的标准就是只看你输出的数据和后台的数据是否能完全吻合，不看输入。不要觉得这种诈骗题很奇怪，这都是我们平常碰到过的，很多比赛都有，比如我们学校前年举办的新生河南省邀请赛里就有一道，如果感兴趣的话，可以看看。

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
    cout<<'B'<<endl;
    return 0;
}

//
// ⠀⠀⠀             ⠀⢸⣿⣿⣿⠀⣼⣿⣿⣦⡀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠀⠀⠀ ⠀⢸⣿⣿⡟⢰⣿⣿⣿⠟⠁
// ⠀⠀⠀⠀⠀⠀⠀⢰⣿⠿⢿⣦⣀⠀⠘⠛⠛⠃⠸⠿⠟⣫⣴⣶⣾⡆
// ⠀⠀⠀⠀⠀⠀⠀⠸⣿⡀⠀⠉⢿⣦⡀⠀⠀⠀⠀⠀⠀ ⠛⠿⠿⣿⠃
// ⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⠀⠀⠹⣿⣶⡾⠛⠛⢷⣦⣄⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣧⠀⠀⠈⠉⣀⡀⠀ ⠀⠙⢿⡇
// ⠀⠀⠀⠀⠀⠀⢀⣠⣴⡿⠟⠋⠀⠀⢠⣾⠟⠃⠀⠀⠀⢸⣿⡆
// ⠀⠀⠀⢀⣠⣶⡿⠛⠉⠀⠀⠀⠀⠀⣾⡇⠀⠀⠀⠀⠀⢸⣿⠇
// ⢀⣠⣾⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⢀⣼⣧⣀⠀⠀⠀⢀⣼⠇
// ⠈⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡿⠋⠙⠛⠛⠛⠛⠛⠁
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⡿⠋⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⢾⠿⠋ 
//