第三届“计协杯”程序设计大赛暨ACM实验室招新选拔4月赛题解
ACMore Team Lv1
  2023-04-20 05:27:34 2023-04-20 05:27

第三届“计协杯”程序设计大赛暨ACM实验室招新选拔4月赛

“计协杯”是由湖南工程学院计算机协会举办的程序设计竞赛，旨在提高同学们激发学生学习计算机领域专业知识与技能的兴趣，鼓励主动灵活地运用计算机知识和技能解决实际问题，有效提升算法设计、逻辑推理、数学建模、编程实现和计算机系统能力，培养团队合作意识、挑战精神和创新能力。

A：

题目描述

由于jk不喜欢说话，jk会将字符串变得更加简单再去读：将连续的几个相同字母读成：（字母 + 字母出现次数）的形式。

例如，连续的 5 个 f，即 fffff，jk会将其读成 f5（也可能读成 f4f、ff3f 等）。

对于这个例子：AAAACCCMMMMM，jk可将其读成 A4C3M5。

为了方便表达，jk不会将连续的超过 9个相同的字符读成简写的形式。

现在给出jk读出的句子，请将其还原

输入格式

输入一行包含一个字符串。

输出格式

输出一个字符串，表示还原后的串

签到题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<stdio.h>
#include<string.h>
#include<ctype.h>
int main()
{
	char s[1000];
	scanf("%s",s);
	for(int i=0;s[i];i++){
		if(isdigit(s[i])){//是数字就输出s[i]-1次s[i-1] 
			for(int j=1;j<s[i]-'0';j++){
				printf("%c",s[i-1]);
			}
		}
		else printf("%c",s[i]);//不是数字就输出字符s[i] 
	}
    return 0;
}

B：

题目描述

这天放假cd和xch打游戏时碰到了翻斗花园第一突破手，翻斗花园第一突破手在n局内对cd造成a1,a2,……ai(1<=i<=n)的伤害,对xch造成了
b1,b2,……bi(1<=i<=n)的伤害，求翻斗花园突破手对cd造成伤害是素数的值和对xch造成伤害是偶数的值之和

输入格式

第一行输入n，接下来两行分别输入n个数据

输出格式

输出伤害和

直接暴力就好了 判断一下是偶数或者素数就加到ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<stdio.h>
typedef long long ll;
int isprime(int x) { //判断素数
	if(x==1||x==0) return 0;
	for(int i=2; i<=x/i; i++) if(x%i==0) return 0 ;
	return 1;
}
int main() {
	ll n,t,ans=0;
	scanf("%d",&n);
	for(int i=0; i<n; i++) {
		scanf("%d",&t);
		if(isprime(t)) ans+=t;
	}
	for(int i=0; i<n; i++) {
		scanf("%d",&t);
		if(!(t&1)) ans+=t;//t&1==1则t为奇数
	}
	printf("%lld",ans);
}

C：

题目描述

lmt最近大创项目研究的协同过滤算法能将喜欢相同物品的人匹配到一起，

现有n个人和10000件商品，分别将这10000件商品编号为1,2,3,……10000，

给出每个人喜欢的商品的编号，请你求出哪一件商品最受这n个人喜欢（如果有多件商品都最受人喜欢，输出编号最小的那个）。

输入格式

第一行输入n
第二行输入n个数，表示n个人分别喜欢商品的编号

输出格式

输出最受喜欢的商品的编号

打表记录每个编号有多少人喜欢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<stdio.h>
int main() {
	int n,arr[10010]={0}; //a拿来记录次数
	scanf("%d",&n);
	for(int i=0; i<n; i++) {
		int t;
		scanf("%d",&t);
		arr[t]++;
	}
	int ma=0,idx=0;//找最大值 idx为下标
	for(int i=1; i<=10000; i++) {
		if(arr[i]>ma) {
			ma=arr[i],idx=i;
		}
	}
	printf("%d",idx);
	return 0;
}

D：

题目描述

jl学长每天下午有空就会去操场健身，

他每天一共做n组运动项目。

其中，ai表示第i组运动项目的时长。

jl学长会循环做三种运动项目：深蹲（squat）、跑步（running）、波比跳（burpee）。

