大连民族大学2025年ACM纳新赛题解

  • Easy : A J L G

  • Medium : D E F B I

  • Medium hard : C H

  • hard : K M

A.烤冷面的诱惑

提炼一下题目的意思可知，要求二元方程组 的非负整数解的个数。可以直接枚举面额为 元的钞票的张数，然后验证当 有 张时， 是否为非负整数，是则解的个数加 。

#include<stdio.h>
int main(){
    int a,b,c,x = 0,s,cnt = 0;
    scanf("%d%d%d",&a,&b,&c);
    while(a * x <= c){
        s = c - a * x;
        if(s % b == 0){
            cnt++;
        }
        x++;
    }
    printf("%d",cnt);
    return 0;
}

J.会员

知识点：模拟

输出 组数，第 天开通，每隔 天续费一次，第一次开通要 元，之后都要 元，我们按照题意模拟即可，计算离一年(天)结束的时间内要支付几次就可以了。

代码如下：

#include<stdio.h>
int main(){
    int n;
    scanf("%d", &n);
    int ans = 0,cnt = 0;
    for(int i = 0; i < n; i++){
        int d,t,w,v;
        scanf("%d %d %d %d", &d, &t, &w, &v);
        ans += w;
        cnt++;
        d += t;
        if(d <= 365){
        int m = (365 - d) / t + 1;
        ans += v * m;
        cnt += m; 
        }
    }
    printf("%d %d\n", cnt, ans);
    return 0;
}

L.小明的神奇机器

一、首先分析一下题目的意思

题目的意思就是给出一个最终结果，然后逆推出最初的结果，并输出对应次数。我们可以先假设输入的数字为 (无论奇偶)，它肯定会经过第一次操作(因为题目要求)，那么第一次操作后， 变为 。再经过第二次操作，除以 过后，此时数字变为 。即经过两次变化过后，最终得到的数 ，那最初的数，次数输出 即可。

详细代码

#include<stdio.h>
int main(){
    int n;
    scanf("%d",&n);  //输入最终的结果；
    printf("%d 2",n+1);
}

二、不同代码

由数学知识可得偶数×偶数＝偶数，奇数×偶数等于奇数。可得第一次操作后必定为偶数。诶，发现没有，从第二次操作逆推，除 变为乘 ，同样也可以变为偶数。那么我们必定能在两次操作内找到一个数 ，从第二次逆推变为 。此时设初始输入数为 ，经过第一次操作后变为。使 。于是可证 次必定能逆推出任何一个输入的结果。

#include<stdio.h>
int main(){ 
    int n; scanf("%d",&n);
    n=n*2;
    n=n+2;
    n=n/2;
    printf("%d 2",n);
}

G.逃离爆炸区题解

主要关注点是逃离那个范围，所以我们只需要知道她最终的终点到初始点的距离就可以了，设初始点在位置最终点为 只要 或者 与 的差值大于 就可以了。

 #include<stdio.h>
    int main(){
        int n,m;
        scanf("%d %d",&n,&m);
        char arr[n+1];
        scanf("%s",arr);
    //用x,y来模拟每一步行动后的落点
        int x=0,y=0;
        for(int i=0;i<n;i++){
            if(arr[i] == 'w'){
                y++;
            }
            else if(arr[i] == 'a'){
                x--;
            }
            else if(arr[i] == 's'){
                y--;
            }
            else if(arr[i] == 'd'){
                x++;
            }
        }
    //要注意x,y有可能是负数，但距离肯定是正数，要注意判断一下
        if(x > m || y > m || x < -m || y < -m){
            printf("YES\n");
        }
        else {
            printf("NO\n");
        }
        return 0;
    }

D.完完完完全平方

此题可以利用 函数开方后是浮点数，隐式转换为整型会向下取整的特性，先输出 以内最大的平方数，剩下的用 补上。

例如：

int m;
m = sqrt(5);//m=2
m = sqrt(17);//m=4

m = sqrt(27);//m=5
m*=m;//m=25

完整代码如下：

