2024第四次随堂测验参考答案

从第四次开始答案会以c++语言提供，自行了解，学习

6-1 报数

报数游戏是这样的：有n个人围成一圈，按顺序从1到n编好号。从第一个人开始报数，报到m（<n）的人退出圈子；下一个人从1开始报数，报到m的人退出圈子。如此下去，直到留下最后一个人。

本题要求编写函数，给出每个人的退出顺序编号。

函数接口定义：

void CountOff( int n, int m, int out[] );

其中n是初始人数；m是游戏规定的退出位次（保证为小于n的正整数）。函数CountOff将每个人的退出顺序编号存在数组out[]中。因为C语言数组下标是从0开始的，所以第i个位置上的人是第out[i-1]个退出的。

裁判测试程序样例：

#include <stdio.h>

#define MAXN 20

void CountOff( int n, int m, int out[] );

int main() {

int out[MAXN], n, m;

int i;

scanf("%d %d", &n, &m);

CountOff( n, m, out );

for ( i = 0; i < n; i++ )

printf("%d ", out[i]);

printf("\n");

return 0;

}

/* 你的代码将被嵌在这里 */

输入样例：

11 3

输出样例：

4 10 1 7 5 2 11 9 3 6 8

参考答案：

void CountOff( int n, int m, int out[] ) {
    int cnt = 1;
    int residual = n;
    int flag[999] = {0};
    int num = 0;
    while(residual > 0) {
        for (int i = 0; i < n; i++) {
            if (flag[i] == 0) {
                num++;
                if (num == m) {
                    out[i] = cnt;
                    cnt++;
                    num = 0;
                    residual--;
                    flag[i] = 1;
                }
            }else if (flag[i] == 1) {
                continue;
            }
        }
    }
}

6-2 走台阶方法

本题要求实现一个函数，可计算对于n阶台阶共有多少种走法。

台阶的走法只可以根据下面三种方式走：

（1）一次走1阶；

（2）一次走2阶；

（3）一次走3阶。

函数接口定义：

int step(int n);

其中 n 表示台阶数。函数返回多少种走法。

裁判测试程序样例：

#include <stdio.h>

int step(int n);

int main() {

int n,k;

scanf("%d",&n);

k=step(n);

printf("%d",k);

return 0;

}

/* 请在这里填写答案 */

输入样例：

输出样例：

参考答案：

int step(int n){
    if(n < 0){
        return 0;
    }
    else if(n == 0){
        return 1;
    }
    return step(n - 1) + step(n - 2) + step(n - 3);
}

7-1 查找整数

本题要求从输入的N个整数中查找给定的X。如果找到，输出X的位置（从0开始数）；如果没有找到，输出“Not Found”。

输入格式：

输入在第一行中给出两个正整数N（≤20）和X，第二行给出N个整数。数字均不超过长整型，其间以空格分隔。

输出格式：

在一行中输出X的位置，或者“Not Found”。

输入样例1：

5 7
3 5 7 1 9

输出样例1：

输入样例2：

5 7
3 5 8 1 9

输出样例2：

Not Found

参考答案：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, num;
    cin >> n >> num;
    int arr[30];
    for (int i = 0; i < n; i++) {cin >> arr[i];}
    int flag = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] == num) {
            cout << i;
            flag = 1;
            break;
        }
    }
    if (flag == 0) cout << "Not Found";
    return 0;
}

7-2 输出数组元素

本题要求编写程序，对顺序读入的n个整数，顺次计算后项减前项之差，并按每行三个元素的格式输出结果。

输入格式：

输入的第一行给出正整数n（1<n≤10）。随后一行给出n个整数，其间以空格分隔。

输出格式：

顺次计算后项减前项之差，并按每行三个元素的格式输出结果。数字间空一格，行末不得有多余空格。

输入样例：

10
5 1 7 14 6 36 4 28 50 100

输出样例：

-4 6 7
-8 30 -32
24 22 50

参考答案：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    int arr[20];
    for (int i = 0; i < n; i++) {cin >> arr[i];}
    int ans[20];
    for (int i = 0; i < n-1; i++) {
        ans[i] = arr[i+1] - arr[i];
    }
    for (int i = 0; i < n-1; i++) {
        if ((i+1)%3 == 0 || i == n-2) {
            cout << ans[i] << endl;
        }else {
            cout << ans[i] << " ";
        }
    }
    return 0;
}

7-3 求整数序列中出现次数最多的数

本题要求统计一个整型序列中出现次数最多的整数及其出现次数。

输入格式：

输入在一行中给出序列中整数个数N（0<N≤1000），以及N个整数。数字间以空格分隔。

输出格式：

在一行中输出出现次数最多的整数及其出现次数，数字间以空格分隔。题目保证这样的数字是唯一的。

输入样例：

10 3 2 -1 5 3 4 3 0 3 2