也就是说他第一组训练是深蹲项目，第二组训练是跑步项目，第三组训练是波比跳项目，第四组训练是深蹲项目，第五组训练是跑步项目……以此类推
直到做完第 n 组训练项目。

请你计算，运动的时长最长的运动项目。

输入格式

第一行包含整数 n。
第二行包含 n 个整数 a1，a2，……，an。

输出格式

共一行，如果训练时长最长的运动为：
深蹲项目，则输出 squat。
跑步项目，则输出 running。
波比跳项目，则输出 burpee。
数据保证训练时长最长的运动是唯一的。

1
2
3
4
5
6
7
8
9
输入的时候直接统计，最后对三个数据进行排序即可。

列举各个运动的规律（这里列举的是 i 的值）：

三个数据一组（这是很显然的）

深蹲项目： 0，3，6，9，…0，3，6，9，… 规律：(i + 1) % 3 == 1
跑步项目：1，4，7，10，…1，4，7，10，… 规律：(i + 1) % 3 == 2
波比跳项目：2，5，8，11，…2，5，8，11，… 规律：(i + 1) % 3 == 0

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>

int i,t,n,max,a[3];

int main()
{
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&t);
		if(i%3==0) a[0]+=t;//a[0]用来存放深蹲项目总时长 
		if(i%3==1) a[1]+=t;//a[1]用来存放跑步项目总时长 
		if(i%3==2) a[2]+=t;//a[2]用来存放波比跳项目总时长 
	}
	for(i=0;i<3;i++)
		if(a[i]>max) //找出最长的时长 
		{
			max=a[i];
			t=i;//保存最长时长的下标 
		}
	if(t==0) puts("squat");
	if(t==1) puts("running");
	if(t==2) puts("burpee");
}

E：

题目描述

sjq和xw在玩扑克牌，她们有三张扑克牌，选择了一张扑克牌并做上了标记。

然后进行 n 次操作，操作数编号为 1∼n。

设某一次的操作数为 i ：

（1）当 i mod 2 = 1 时，sjq会将中间的扑克牌与左边的扑克牌交换位置。

（2）当 i mod 2 = 0 时，xw会将中间的扑克牌与右边的扑克牌交换位置。

分别用0、1、2来表示左，中，右三个位置。

n 次操作全部完成以后，被标记的扑克牌位于位置 x。

请你计算，所有操作开始前，被标记的扑克牌所在的初始位置。

输入格式

第一行，一个整数 n。
第二行，一个整数 x。

输出格式

输出一个 0∼2 的整数，表示所有操作开始前，被标记的扑克牌所在的初始位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<stdio.h>

int n,x;
int a[6][3]=//每个周期中的六次操作 
{
  {1,2,3},
  {2,1,3},
  {2,3,1},
  {3,2,1},
  {3,1,2},
  {1,3,2},
};
int main()
{
    scanf("%d%d",&n,&x);
    n=n%6;//每六次操作为一个周期 
    int k=a[n][x];//n次操作后位于x位置的扑克牌大小
    for(int i=0;i<3;i++)
    {
        if(a[0][i]==k)//找到首次操作的初始位置 
			printf("%d",i);
    }
    return 0;
}

F：

题目描述

桌上放着排成一排的若干硬币，我们用 表示反面，用
小写的 o 表示正面

比如，可能情形是：oooooo

如果同时翻转左边的两个硬币，则变为：oooo*oooo

我们约定：把翻动相邻的两个硬币叫做一步操作

现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？

输入格式

两行等长的字符串，分别表示初始状态和要达到的目标状态。每行的长度<1000

输出格式

一个整数，表示最小操作步数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>

const int N=110;

int main()
{
    char s1[N], s2[N];//s1：初始状态，s2：最终状态 
    int i,cnt = 0;//记录翻转次数 
   	scanf("%s\n%s",s1,s2);
    for (i=0;s1[i]; i++)
    {
        if (s1[i] != s2[i])//若第i个位置上的硬币不同，就翻转此硬币和它后面的那个 
        {
            cnt++;//翻转一次硬币 
            if (s1[i] == '*') s1[i] = 'o';//翻转 i 位置上的硬币 
            else s1[i] = '*';
            
            if (s1[i+1] == 'o') s1[i+1] = '*';//翻转 i+1 位置上的硬币 
            else s1[i+1] = 'o';
        }
    }
    printf("%d",cnt);
}