#include <stdio.h>
#include <math.h>
int main(){
    int n,num,cnt = 1;
    scanf("%d",&n);
    num = sqrt(n);
    num *= num;
    n -= num;
    cnt += n;
    printf("%d\n%d ",cnt,num);
    while(n--) printf("1 ");//当n=0时为fasle，则退出循环
    /*
    可等价于：
    while(n>0){
        printf("1 ");
        n--;
    }
    */
    return 0;
}

E.数字异世界

要求相邻单元格和为奇数，只是是奇数加偶数，所以只要奇数和偶数交替出现就可以了，一个连续的依次增大的排列就是奇数偶数交替出现，所以我们只需要将它折叠成一个矩阵就可以了。

示例矩阵：
1 2 3 4
8 7 6 5
9 10 11 12
16 15 14 13

AC代码

#include<stdio.h>
int main(){
    int n;
    scanf("%d",&n);
    int arr[n+1][n+1];
    int cnt = 1;
    for(int i=0;i<n;i++){
        //根据i的奇偶性来决定j是正序还是倒序
        if((i + 1) % 2 == 1){
            for(int j=0;j<n;j++){
                arr[i][j] = cnt;
                cnt++;
            }
        }
        else {
            for(int j=n-1;j>=0;j--){
                arr[i][j] = cnt;
                cnt++;
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            printf("%d ",arr[i][j]);
        }
        printf("\n");
    }
    return 0;
}

F.虚狩

简单来说，题面含义就是给出 个点的坐标和一个半径 ，求等概率随机选一个点并以该点为圆心、 为半径的圆能覆盖所有点的概率。由于数据小，直接记录所有点的坐标再逐一遍历即可。以下为 AC 代码

#include <stdio.h>
int main(){
    int n, r;
    scanf("%d%d", &n, &r);
    int x[11], y[11];
    for (int i = 0; i < n; i++)
        scanf("%d%d", &x[i], &y[i]);
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        int flag = 1; //判断当前点能否覆盖所有点的标志
        for (int j = 0; j < n; j++) {
            if(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2) > r * r){
                flag = 0;//如果有一个点覆盖不到则标志位置0
                break;
            }
        }
        //如果标志没被改为0，则说明当前点能覆盖所有点，计数加一
        if (flag)
            cnt++;
    }
    //输出概率
    printf("%.3f%%\n", cnt * 100.0 / n);
}

B.土豆

根据题意，我们需要确认草坪上是否有僵尸需要用小推车清除，我们可以建立一个和草坪同等大小的二维数组mark来记录每一次土豆雷爆炸时造成的伤害（每个土豆雷周围的八个格子减一，模拟爆炸造成伤害），最后检查一下mark数组中是否还有大于一的数，如果有说明该行还有幸存者僵尸，有多少行有幸存者就需要多少量小推车。（该题需要熟练的使用双循环和二维数组）

//注意这两者的区别，如果用(1)存储地图的话会吧空格也存入map数组中会
//导致结果错误
scnaf("%c",&map[i][j]);//(1)
scanf(" %c",&map[i][j]);//(2)

最后AC代码奉上

#include<stdlib.h>
#include<stdio.h>
//用dx,dy来表示i,j点周围一圈的八个方格
int dx[] = {1,1,0,-1,-1,-1,0,1};
int dy[] = {0,1,1,1,0,-1,-1,-1};
void solve(){
    int n,m;
    scanf("%d %d",&n,&m);
    char Map[n+1][m+1];
    int mark[n+1][m+1];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
          //注意空格匹配，比赛时可以经常输出数组查看自己是否存储正确
            scanf(" %c",&Map[i][j]);
            if(Map[i][j] == 'o' || Map[i][j] == '.'){
                mark[i][j] = 0;
            }
            else{
                //根据ascll码将字符转换成数字
                mark[i][j] = Map[i][j] - '0';
            }
        }
    }
    int ans = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(Map[i][j] == 'o'){
                //爆炸模拟，注意检查是否越界
                for(int k=0;k<8;k++){
                    int fx = i+dx[k];
                    int fy = j+dy[k];
                    if(fx >= 0 && fy >=0 && fx < n && fy < m)
                    mark[fx][fy]--;
                }
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
           /*当发现幸存者时，需要的小推车加一，同时该行就不用再继续检查了，不管该行有多少僵尸都只需要一轮小推车。*/
            if(mark[i][j] > 0){
                ans++;
                break;
            }
        }
    }
    if(ans == 0){
        printf("Yes\n");
    }
    else{
        printf("No %d\n",ans);
    }
}
int main(){
    int t;
    scanf("%d ",&t);
    while(t--){
        solve();
    }
}