输出样例：

3 4

参考答案：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    int a[1010];
    for(int i = 0; i <= n; i++){
        cin >> a[i];
    }
    int ans_num = -1;
    int ans_cnt = -1;
    for(int i = 0; i <= n; i++)
    {
        int cnt = 1;
        for(int j = 0; j < i; j++)
        {
            if(a[i] == a[j])
            cnt++;
        }
        if(cnt > ans_cnt)
        {
            ans_cnt = cnt;
            ans_num = a[i];
        }
        
    }
    cout << ans_num << " " << ans_cnt;
    return 0;
}

7-4 猜帽子游戏

宝宝们在一起玩一个猜帽子游戏。每人头上被扣了一顶帽子，有的是黑色的，有的是黄色的。每个人可以看到别人头上的帽子，但是看不到自己的。游戏开始后，每个人可以猜自己头上的帽子是什么颜色，或者可以弃权不猜。如果没有一个人猜错、并且至少有一个人猜对了，那么所有的宝宝共同获得一个大奖。如果所有人都不猜，或者只要有一个人猜错了，所有宝宝就都没有奖。
下面顺序给出一排帽子的颜色，假设每一群宝宝来玩的时候，都是按照这个顺序发帽子的。然后给出每一群宝宝们猜的结果，请你判断他们能不能得大奖。

输入格式：

输入首先在一行中给出一个正整数 N（2<N≤100），是帽子的个数。第二行给出 N 顶帽子的颜色，数字 1 表示黑色，2 表示黄色。
再下面给出一个正整数 K（≤10），随后 K 行，每行给出一群宝宝们猜的结果，除了仍然用数字 1 表示黑色、2 表示黄色之外，0 表示这个宝宝弃权不猜。
同一行中的数字用空格分隔。

输出格式：

对于每一群玩游戏的宝宝，如果他们能获得大奖，就在一行中输出 Da Jiang!!!，否则输出 Ai Ya。

输入样例：

输出样例：

Da Jiang!!!
Ai Ya
Ai Ya

参考答案：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    int true_ans[110];
    for (int i = 0; i < n; i++) {
        cin >> true_ans[i];
    }
    int k;
    cin >> k;
    while(k--) {
        int true_cnt = 0;
        int false_cnt = 0;
        int abstain = 0;
        for (int i = 0; i < n; i++){
            int choice;
            cin >> choice;
            if (choice == 0) {abstain++;}
            else {
                if (choice == true_ans[i]) true_cnt++;
                else false_cnt++;
            }
        }
        if (false_cnt == 0 && true_cnt >= 1) cout << "Da Jiang!!!" << endl;
        else cout << "Ai Ya" << endl;
    }
    return 0;
}

7-5 出生年

以上是新浪微博中一奇葩贴：“我出生于1988年，直到25岁才遇到4个数字都不相同的年份。”也就是说，直到2013年才达到“4个数字都不相同”的要求。本题请你根据要求，自动填充“我出生于y年，直到x岁才遇到n个数字都不相同的年份”这句话。

输入格式：

输入在一行中给出出生年份y和目标年份中不同数字的个数n，其中y在[1, 3000]之间，n可以是2、或3、或4。注意不足4位的年份要在前面补零，例如公元1年被认为是0001年，有2个不同的数字0和1。

输出格式：

根据输入，输出x和能达到要求的年份。数字间以1个空格分隔，行首尾不得有多余空格。年份要按4位输出。注意：所谓“n个数字都不相同”是指不同的数字正好是n个。如“2013”被视为满足“4位数字都不同”的条件，但不被视为满足2位或3位数字不同的条件。

输入样例1：

1988 4

输出样例1：

25 2013

输入样例2：

1 2

输出样例2：

0 0001

参考答案：

#include<bits/stdc++.h>
using namespace std;
bool isStf(int year, int n){
    int a = year%10;
    int b = year/10%10;
    int c = year/100%10;
    int d = year/1000;
    int cnt = 1; 
    if (b != a) cnt++;
    if (c != a && c != b) cnt++;
    if (d != a && d != b && d != c) cnt++;
    if (cnt == n) return true;
    else return false;
}
int main(){
    int year, n;
    cin >> year >> n;
    for(int i = year; ; i++) {
        if (isStf(i, n) == true) {
            printf("%d %04d", i-year, i);
            break;
        }
    }
    return 0;
}

7-6 试试手气

我们知道一个骰子有 6 个面，分别刻了 1 到 6 个点。下面给你 6 个骰子的初始状态，即它们朝上一面的点数，让你一把抓起摇出另一套结果。假设你摇骰子的手段特别精妙，每次摇出的结果都满足以下两个条件：

1、每个骰子摇出的点数都跟它之前任何一次出现的点数不同；
2、在满足条件 1 的前提下，每次都能让每个骰子得到可能得到的最大点数。

