桂林电子科技大学 ACM 暑假课 | 7 月 21 日 ACM 作业题解

桂林电子科技大学暑假课 ACM 作业题解合集

本文整理了桂电暑假 ACM 训练营 7 月 21 日作业的 10 道典型题目及参考代码，并附带简明题解说明，供学习和复习使用。

---

1. A 简单数学题：判断数字各位是否全不相同

题目描述：

给定一个数字 n，判断它的每一位数字是否都不相同。

输入：
一个数字 n，满足 1 < n < 1000000

输出：
若各位数字均不相同，输出 YES，否则 NO。

参考代码（C）：

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

int main() {
    char A[10];
    bool used[300] = {false};
    scanf("%s", A);
    for (int i = 0; A[i] != '\0'; i++) {
        if (used[A[i]]) {
            printf("NO");
            return 0;
        }
        used[A[i]] = true;
    }
    printf("YES");
    return 0;
}

题解

• 使用数组 A[10] 存放输入的数字字符，最多 10 位，足够。

• 用布尔数组 result 标记每个字符是否出现过，出现重复即输出NO。

• 也可以用计数变量统计每个数字出现次数，出现超过一次即输出 NO。

2.B 二进制转换

题目描述

将给定数字 n 转换为二进制表示。

输入
一个数字 n，满足 1 < n < 10^5。

输出
输出数字 n 的二进制表示。

参考程序

#include <stdio.h>

int main() {
    int num[10001], i = 0, n;
    scanf("%d", &n);
    while (n > 0) {
        num[i++] = n % 2;
        n /= 2;
    }
    while (i--)
        printf("%d", num[i]);
    return 0;
}

题解

• 通过取余操作不断除以 2，将结果倒序存储，最后正序输出即可。

3.C 经典字符串问题 — 判断回文串

题目描述

给定一个字符串，判断它是否为回文串（正反相同）。

输入

• 第一行一个数字 t，表示测试组数，0 < t < 100。

• 接下来每组两行：

  • 第一行为字符串长度 n (1 < n < 1000)

  • 第二行为长度为 n 的字符串。

输出

每组数据输出 YES（回文）或 NO（非回文）。

参考程序

#include <stdio.h>
#include <string.h>

int main() {
    int n, t, i, isPalindrome;
    char str[1001];
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        scanf("%s", str);
        isPalindrome = 1;
        for (i = 0; i < n; i++) {
            if (str[i] != str[n - i - 1]) {
                isPalindrome = 0;
                break;
            }
        }
        printf(isPalindrome ? "YES\n" : "NO\n");
    }
    return 0;
}

题解

• 字符串回文判断，比较对应位置字符是否相等。
• 也可用整形数反转法判断数字是否回文（参考代码略）。

4.D 排序

题目描述

给定长度为 n 的序列，对其从小到大排序后输出。

输入

• 第一行为 n，1 < n < 1000

• 第二行 n 个整数。

输出
排序后的序列，空格分隔。

样例
输入：

10
2 5 7 8 10 1 6 11 20 35

输出：

1 2 5 6 7 8 10 11 20 35

参考程序

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    return 0;
}

题解

• C++的 sort 函数使用方便。
• 若需要从大到小排序，可以传入自定义比较函数。

5.E 改作文

题目描述

LZH 是个超差劲的学生呢。
LLF 每次批改他的英语作业都会很生气
LLF 批改作文是这样计算得分的 ：
文章里共有 n 个字母，第 i（i<=n）个字母可能大写得一分（小写 0 分），也可能小写得一分（大写 0 分） 毕竟 LLF 是经常喜怒无常的呢，看心情给分。
同时 lzh 又是个 unlucky boy 英语作文每次都必得零分（运气很差呢，每次都恰好得零分）
现在你掌握了时间回溯大法，可以穿越时空，回到过去，因为 LZH 跟你进行了 PY 交易，你要帮他在 LLF 批改作文时得满分，所以你要趁机修改他的作文
现在给出 lzh 的作文
要求帮他修改到满分

输入

• 第一行有一个数 n 代表文章长度 (1<n<1000)

• 第二行 有 n 个字母 代表 LZH 的作文

输出
输出此时可以让 LLF 给满分的作文

样例输入

10
adsadaAStY

样例输出

ADSADAasTy

参考程序

#include<stdio.h>
char str[1001];
int main(){
int n,i;
scanf("%d",&n);
scanf("%s",&str);
for(i=0;i<n;i++){
if(str[i]>='a'&&str[i]<='z')
str[i]=str[i]+'A'-'a';
else if(str[i]>='A'&&str[i]<='Z')
str[i]=str[i]+'a'-'A';}
puts(str);
return 0;
}