G：

题目描述

小红打算从下周一开始努力刷题准备今年的一系列比赛
他计划周一到周五每天做 a 道题目，周六和周日每天做 b 道题目。
请你帮小红计算，按照计划他将在第几天实现做题数大于或者等于 n 题？

输入格式

输入一行包含三个整数 a,b 和 n

输出格式

输出一个整数代表天数

对于 100% 的评测用例，1≤a,b,n≤10^18

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<stdio.h>
typedef long long ll;
int main() {
	ll a,b,c,s=0,index=0;
	scanf("%lld%lld%lld",&a,&b,&c);
	index+=(c/((ll)5*a+(ll)2*b))*(ll)7;
	//index先按星期为周期处理 
	c%=((ll)5*a+(ll)2*b);
	//c为剩下的最后一个星期还有多少题没做 
	while(s<c) {
		if(index%7<5) s+=a;
		else s+=b;
		index++;
	}

	printf("%lld",index);
}

H：

题目描述

ttf和yjm准备玩一个进制的小游戏，ttf会给定一个十进制整数n ，yjm会给出一个小整数 x。
请你将整数 n 转为 x 进制，对于超过十进制的数码，用 A，B … 表示。

输入格式

第一行n，第二行x。

输出格式

输出仅一个数，表示答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
using namespace std;

string R = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int n, x;

void fun(int n) {
	if (n / x == 0) {
		cout << n;
		return;
	}
	fun(n / x);
	cout << R[n % x];
}

int main() {
	cin >> n >> x;
	fun(n);
}

I：

题目描述

湖南工程学院有两棵树，一棵是大树，另一棵也是大树。鲁迅：我没说过这话。鲁迅先生的确没说过这话，但学校里有很多树是真的。现在给你一张绿化示意图，假如每棵树算作一片森林的话，问你校园里有多少片森林，如果每棵树的旁边（上下左右四个位置）如果还是树的话，算作同一片森林。
问给定的示意图上有多少片森林。

输入格式

每个测试数据文件只有一组数据。
第一行该地图的行数m(0<m<100)与列数n(0<n<100)，然后，输入接下来的m行每行输入n个数，表示此处有树还是没树（1表示此处有树，0表示此处没树）

输出格式

输出该地图中森林的个数。
要注意，每棵树的旁边（上下左右四个位置）如果还是树的话，它们可以看做是同一片森林。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
using namespace std;

const int N = 110;
int a[N][N], n, m, ans;

void dfs(int x, int y) {
	a[x][y] = 0;
	if (a[x - 1][y]) dfs(x - 1, y);
	if (a[x + 1][y]) dfs(x + 1, y);
	if (a[x][y - 1]) dfs(x, y - 1);
	if (a[x][y + 1]) dfs(x, y + 1);
}

int main() {
	cin >> n >> m;
	for (int i = 1;i <= n;i++) for (int j = 1;j <= m;j++) cin >> a[i][j];
	for (int i = 1;i <= n;i++) for (int j = 1;j <= m;j++) if (a[i][j] == 1) ans++, dfs(i, j);
	cout << ans;
}

J：

题目描述

数字三角形，从三角形顶部往下走，只能往左下或右下走，求走到最下面时所经过的数字和最大为多少？

输入格式

第1行：整数n(1<=n<=1000)
第2-n+1行：每行若干整数，第i行有i-1个整数，空格分隔。

输出格式

一行：一个整数，表示所经过数字的最大和。

1
2
3
4
5
6
7
8
9
10
11
12
#include<iostream>
using namespace std;

const int N = 1010;
int a[N][N], n;

int main() {
	cin >> n;
	for (int i = 1;i <= n;i++) for (int j = 1;j <= i;j++) cin >> a[i][j];
	for (int i = n;i >= 1;i--) for (int j = 1;j <= i;j++) a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]);
	cout << a[1][1];
}