那么你应该可以预知自己第 n 次（1≤n≤5）摇出的结果。

输入格式：

输入第一行给出 6 个骰子的初始点数，即 [1,6] 之间的整数，数字间以空格分隔；第二行给出摇的次数 n（1≤n≤5）。

输出格式：

在一行中顺序列出第 n 次摇出的每个骰子的点数。数字间必须以 1 个空格分隔，行首位不得有多余空格。

输入样例：

3 6 5 4 1 4
3

输出样例：

4 3 3 3 4 3

样例解释：

这 3 次摇出的结果依次为：

6 5 6 6 6 6
5 4 4 5 5 5
4 3 3 3 4 3

参考答案：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int flag[10][10] = {0};
    for (int i = 1; i <= 6; i++) {
        int num_init;
        cin >> num_init;
        flag[i][num_init] = 1;
    }
    int n;
    cin >> n;
    int ans[10];
    for (int i = 1; i <= 6; i++) {
        int k = n;
        for (int j = 6; ; j--) {
            if (flag[i][j] == 0) {
                k--;
            }else {
                continue;
            }
            if (k == 0) {
                ans[i] = j;
                break;
            }
        }
    }
    for (int i = 1; i <= 6; i++) {
        if (i != 1) printf(" ");
        cout << ans[i];
    }
    return 0;
}

7-7 金铲铲之战#4

在金铲铲之战中存在各种各样的银色、金色、彩色海克斯科技强化。

在每一局游戏的第二、第三、第四三个回合中总共可以获得三个海克斯科技强化。而广大棋手们认为，当第二回合与第三回合的海克斯科技强化品质为金色和彩色时，第四个回合的海克斯科技强化大概率为银色。如果我们把海克斯科技强化的级别转换为字符。（银色-A，金色-B，彩色-C）

我们将会给出两行输入，在第一行中输入多个字符代表获得的海克斯科技强化（题目保证，输入的字符皆为A、B、C，且至少有两个，并且不会超过30个）。

第二行中输入三个字符，此为海克斯科技强化的匹配规则。如：金彩银的对应规则为BCA。(BC的匹配结果为A)

我们的要求是，查看第一行输入的字符是否存在第二行的对应规则，每有一对字符匹配成功，就输出一次匹配结果。如果一次成功匹配都没有，则输出None。

输入格式:

输入两行字符串：

第一行输入多个字符（题目保证，输入的字符皆为A、B、C，且至少有两个）。
第二行中输入三个字符。

输出格式:

在一行中输出匹配结果。

输入样例:

在这里给出一组输入。例如：

ABCBBACABC
BCA

输出样例:

在这里给出相应的输出。例如：

AA

参考答案：

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin >> s;
    char a, b, c;
    cin >> a >> b >> c;
    int cnt = 0;
    for (int i = 0; i < s.size()-1; i++) {
        if (s[i] == a && s[i+1] == b) cnt++;
    }
    if (cnt == 0) {
        cout << "None";
    }else {
        for (int i = 1; i <= cnt; i++) {
            cout << c;
        }
    }
    return 0;
}

7-8 字符串替换

本题要求编写程序，将给定字符串中的大写英文字母按以下对应规则替换：

原字母	对应字母
A	Z
B	Y
C	X
D	W
…	…
X	C
Y	B
Z	A

输入格式：

输入在一行中给出一个不超过80个字符、并以回车结束的字符串。

输出格式：

输出在一行中给出替换完成后的字符串。

输入样例：

Only the 11 CAPItaL LeTtERS are replaced.

输出样例：

Lnly the 11 XZKRtaO OeGtVIH are replaced.

参考答案：

#include<bits/stdc++.h>
using namespace std;
char letter[] = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
map <char, char> mp;
int main(){
    for (int i = 0; i < 26; i++) {
        mp[letter[i]] = letter[25-i];
    }
    string s;
    getline(cin, s);
    for(int i = 0; i < s.size(); i++) {
        if (s[i] >= 'A' && s[i] <= 'Z') {
            s[i] = mp[s[i]];
        }
    }
    cout << s;
    return 0;
}

7-9 金铲铲之战#5

在金铲铲之战中，有一件辅助装备的名字叫兰顿之兆，其效果是提供30护甲和30魔抗给携带者和邻格的友军们。

0

0X0

0

其装备效果如上图所示，假设X为兰顿之兆携带者，那么其上下左右四个邻近的友军与自己都可以获得属性加成。

附加规则1：当棋子处于奇数个兰顿之兆的增益范围内时，将会获得增益；但处于偶数个兰顿之兆的增益范围内时，将不会获得增益。

附加规则2：游戏共计进行K个回合，每个回合将会给一个位子的棋子装备兰顿之兆。如果该位子无棋子，那么本轮的兰顿之兆将不产生任何效果。