题解：一定要注意细节，这道题就这么多

F: 抽签 game

题目描述

由于 LZH 在国庆之前偷偷把作业给 AK 掉了，于是 LLF 提议玩一个小游戏，将写有数字的 N 个纸片放入盒子 LZH 每次可以从盒子中抽取一个纸片，并将其放回盒子中，LZH 一共可以抽取四次，LLF 给出一个数字 M，如果 LZH 四次抽到的数字之和等于 M，那么 LZH 就会平安无事，否则 LLF 会给他最喜爱的大嘴巴子。但是 LZH 玩了几次抽签游戏，每次都获得了他最喜爱的大嘴巴子，他怀疑 LLF 在搞他，于是他恼羞成怒，怒把盒子打开看看里面的到底能不能抽四次的数字之和等于 M，
现在给你一个盒子 要求你帮 LZH 检查一下盒子里面的卡片是否真的可以满足上述条件

输入

• 第一行有一个数 n 代表卡片数量 1<n<50

• 第二行有一个数 M，M 的意义如题 1<m<10000000

• 第三行有 n 个数，代表 n 张卡片上面所写的数值 1<每个数字<10000000

输出

• 如果抽四次可以满足上述条件 输出 YES

• 否则输出 NO

样例输入

5
10
1 2 3 4 5

样例输出

YES

参考程序

#include <stdio.h>
int main(){
    int str[50],i,j,k,l,n,m;
    scanf("%d",&n);
    scanf("%d",&m);
    for(i=0;i<n;i++)
    scanf("%d",&str[i]);
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            for(k=0;k<n;k++){
                for(l=0;l<n;l++){
                if(str[i]+str[j]+str[k]+str[l]==m){
                    printf("YES");
                    return 0;
                }
                }
            }
        }
    }
    printf("NO");
    return 0;
}

题解：就是穷举嘛，一个个试

G: help 庞学姐

题目描述：

庞学姐和最帅的郑学长在玩密室逃脱，经历了千辛万苦，他们终于走到了最后一关，
最后一关是一个 n*m 的迷宫，里面有许多障碍物，这时上帝给了他们一张地图，上面给出了障碍物和终点分布，因为郑学长身手比较敏捷，所以可以无视障碍物，直接到达终点，
但是庞学姐只是一个肥宅，他无法穿越障碍物，只能一步一步走到终点
并且他只会往 上 下 左 右 四个方向走
“ * “代表此处可通 “ ? “代表此处为障碍物
现在给你迷宫的地图，请帮助庞学姐找到最短到终点的路。
起点坐标为（1，1） 终点坐标为（n,m)迷宫：

****?
*??*?
**?*?
??**?
*****

输入

• 第一行为两个数 n,m 意义如上 1<n,m<50

• 下面 n 行 每行有 m 个字符 “ * “代表此处可通 “ ? “代表此处为障碍物

• 题目保证 起点和终点为 “ * “

输出

• 输出使庞学姐走出迷宫的最少步数

• 题目保证有解

样例输入

5 5
****?
*??*?
**?*?
??**?
*****

样例输出

8

参考程序