I.想赢？那就开锁血

判断输赢，直接考虑临界状态，临界状态就是首项为1且公差为1的等差数列，直接用等差数列的公式。

AC代码

#include<stdio.h>
#include<stdint.h> 
#define int long long
//数据范围1e9比较大，用long long，可以存更大范围的整数
int t,E,k;
int32_t main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&E,&k);
        int sum=k*(k+1)/2;//求和公式
        if(sum<=E)printf("WIN\n");
        else printf("LOSE\n");
    }
    return 0;
}

C. Shelby's Bar

此题不用想得太复杂，由于数据量巨大，即使遍历一遍 个数据都会超时，所以不可能用模拟等暴力求解的方式。由此我们想到找规律来解决这道题，规律与起始方向和最终方向以及杯子数量的奇偶性有关。

当 s == a 时

杯子数量 差异位置 差异个数 有解性 操作次数
偶数 所有奇数位 为偶数时
奇数 所有奇数位 为偶数时

当 s != a 时

杯子数量 差异位置 差异个数 有解性 操作次数
偶数 所有偶数位 为偶数时YES
奇数 所有偶数位 为偶数时YES

代码如下：

#include <stdio.h>
#include <stdbool.h>

int main() {
    int t;
    scanf("%lld", &t);
    while (t--) {
        char a, s;
        long long cnt = 0, n;
        scanf(" %c %lld %c", &s, &n, &a); 
        // 注意%c前的空格用于跳过空白字符
        bool f = false;
        if (s == a) f = true; // 第一个朝向相同
        if (n % 2 == 0) {
            cnt = n / 2;
        } else {
            if (f) cnt = n / 2 + 1;
            else cnt = n / 2;
        }
        if (cnt % 2 == n % 2) {
            printf("YES\n%lld\n", n - cnt);
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

H.去漫展吧！

用贪心解法，尽量选择结束早的，就可以选择更多活动，故按照结束时间排序。

为了方便排序，将时间都转为 为单位的整数。

注意！！时间输入方式不止 ，故要根据冒号来判断，小时和分钟。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 110
//结构体将开始时间和结束时间绑定在一起
typedef struct {
    int start;
    int end;
} Ac;
//存活动
Ac a[N];
int n;
//将字符串时间转化为以min为单位的整数
int change(const char* s) {
    int pos = -1;
    //找到冒号下标
    for (int i=0;i<strlen(s);i++) {
        if (s[i]==':') {
            pos=i;
            break;
        }
    }
    int h=0,m=0;
    for (int i=0;i<pos;i++)
        h=h*10+(s[i]-'0');
    for(int i=pos+1;i<strlen(s);i++)
        m=m*10+(s[i]-'0');
    return h*60+m;
}
//比较函数，用于快排
int cmp(const void *p1, const void *p2) {
    const Ac *x = (const Ac *)p1;
    const Ac *y = (const Ac *)p2;
    //先按结束时间从小到大排序
    if (x->end != y->end) return x->end - y->end;
    //若结束时间相同，就按开始时间从小到大排序
    return x->start - y->start;
}
//另一种，冒泡排序
void sort(Ac arr[],int len) {
    for (int i=0;i<len-1;i++) { 
        for (int j=0;j<len-1-i;j++){  
            //若前一个结束时间比后一个大就交换
            if (arr[j].end>arr[j+1].end){
                Ac temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            } 
            //若结束时间相同，就按开始时间从小到大排序
            else if (arr[j].end==arr[j+1].end){
                 //若前一个开始时间比后一个大就交换
                if (arr[j].start> arr[j+1].start) {
                    Ac temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }
    }
}
int main() {
    scanf("%d", &n);
    getchar();//防止读取字符串时读到换行符
    for (int i = 0;i<n;i++){
        char s[6], e[6];
        scanf("%5s %5s", s, e);//%5s最多读取长度为5的字符串
        //转化
        a[i].start = change(s);
        a[i].end = change(e);
    }
    //快排函数
    //qsort(a, n, sizeof(Ac), cmp);
    //调用自己写的冒泡函数
    sort(a, n);
    int t = -1;//记录前一个结束时间
    int cnt = 0;
    for (int i = 0;i<n;i++) {
        //下一个活动时间>=上一个结束时间才可以参加
        if (a[i].start >= t) {
            t = a[i].end;//更新结束时间
            cnt++;
        }
    }
    printf("%d\n", cnt);
    return 0;
}

K.胆小鬼

题解思路

有一个 的矩阵，数字范围 ，每个数字出现 次。

定义：

胆小数组

最长合格排列长度 ：从 中能构成的最长连续排列

其中：

​：所有 的列中，(那列的另外两数之和 - 最小值) 的最小值。

​：所有矩阵中值为 的元素的行号和。

核心思路

  1. 构造 B 数组对每列取最小值。

  2. 求最长排列长度k看哪些数字 连续出现在 中。直到某个数字缺失为止。

  3. 计算两部分值对每个 ：找出所有列中 。计算 = 最小的 。计算 = 所有矩阵中值为 x 的行号之和。

  4. 答案即为所有 的总和

#include <stdio.h>
#include <stdlib.h>

#define INF 0x3f3f3f3f
#define MIN(a,b) ((a)<(b)?(a):(b))

int min3(int a, int b, int c) {
    int t = a < b ? a : b;
    return t < c ? t : c;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        int v[3][3005];
        int b[3005];      // 胆小数组B
        int has[3005];    // 每列 (和 - 2*最小值)
        int used[3005] = {0}; // 标记哪些值出现过
        int cnt = 0;

        // 读入并计算
        for(int i = 0; i < 3; i++)
            for(int j = 0; j < n; j++)
                scanf("%d", &v[i][j]);

        for (int j = 0; j < n; j++){
            int mn = min3(v[0][j], v[1][j], v[2][j]);
            b[j] = mn;
            has[j] = v[0][j] + v[1][j] + v[2][j] - 2 * mn;
        }

        // 找最长连续排列 1..k
        int appear[3005] = {0};
        for (int i = 0; i < n; i++) appear[b[i]] = 1;
        int k = 0;
        for (int i = 1; i <= n; i++) {
            if (appear[i]) k++;
            else break;
        }

        // 计算第一部分：每个x=1..k的min_x
        int minx[3005];
        for (int i = 1; i <= k; i++) minx[i] = INF;
        for (int i = 0; i < n; i++) {
            if (b[i] <= k)
                if (has[i] < minx[b[i]]) minx[b[i]] = has[i];
        }

        // 计算第二部分：r_x（行号之和）
        int row_sum[3005] = {0};
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < n; j++) {
                int x = v[i][j];
                if (x <= k)
                    row_sum[x] += (i + 1);
            }

        long long ans = 0;
        for (int i = 1; i <= k; i++)
            ans += minx[i] + row_sum[i];

        printf("%lld\n", ans);
    }
    return 0;
}

M.东方明珠！

知识点：判断质数，循环

给了 组样例，记得多组输出。

根据题意，我们只需要找到一段序列，使这段序列满足以下条件：

这些数都不是合数。

这一段序列的长度大于等于 。

做法：

对于数组中每个数先进行合数判断，如果是质数，或者是（因为不是合数）就使用一个 循环来判断后面有多少个连续的数满足不是合数的条件，用一个计数器 记录就行了，然后再判断是否大等于 就行了。

示例代码：

#include<stdio.h>
#include<stdbool.h>

bool prime(int x){
    for(int i = 2; i * i <= x; i++){
        if(x % i == 0) return false;
    }
    return true;
}

int main(){
    int T;
    scanf("%d", &T);
    int a[100005];
    while(T--){
        int n,x;
        scanf("%d %d", &n, &x);
        memset(a,0,sizeof(a));
        for(int i = 0; i < n; i++){
            scanf("%d", &a[i]);
        }
        bool ok = false;
        for(int i = 0; i < n; ++i){
            int cnt = 0;
            while(i < n && prime(a[i])){
                cnt++;
                i++;
            }
            if(cnt >= x){
                ok = true;
                break;
            }
            cnt = 0;
        }
        if(!ok) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}