假设，我们首先在一行中输入两个值M、N，将棋盘模拟为一个M×N的二维平面（M、N为不超过20的正整数）；

随后给出整个棋盘的棋子排列情况，其中0表示该位子无棋子，#表示该位子存在棋子；

再在接下来一行中给出一个K值，表示游戏回合数；

接下来k行，每行给出一个x、y坐标，表示该位置将会获得一个兰顿之兆（如果该位子无棋子，那么本轮的兰顿之兆将不产生任何效果）。

最后给出k行输出，每一行输出一个回合中获得兰顿之兆增益效果的棋子数。

输入格式:

在第一行中给出两个值M、N，中间用空格隔开；

接下来几行给出整个棋盘的棋子排列情况，其中0表示该位子无棋子，#表示该位子存在棋子；

再在接下来一行中给出一个K值，表示游戏回合数；

接下来k行，每行给出一个x、y坐标。

输出格式:

总共给出k行输出，第i行表示第i个回合中，获得兰顿之兆增益效果的棋子数。

输入样例:

在这里给出一组输入。例如：

输出样例:

在这里给出相应的输出。例如：

参考答案：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int m,n;
    cin >> m >> n;
    char a[m][n];
    int b[m+2][n+2];
    int flag[m+2][n+2];
    for(int i=0;i<m+2;i++){
        for(int j=0;j<n+2;j++){
            b[i][j] = -1;
            flag[i][j] = 0;
        }
    }
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            //a[i][j] = 0;
            cin >> a[i][j];
            if(a[i][j] == '#'){
                b[i+1][j+1] = 0;
            }
        }
    }
    int k, x, y, cnt;
    cin >> k;
    while(k--){
        cnt = 0;
        cin >> x >> y;
        if(a[x][y] == '#'){
            if(b[x+1][y+1] == 0) b[x+1][y+1]++;
            else b[x+1][y+1]--;
            
            if(b[x+1][y] == 0) b[x+1][y]++;
            else b[x+1][y]--;
            
            if(b[x+1][y+2] == 0) b[x+1][y+2]++;
            else b[x+1][y+2]--;
            
            if(b[x][y+1] == 0) b[x][y+1]++;
            else b[x][y+1]--;
            
            if(b[x+2][y+1] == 0) b[x+2][y+1]++;
            else b[x+2][y+1]--;
        }
        for(int i=0;i<m+2;i++){
            for(int j=0;j<n+2;j++){
                if(b[i][j] > 0 && flag[i][j] == 0){
                    cnt++;
                    flag[i][j] = 1;
                }
                if(b[i][j] == 0 && flag[i][j] == 1){
                    flag[i][j] = 0;
                }
            }
        }
        cout << cnt << endl;
    }
    return 0;
}

7-10 最长对称子串

对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定Is PAT&TAP symmetric?，最长对称子串为s PAT&TAP s，于是你应该输出11。

输入格式：

输入在一行中给出长度不超过1000的非空字符串。

输出格式：

在一行中输出最长对称子串的长度。

输入样例：

Is PAT&TAP symmetric?

输出样例：

参考答案：

#include<bits/stdc++.h>
using namespace std;
bool isStf(string x) {
    for (int i = 0, j = x.size()-1; i < j; i++, j--) {
        if (x[i] != x[j]) return false;
    }
    return true;
}
int main(){
    string s;
    getline(cin, s);
    int ans = -1;
    for (int i = 0; i < s.size(); i++) {
        for (int j = 1; j <= s.size()-i; j++) {
            string temp = s.substr(i, j);
            int len = temp.size();
            if (isStf(temp) && len > ans) {
                ans = len;
            }
        }
    }
    cout << ans;
    return 0;
}

7-11 IP地址转换

一个IP地址是用四个字节（每个字节8个位）的二进制码组成。请将32位二进制码表示的IP地址转换为十进制格式表示的IP地址输出。

输入格式：

输入在一行中给出32位二进制字符串。

输出格式：

在一行中输出十进制格式的IP地址，其由4个十进制数组成（分别对应4个8位的二进制数），中间用“.”分隔开。

输入样例：

11001100100101000001010101110010

输出样例：

204.148.21.114

参考答案：

#include<bits/stdc++.h>
using namespace std;
int btd(int x) {
    int ans = 0;
    for (int i = 0; i <= 7; i++) {
        ans += (x%10)*pow(2, i);
        x /= 10;
    }
    return ans;
}
int main(){
    string s;
    getline(cin, s);
    int a = stoi(s.substr(0,8));
    int b = stoi(s.substr(8,8));
    int c = stoi(s.substr(16,8));
    int d = stoi(s.substr(24,8));
    cout << btd(a) << "." << btd(b) << "." << btd(c) << "." << btd(d);
    return 0;
}