#include<stdio.h>
int n,m;
char mp[51][51];
int vis[51][51];
int dx[]={-1,1,0,0},dy[]={0,0,1,-1};
int ans=0,step=0,min=999999;
void dfs(int x,int y,int step){
    if(x<0||x>=n||y<0||y>m) return ;
    if(x==n-1&&y==m-1){ans=1;
    if(step<min) min=step;
    return ;}
    for(int i=0;i<4;i++){
        int nowx=x+dx[i];
        int nowy=y+dy[i];
        if(mp[nowx][nowy]=='*'&&vis[nowx][nowy]==0){
            vis[nowx][nowy]=1;
            dfs(nowx,nowy,step+1);
            vis[nowx][nowy]=0;
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    scanf("%s",mp[i]);
    dfs(0,0,0);
    printf("%d",min);
    return 0;
}

题解：涉及搜索请移步搜索

H: 一根绳上的蚂蚁

题目描述：

n 只蚂蚁以每秒 1cm 的速度在长为 L cm 的绳子上爬行，当蚂蚁爬到绳子端点时就会自动掉落，由于绳子太细，两只蚂蚁相遇时，他们不能交错通过，只能各自反向爬回去。
对于每只蚂蚁，我们知道它距离绳左端的距离 Xi，和它当前的头朝向，请计算所有蚂蚁经过复杂的爬行后，全部落下绳子的时刻。

输入

• 第一行为一个整数 L 代表绳子长度 （1<L<=10^6)

• 第二行一个整数 n 代表蚂蚁个数 (1<n<=10^6)

• 以下 n 行 每行有 Xi 和一个字母（R 或 L） Xi 代表蚂蚁距离左端的距离 字母代表当前的方向 （R 代表头朝右，L 代表头朝左）

输出

输出所有蚂蚁都掉落时的时刻

样例输入

10
3
2 R
6 L
7 L

样例输出

8

参考程序

#include<stdio.h>
int main(){
    int t,l,y,max=0,sum;
    char x;
    scanf("%d",&l);
    scanf("%d",&t);
    while(t--){
        scanf("%d %c",&y,&x);
        if(x=='R')
        sum=l-y;
        else
        sum=y;
        if(sum>max)
        max=sum;
    }
    printf("%d",max);
    return 0;
}

题解：蚂蚁相撞从计算机的视角来看待这个问题就当成一个他们擦肩而过对最终的结果毫无影响，反正我们考虑的是最晚掉下去的蚂蚁而不在乎是那只蚂蚁。最后掉下去，所以很显然的，计算那只蚂蚁离两端最远就行了。

I: 小学数学题

题目描述：

求这个数 答案可能很大 因此输出这个数对 1e9+7 取余； （10^9+7）

1<N<10^5

输入

第一行一个 t 代表测试组数
下面 t 行 每行有一个数 N 意义如题

输出

输出有 t 行
每行输出一个答案

样例输入

2
2
5

样例输出

11
120

提示

• 取余的加法运算律（a+b）%m=（a%m+b%m）%m

• 取余的乘法运算律 (a*b) % m = 【(a%m) * (b%m)】 % m

• 计算机每秒进行 10^7 次运算

• int 类型可以存的最大整数为 2^32-1;

• long long 类型可以存的最大整数为 2^64 -1;

参考程序

#include<cstdio>
using namespace std;
long long now,ans,p=1e9+7;
int t,n;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        ans=0;now=1;
        for(int i=0;i<=n;i++){
            ans+=now*(n+1-i)%p;
            ans%=p;
            now=(now*2)%p;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

题解：根据提示编写程序。

J: 超简单的 A+B

题目描述：

求两个不超过 200 位的非负整数的和。

输入

有两行，每行是一个不超过 200 位的非负整数，可能有多余的前导 0。

输出

一行，即相加后的结果。结果里不能有多余的前导 0，即如果结果是 342，那么就不能输出为 0342。

样例输入

22222222222222222222
33333333333333333333

样例输出

55555555555555555555

参考程序

#include<stdio.h>
#include<string.h>
char s[10100],ss[10100];
int a[10100],b[10100];
int len;

void jia()     //自定义函数"jia"(名字low了一点（好像不是一点，但容易理解不是吗）)
{
    int l1 = strlen(s);     //"strlen"是一个计算字符串长度的函数
    int l2 = strlen(ss);    //将输入的两个字符串的长度赋值给l1,l2
    if (l1 > l2)
        len = l1;      //将len赋值为l1,l2中大的那个
    else
        len = l2;
//      for (int i = 0 ; i <= len ; i++)  //清零（这里for循环和下面三句memset都为将字符串清零 ）
//          a[i] = b[i] = c[i] = 0;
    memset(a,0,sizeof(a));    //清零too(只能清零，不能干别的)
    memset(b,0,sizeof(b));    //这是清零函数（字符串）
                                        //两个for循环是将输入的两个字符串倒过来
    for (int i = l1 - 1 ; i >= 0 ; i--)    //再将字符串里的字符转换为数字赋值给a,b整型数组
        a[l1 - i - 1] = s[i] - '0';        //但为什么大数要用字符串存呢？
    for (int i = l2 - 1 ; i >= 0 ; i--)    //因为大数太大，用任何整型变量都存不下
        b[l2 - i - 1] = ss[i] - '0';       //为什么要把字符串倒过来赋值呢？
                                    //因为大数与大数是一位一位运算的，还要涉及进位等
    for (int i = 0 ; i < len ; i++)
    {
        a[i] = a[i] + b[i];    //运算
        a[i+1]+= a[i] / 10;    //如有进位，在后一位上加上
        a[i] = a[i] % 10;      //原来那一位减掉进位了的
    }
    if (a[len] != 0) len++;    //如果有进位就多显示一位（这句话很重要）

    while (a[len - 1] == 0 && len>1) len--;      //我叫它while去零法

    for (int i = len - 1 ;i >= 0 ;i--)  //输出结果
        printf("%d",a[i]);
}

int main()
{
scanf("%s%s",s,ss);
jia();
    return 0;
}

题解：高精度计算基本内容请掌握。