2022第十三届蓝桥杯第一场,b组c/c++题目和个人理解

本次比赛是2道填空题和8道编程题,跟以往不同.这些答案并不一定完全正确啊，大家可以相互讨论讨论，仅仅发表个人意见啦，各位少侠手下留情

目录

第一题:

第二题:

第三题:

第四题:

第五题:

第六题:

第七题:

第八题:

第九题:

第十题:

第一题:

试题 A: 九进制转十进制

本题总分： 5 分

【问题描述】

九进制正整数 (2022) 9 转换成十进制等于多少？

#include
int main()
{
	int sum=0,n=0,m=2022,k=1;
	while(m>0)
	{
		n=m%10;
		m=m/10;
		sum+=n*k;
		k=k*9;
	}
	printf(\"%d\",sum);
	return 0;
}

最后输出也就是1478

第二题:

试题 B: 顺子日期

本题总分： 5 分

【问题描述】

小明特别喜欢顺子。顺子指的就是连续的三个数字： 123 、 456 等。顺子日

期指的就是在日期的 yyyymmdd 表示法中，存在任意连续的三位数是一个顺

子的日期。例如 20220123 就是一个顺子日期，因为它出现了一个顺子： 123 ；

而 20221023 则不是一个顺子日期，它一个顺子也没有。小明想知道在整个 2022

年份中，一共有多少个顺子日期。

 这个题大家争议很大，因为不知道012算不算是顺子，如果算是顺子的话答案就是14，如果不算顺子就是4，这直接手算就好了，没必要编程了。

第三题:

试题 C: 刷题统计

时间限制 : 1.0s

内存限制 : 256.0MB

本题总分： 10 分

【问题描述】

小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天

做 a 道题目，周六和周日每天做 b 道题目。请你帮小明计算，按照计划他将在

第几天实现做题数大于等于 n 题？

【输入格式】

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

【输出格式】

输出一个整数代表天数。

【样例输入】

10 20 99

【样例输出】

8

【评测用例规模与约定】

对于 50 % 的评测用例， 1 ≤ a , b , n ≤ 1e 6 .

对于 100 % 的评测用例， 1 ≤ a , b , n ≤ 1e18   .

 这是编程第一道题，也不难其实，就是一个入门题大家只需要把题认真看下，还有就是整形类型开大一点就好了，因为它后面都到了1e18，所以开longlong吧

#include
int main()
{
	long long int a,b,n,sum=0;
	scanf(\"%lld%lld%lld\",&a,&b,&n);
	long long int flag=n/(a*5+b*2);
	n-=(a*5+b*2)*flag;
	sum+=flag*7;
	if(n/a<=5)
	{
		sum+=n/a;
		if(n%a>0)
		{
			sum++;
		}
	}else{
		sum+=5+(n-5*a)/b;
		if((n-5*a)%b>0)
		{
			sum++;
		}
	}
	printf(\"%lld\",sum);
	return 0;
}

第四题:

试题 D: 修剪灌木

时间限制 : 1.0s

内存限制 : 256.0MB

本题总分： 10 分

【问题描述】

爱丽丝要完成一项修剪灌木的工作。

有 N 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晚会修剪一棵灌

木，让灌木的高度变为 0 厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始，

每天向右修剪一棵灌木。当修剪了最右侧的灌木后，她会调转方向，下一天开

始向左修剪灌木。直到修剪了最左的灌木后再次调转方向。然后如此循环往复。

灌木每天从早上到傍晚会长高 1 厘米，而其余时间不会长高。在第一天的

早晨，所有灌木的高度都是 0 厘米。爱丽丝想知道每棵灌木最高长到多高。

【输入格式】

一个正整数 N ，含义如题面所述。

【输出格式】

输出 N 行，每行一个整数，第行表示从左到右第 i 棵树最高能长到多高。

【样例输入】

3

【样例输出】

4

2

4

【评测用例规模与约定】

对于 30 % 的数据， N ≤ 10 .

对于 100 % 的数据， 1 < N ≤ 10000 .

这个题其实你把题读懂了就很简单了，其实就是找规律就好了，前半段的树和后半段的树最大长度肯定是一样的，然后你把这些树分一下，如果n是偶数是一种情况，n是奇数是另一种情况，如果你直接暴力的话需要2的n次方次才可以求出所有位置的最大解，这显然是不行的，那么你想一下，每个位置的最大解其实就是第一次剪完了后，第二次剪之前，这个时间段，自己画个图就明白了。

#include
#include
#define max 10005
int arr[max];
int main()
{
	int n,i,j;
	scanf(\"%d\",&n);
	for(i=1; i<=n/2; i++)
	{
		arr[i]=2*(n-i);
	}
	if(n&1)
	{
		arr[(n+1)>>1]=n-1;
	}
	for(i=1; i<=n/2; i++)
	{
		printf(\"%d\\n\",arr[i]);
	}
	if(n&1)
	{
		printf(\"%d\\n\",arr[(n+1)>>1]);
	}
	for(j=n/2;j>=1;j--)
	{
		printf(\"%d\\n\",arr[j]);
	}
	return 0;
}

第五题:

试题 E: X 进制减法

时间限制 : 1.0s

内存限制 : 256.0MB

本题总分： 15 分

【问题描述】

进制规定了数字在数位上逢几进一。

X 进制是一种很神奇的进制，因为其每一数位的进制并不固定！例如说某

种 X 进制数，最低数位为二进制，第二数位为十进制，第三数位为八进制，则

X 进制数 321 转换为十进制数为 65 。

现在有两个 X 进制表示的整数 A 和 B ，但是其具体每一数位的进制还不确

定，只知道 A 和 B 是同一进制规则，且每一数位最高为 N 进制，最低为二进

制。请你算出 A − B 的结果最小可能是多少。

请注意，你需要保证 A 和 B 在 X 进制下都是合法的，即每一数位上的数

字要小于其进制。

【输入格式】

第一行一个正整数 N ，含义如题面所述。

第二行一个正整数 M a ，表示 X 进制数 A 的位数。

第三行 M a 个用空格分开的整数，表示 X 进制数 A 按从高位到低位顺序各

个数位上的数字在十进制下的表示。

第四行一个正整数 M b ，表示 X 进制数 B 的位数。

第五行 M b 个用空格分开的整数，表示 X 进制数 B 按从高位到低位顺序各

个数位上的数字在十进制下的表示。

请注意，输入中的所有数字都是十进制的。

【输出格式】

输出一行一个整数，表示 X 进制数 A − B 的结果的最小可能值转换为十进

制后再模 1000000007 的结果。

试题 E: X 进制减法

6 第十三届蓝桥杯大赛软件赛省赛 C/C++ 大学 B 组

【样例输入】

11

3

10 4 0

3

1 2 0

【样例输出】

94

【样例说明】

当进制为：最低位 2 进制，第二数位 5 进制，第三数位 11 进制时，减法

得到的差最小。此时 A 在十进制下是 108 ， B 在十进制下是 14 ，差值是 94 。

【评测用例规模与约定】

对于 30 % 的数据， N ≤ 10; M a , M b ≤ 8 .

对于 100 % 的数据， 2 ≤ N ≤ 1000; 1 ≤ M a , M b ≤ 100000; A ≥ B .

这个题没有读懂，不知啥意思，哪个321咋转换到65去了，一直转不过去，有懂得同学可以讲下，谢谢了。

第六题:

试题 F: 统计子矩阵

时间限制 : 1.0s

内存限制 : 256.0MB

本题总分： 15 分

【问题描述】

给定一个 N × M 的矩阵 A ，请你统计有多少个子矩阵 ( 最小 1 × 1 ，最大

N × M ) 满足子矩阵中所有数的和不超过给定的整数 K ?

【输入格式】

第一行包含三个整数 N , M 和 K .

之后 N 行每行包含 M 个整数，代表矩阵 A .

【输出格式】

一个整数代表答案。

【样例输入】

3 4 10

1 2 3 4

5 6 7 8

9 10 11 12

【样例输出】

19

【样例说明】

满足条件的子矩阵一共有 19 ，包含：

大小为 1 × 1 的有 10 个。

大小为 1 × 2 的有 3 个。

试题 F: 统计子矩阵

8 第十三届蓝桥杯大赛软件赛省赛 C/C++ 大学 B 组

大小为 1 × 3 的有 2 个。

大小为 1 × 4 的有 1 个。

大小为 2 × 1 的有 3 个。

【评测用例规模与约定】

对于 30 % 的数据， N , M ≤ 20 .

对于 70 % 的数据， N , M ≤ 100 .

对于 100 % 的数据， 1 ≤ N , M ≤ 500; 0 ≤ A i j ≤ 1000; 1 ≤ K ≤ 250000000 .

二位前缀和，不过要优化才能拿满分，给一个可以得80分得代码

#include
#include
#define max 505
int arr[max][max],kul[max][max];
int main()
{
	int n,m,k,val,i,j,p;
	scanf(\"%d%d%d\",&n,&m,&val);
	memset(kul,0,sizeof(kul));
	for(i=1; i<=n; i++)
	{
		for(j=1; j<=m; j++)
		{
			scanf(\"%d\",&arr[i][j]);
			kul[i][j]=kul[i-1][j]+kul[i][j-1]+arr[i][j]-kul[i-1][j-1];
		}
	}
	int flag=0,mi=0;
	for(i=1; i<=n; i++)
	{
		for(j=1; j<=m; j++)
		{
			for(k=i;k<=n;k++)
			{
				for(p=j;p<=m;p++)
				{
					if(kul[k][p]-kul[i-1][p]-kul[k][j-1]+kul[i-1][j-1]<=val)
					{
						flag++;
					}else{
						break;
					}
				}
			}
		}
	}
	printf(\"%d\",flag);
	return 0;
}

第七题:

试题 G: 积木画

时间限制 : 1.0s

内存限制 : 256.0MB

本题总分： 20 分

【问题描述】

小明最近迷上了积木画，有这么两种类型的积木，分别为 I 型（大小为 2

个单位面积）和 L 型（大小为 3 个单位面积）：

同时，小明有一块面积大小为 2 × N 的画布，画布由 2 × N 个 1 × 1 区域构

成。小明需要用以上两种积木将画布拼满，他想知道总共有多少种不同的方式？

积木可以任意旋转，且画布的方向固定。

【输入格式】

输入一个整数 N ，表示画布大小。

【输出格式】

输出一个整数表示答案。由于答案可能很大，所以输出其对 1000000007 取

模后的值

【样例输入】

3

【样例输出】

5

 这个题dp解起来还是比较好解得，用一维dp就可以解（和斐波那契数列有点像），前提是你会划分，将I型积木看成1个方格，将L型积木看成1.5个方格，然后开一个一维得dp[N]数组就可以了，你看最后一步，要不就是剩了2个积木，要不就是剩了6个积木（也就是两个L型的），所以状态转移方程就可以写成dp[i]=dp[i-1]*2+dp[i-3],这里乘以2是因为一个I型积木它的摆放位置有2种，看题目给的样例就明白了

 这是五中方法，你会发现他I型在一个位置可以放2种状态

然后就是初始化前三个分别是1，2，5

#include
#include
#define mod 1000000007
int dp[10000005];
int main()
{
	int n;
	scanf(\"%d\",&n);
	memset(dp,0,sizeof(dp));
	dp[1]=1,dp[2]=2,dp[3]=5;
	for(int i=4;i<=n;i++)
	{
		dp[i]=(dp[i-1]*2%mod+dp[i-3]%mod)%mod;
	}
	printf(\"%d\\n\",dp[n]);
	return 0;
}

第八题:

试题 H: 扫雷

时间限制 : 1.0s

内存限制 : 256.0MB

本题总分： 20 分

【问题描述】

小明最近迷上了一款名为《扫雷》的游戏。其中有一个关卡的任务如下，

在一个二维平面上放置着 n 个炸雷，第 i 个炸雷 ( x i , y i , r i ) 表示在坐标 ( x i , y i ) 处

存在一个炸雷，它的爆炸范围是以半径为 r i 的一个圆。

为了顺利通过这片土地，需要玩家进行排雷。玩家可以发射 m 个排雷火

箭，小明已经规划好了每个排雷火箭的发射方向，第 j 个排雷火箭 ( x j , y j , r j ) 表

示这个排雷火箭将会在 ( x j , y j ) 处爆炸，它的爆炸范围是以半径为 r j 的一个圆，

在其爆炸范围内的炸雷会被引爆。同时，当炸雷被引爆时，在其爆炸范围内的

炸雷也会被引爆。现在小明想知道他这次共引爆了几颗炸雷？

你可以把炸雷和排雷火箭都视为平面上的一个点。一个点处可以存在多个

炸雷和排雷火箭。当炸雷位于爆炸范围的边界上时也会被引爆。

【输入格式】

输入的第一行包含两个整数 n 、 m .

接下来的 n 行，每行三个整数 x i , y i , r i ，表示一个炸雷的信息。

再接下来的 m 行，每行三个整数 x j , y j , r j ，表示一个排雷火箭的信息。

【输出格式】

输出一个整数表示答案。

【样例输入】

2 1

2 2 4

4 4 2

0 0 5

试题 H: 扫雷

12 第十三届蓝桥杯大赛软件赛省赛 C/C++ 大学 B 组

【样例输出】

2

【样例说明】

示例图如下，排雷火箭 1 覆盖了炸雷 1 ，所以炸雷 1 被排除；炸雷 1 又覆

盖了炸雷 2 ，所以炸雷 2 也被排除。

【评测用例规模与约定】

对于 40 % 的评测用例： 0 ≤ x , y ≤ 1e 9 , 0 ≤ n , m ≤ 1e 3 , 1 ≤ r ≤ 10 .

对于 100 % 的评测用例： 0 ≤ x , y ≤ 1e 9 , 0 ≤ n , m ≤ 5 × 1e 4 , 1 ≤ r ≤ 10 .

 其实我想的是把它看成图来进行解答，用的floyd暴力解的（迪杰斯特拉时间复杂度也一样，因为要遍历全部点），时间复杂度可能太大了，勉强过40案例吧，你们把它给的雷和导弹全成点，然后构造一个无向无权图，如果说这两个点之间的距离小于等于他们的半径之和那就可以排雷就设置为1，然后用floyd将所有点都看一遍，最后遍历导弹那个点，也就是最后一排的1的个数就是可以排的雷的总数量

#include
#include
#define max 10005
int arr[max][max],a[2*max],b[2*max],c[2*max];
void init(int n,int m)
{
	int i,j;
	for(i=1; i<=n+m; i++)
	{
		for(j=1; j<=n+m; j++)
		{
			if(i==j)
			{
				arr[i][j]=0;
				continue;
			}
			if(sqrt(pow((a[i]-a[j]),2)+pow((b[i]-b[j]),2))<=c[i]+c[j])
			{
				arr[i][j]=1;
			}else{
				arr[i][j]=0;
			}
		}
	}
}
int floyd(int n,int m)
{
	int i,j,k,flag=0;
	for(k=1; k<=n+m; k++)
	{
		for(i=1; i<=n+m; i++)
		{
			for(j=1; j<=n+m; j++)
			{
				if(arr[i][k]==1&&arr[k][j]==1&&i!=j)
				{
					arr[i][j]=1;
				}
			}
		}
	}
	for(i=1;i<=n+m;i++)
	{
		if(arr[n+m][i]==1)
		{
			flag++;
		}
	}
	return flag;
}
int main()
{
	int n,m,i,j,k;
	scanf(\"%d%d\",&n,&m);
	for(i=1; i<=n+m; i++)
	{
		scanf(\"%d%d%d\",&a[i],&b[i],&c[i]);
	}
	init(n,m);
	printf(\"%d\",floyd(n,m));
	return 0;
}

第九题:

试题 I: 李白打酒加强版

时间限制 : 1.0s

内存限制 : 256.0MB

本题总分： 25 分

【问题描述】

话说大诗人李白，一生好饮。幸好他从不开车。

一天，他提着酒壶，从家里出来，酒壶中有酒 2 斗。他边走边唱：

无事街上走，提壶去打酒。

逢店加一倍，遇花喝一斗。

这一路上，他一共遇到店 N 次，遇到花 M 次。已知最后一次遇到的是花，

他正好把酒喝光了。

请你计算李白这一路遇到店和花的顺序，有多少种不同的可能？

注意：壶里没酒 ( 0 斗 ) 时遇店是合法的，加倍后还是没酒；但是没酒时遇

花是不合法的。

【输入格式】

第一行包含两个整数 N 和 M .

【输出格式】

输出一个整数表示答案。由于答案可能很大，输出模 1000000007 的结果。

【样例输入】

5 10

【样例输出】

14

【样例说明】

如果我们用 0 代表遇到花， 1 代表遇到店， 14 种顺序如下：

试题 I: 李白打酒加强版

14 第十三届蓝桥杯大赛软件赛省赛 C/C++ 大学 B 组

010101101000000

010110010010000

011000110010000

100010110010000

011001000110000

100011000110000

100100010110000

010110100000100

011001001000100

100011001000100

100100011000100

011010000010100

100100100010100

101000001010100

【评测用例规模与约定】

对于 40 % 的评测用例： 1 ≤ N , M ≤ 10 。

对于 100 % 的评测用例： 1 ≤ N , M ≤ 100 。

 dfs暴力搜索的，也是只能过50案例，没啥说的，直接暴力(这个题得满分应该要dp做，dfs不论你怎么剪最多过60案例，因为这个时间复杂度是o2的n次方)

#include
#include 
#define mod 1000000007
int N,M,flag=0,k=2,i=1,arr[105];
void dfs(int x,int y)
{
	if(x>N||y>M)                     
	   //如果超出去就剪枝 
	{
		return;
	}
	if(x