第十三届蓝桥杯大赛软件赛 CC++省赛B组题解

A题：九进制转十进制 【问题描述】

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

【题目解答】

  直接算就可以，答案为1478

#include

int main()
{
	int a=2, b=0, c=2, d=2;
	printf("%d", a*729+b*81+c*9+d);
	return 0;
}

B题：顺子日期 【问题描述】

  小明特别喜欢顺子。

顺子指的就是连续的三个数字：123、456 等。

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

例如 20220123 就是一个顺子日期，因为它出现了一个顺子：123； 而 20221023 则不是一个顺子日期，它一个顺子也没有。

小明想知道在整个 2022年份中，一共有多少个顺子日期。

【题目解答】

  目前说法不统一，题目说连续的三个数字，表述不明确，所以答案就有多种，可能的答案有4、5、14、47，具体答案以官方给出的为准。

我在考试是写的是4。

#include
#include

int main()
{
	int month[]={31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
	int i, j, res=0;
	char str[10];
	for(i=0;i<12;i++)
		for(j=0;j<month[i];j++)
		{
			sprintf(str, "2022%02d%02d", i+1, j+1);
			int k, s = strlen(str);
			for(k=0;k<s-2;k++)
				if(str[k]!='0' && str[k]+1==str[k+1] && str[k+1]+1==str[k+2]) //0不算在寻找范围内，只正序，答案为4 
				//if(str[k]+1==str[k+1] && str[k+1]+1==str[k+2]) //012也算顺子，只正序，答案为14 
				//if((str[k]!='0' && str[k]+1==str[k+1] && str[k+1]+1==str[k+2]) || (str[k]!='2' && str[k]-1==str[k+1] && str[k+1]-1==str[k+2])) 
				//0不算在寻找范围内，正序+逆序，答案为5
				//if((str[k]+1==str[k+1] && str[k+1]+1==str[k+2]) || (str[k]-1==str[k+1] && str[k+1]-1==str[k+2])) 
				//012、210都算顺子，正序+逆序，答案为47
				{
					//puts(str); //展示对应日期 
					res++;
					break;
				}
		}
	printf("%d", res);
	return 0;
}

C题：刷题统计 【问题描述】

  小明决定从下周一开始努力刷题准备蓝桥杯竞赛。

他计划周一至周五每天做 a 道题目，周六和周日每天做 b 道题目。

请你帮小明计算，按照计划他将在第几天实现做题数大于等于 n 题？

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

  输出一个整数代表天数。

  对于 50% 的评测用例，1 ≤ a, b, n ≤ 10⁶.
  对于 100% 的评测用例，1 ≤ a, b, n ≤ 10¹⁸.

【输入样例】

10 20 99

【输出样例】

8

【题目解答】

  本题很简单，先看测试用例，大小在10¹⁸则需要用到long long int来保存数据，同时为保证程序时间不会超限，所以使总做题量除每周做题量，得数为用掉的周数，对余数进行模拟，最多进行七遍就可以得出做完余量的天数。

  最终答案 = 周数×7+做完余量的天数

#include

int main()
{
	long long int a, b, n;
	scanf("%lld%lld%lld", &a, &b, &n);
	long long int i, sum = 7*(n/(5*a+2*b));
	n %= 5*a+2*b;
	for(i=0;i<7 && n>0;i++)
	{
		n -= (i<5) ? a : b;
		sum++;
	}
	printf("%lld", sum);
	return 0;
}

D题：修剪灌木 【问题描述】

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

  有 N 棵灌木整齐的从左到右排成一排。

爱丽丝在每天傍晚会修剪一棵灌木，让灌木的高度变为 0 厘米。

爱丽丝修剪灌木的顺序是从最左侧的灌木开始，每天向右修剪一棵灌木。

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

直到修剪了最左的灌木后再次调转方向。

然后如此循环往复。

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

在第一天的早晨，所有灌木的高度都是 0 厘米。

爱丽丝想知道每棵灌木最高长到多高。

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

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

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

【输入样例】

3

【输出样例】

4
2
4

【题目解答】

  这道题直接找规律模拟即可。

先手算模拟找规律

• 三个灌木
  4 2 4
• 四个灌木
  6 4 4 6
• 五个灌木
  8 6 4 6 8

  算了三个数据以后找规律，很明显答案是：对 n 棵灌木中的第 i 个而言最高高度为| n-i | × 2，可以直接上手编代码了

#include

int main()
{
	int i, n;
	scanf("%d", &n);
	for(i=1;i<=n;i++)
		printf("%d\n", (i<=n/2) ? 2*(n-i) : 2*(i-1));
	return 0;
}

E题：X 进制减法 【问题描述】

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

  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 的结果。

  对于 30% 的数据，N ≤ 10; Ma, Mb ≤ 8.
  对于 100% 的数据，2 ≤ N ≤ 1000; 1 ≤ Ma, Mb ≤ 100000; A ≥ B.

【输入样例】

11
3
10 4 0
3
1 2 0

【输出样例】

94

【样例说明】

  当进制为：最低位 2 进制，第二数位 5 进制，第三数位 11 进制时，减法得到的差最小。

此时 A 在十进制下是 108，B 在十进制下是 14，差值是 94

【题目解答】

  很多人在这里就看不懂题了，其实这个题目是很简单的，我们来讲一下样例吧。

给的第一个数为10 4 0， 每位对应的进制分别为11 5 2， 那么转化为十进制的过程是(10×5+4)×2+0=108；第二个数为1 2 0， 每位对应的进制分别为11 5 2， 那么转化为十进制的过程是(1×5+2)×2+0=14；不难看出其中规律：
  （当前位置数×下一个位置的进制+下一个位置数）×下下个位置的进制+下下个位置数……
  直到最后一个位置的数为止。

  细心的小伙伴不难看出这种辗转乘的方法就是某进制转十进制的方法，所以最后一个数乘的应该是1（所以就直接忽略掉啦），而加完之后整个数也就变成了十进制。

然后题中说的最小结果，就是最高位的进制不需要考虑，让每一位的进制尽可能的小即可。

因为A、B的进制相同，所以第 i 位的进制就是max(A[i], B[i])+1，当然最小也要大于等于2哦。

  还要考虑到A和B的位数不一致而需要补0，最重点的是对10e9+7取余！！！，博主就忘记了这一点，现在已经后悔死了o(╥﹏╥)o
  上代码：

#include
#include

const long long int MAX=10e9+7;

int main()
{
	int i, j, n, ma, mb;
	long long int a=0, b=0;
	int al[100000], bl[100000];
	scanf("%d%d", &n, &ma);
	for(i=0;i<ma;i++)
		scanf("%d", &al[i]);
	scanf("%d", &mb);
	for(i=0;i<mb;i++)
		scanf("%d", &bl[i]);
	int max = (ma>mb) ? ma : mb;
	int k = (ma>mb) ? 1 : 0;
	int num = abs(ma-mb);
	for(i=0;i<max;i++)
	{
		int x = (i<num && k==0) ? 0 : al[i-num];
		int y = (i<num && k==1) ? 0 : bl[i-num]; 
		int p = (x>y) ? x : y;
		p = (p<2) ? 2 : p+1;
		a = a*p + x;
		b = b*p + y;
	}
	printf("%lld", abs(a-b)%MAX);
	return 0;
}

F题：统计子矩阵 【问题描述】

  给定一个 N × M 的矩阵 A，请你统计有多少个子矩阵 (最小 1 × 1，最大N × M) 满足子矩阵中所有数的和不超过给定的整数 K?

  输入第一行包含三个整数 N, M 和 K.
  之后 N 行每行包含 M 个整数，代表矩阵 A

  输出一个整数代表答案。

  对于 30% 的数据，N, M ≤ 20.
  对于 70% 的数据，N, M ≤ 100.
  对于 100% 的数据，1 ≤ N, M ≤ 500; 0 ≤ Ai j ≤ 1000; 1 ≤ K ≤ 250000000.

【输入样例】

3 4 10
1 2 3 4
5 6 7 8
9 10 11 12

【输出样例】

19

【题目解答】

  遇到这种题直接暴力模拟吧，六个循环套一起搞它。

当然要注意k是很大的一个数，虽然这个代码的时间复杂度并不允许我考虑 k 。

  上代码：

#include

int a[500][500];

int add(int i, int j, int x, int y);

int main()
{
	int i, j, n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
			scanf("%d", &a[i][j]); 
	int x, y, res=0;
	for(x=1;x<=n;x++)
		for(y=1;y<=m;y++)
			for(i=0;i<=n-x;i++)
				for(j=0;j<=m-y;j++)
					if(add(i, j, x, y) <= k)
						res++;
	printf("%d", res);
	return 0;
}

int add(int i, int j, int x, int y)
{
	int sum = 0, p, q;
	for(p=0;p<x;p++)
		for(q=0;q<y;q++)
			sum += a[i+p][j+q];
	return sum;
}

G题：积木画 【问题描述】

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

  输出一个整数表示答案。

由于答案可能很大，所以输出其对 1000000007 取模后的值

  对于所有测试用例，1 ≤ N ≤ 10000000.

【输入样例】

3

【输出样例】

5

【样例说明】

【题目解答】

  这道题考试的时候并没有看出来怎么做。

（当然现在也没看出来）

H题：扫雷 【问题描述】

  小明最近迷上了一款名为《扫雷》的游戏。

其中有一个关卡的任务如下，在一个二维平面上放置着 n 个炸雷，第 i 个炸雷 (xi, yi,ri) 表示在坐标 (xi, yi) 处存在一个炸雷，它的爆炸范围是以半径为 ri 的一个圆。

  为了顺利通过这片土地，需要玩家进行排雷。

玩家可以发射 m 个排雷火箭，小明已经规划好了每个排雷火箭的发射方向，第 j 个排雷火箭 (xj, yj,rj) 表示这个排雷火箭将会在 (xj, yj) 处爆炸，它的爆炸范围是以半径为 rj 的一个圆，在其爆炸范围内的炸雷会被引爆。

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

现在小明想知道他这次共引爆了几颗炸雷？
  你可以把炸雷和排雷火箭都视为平面上的一个点。

一个点处可以存在多个炸雷和排雷火箭。

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

  输入的第一行包含两个整数 n、m.
  接下来的 n 行，每行三个整数 xi, yi,ri，表示一个炸雷的信息。

  再接下来的 m 行，每行三个整数 xj, yj,rj，表示一个排雷火箭的信息。

  输出一个整数表示答案。

  对于 40% 的评测用例：0 ≤ x, y ≤ 109, 0 ≤ n, m ≤ 103, 1 ≤ r ≤ 10.
  对于 100% 的评测用例：0 ≤ x, y ≤ 109, 0 ≤ n, m ≤ 5 × 104, 1 ≤ r ≤ 10.

【输入样例】

2 1
2 2 4
4 4 2
0 0 5

【输出样例】

2

【样例说明】

【题目解答】

  没什么好说的了，直接上手模拟。

因为要考虑时间复杂度，所以选择递归模拟。

大概时间会超吧，但又有什么关系呢(〃‘▽’〃)

#include
#include

int n, res=0;
struct boom{
	int x;
	int y;
	int r;
	int k;
}a[50000];

int find(int x, int y, int r);

int main()
{
	int i, m, x, y, r;
	scanf("%d%d", &n, &m);
	for(i=0;i<n;i++)
	{
		scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].r);
		a[i].k = 0;
	}
	while(m--)
	{
		scanf("%d%d%d", &x, &y, &r);
		find(x, y, r);
	}
	printf("%d", res);
	return 0;
}

int find(int x, int y, int r)
{
	int i;
	for(i=0;i<n;i++)
		if(pow(a[i].x-x, 2)+pow(a[i].y-y, 2) <= pow(r, 2) && a[i].k==0)
		{
			res++;
			a[i].k = 1;
			find(a[i].x, a[i].y, a[i].r);
		}
}

I题：李白打酒加强版 【问题描述】

  话说大诗人李白，一生好饮。

幸好他从不开车。

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

他边走边唱：

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

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

  这一路上，他一共遇到店 N 次，遇到花 M 次。

已知最后一次遇到的是花，他正好把酒喝光了。

  请你计算李白这一路遇到店和花的顺序，有多少种不同的可能？
  注意：壶里没酒 ( 0 斗) 时遇店是合法的，加倍后还是没酒；但是没酒时遇花是不合法的。

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

  输出一个整数表示答案。

由于答案可能很大，输出模 1000000007 的结果。

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

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

【输入样例】

5 10

【输出样例】

14

【样例说明】

  如果我们用 0 代表遇到花，1 代表遇到店，14 种顺序如下：
   010101101000000
   010110010010000
   011000110010000
   100010110010000
   011001000110000
   100011000110000
   100100010110000
   010110100000100
   011001001000100
   100011001000100
   100100011000100
   011010000010100
   100100100010100
   101000001010100

【题目解答】

  这道题很好想明白，就是一开始有2斗酒，总共经过了 n+m 次 *** 作（ n 次店 m 次花）。

将它看成随机事件，每一次 *** 作遇到店或花的概率都是相同的，所以n次之后就会出现2ⁿ个结果，排除掉其中遇店次数超过 n 的、遇花次数超过 m 的和最后结果不为 0 的，剩下的就是可能的情况了。

当然，题目保证最后一次一定遇到花，所以就相当于是寻找经过 n+m-1 次 *** 作后得到结果为 1 的项，可以递归处理，也可以上手dp。

  下面强调一件事，注意取模！！！
  是的，还是我，又是这个大冤种，又忘了对10e9+7取模了…(｡•ˇ‸ˇ•｡)…。

  第一种方法，动态规划dp（注意空间可能不够）：

#include
#include

long long int res=0;
int dp[110][1000000][3]={0};

int main()
{
	int i, j, n, m;
	scanf("%d%d", &n, &m);
	dp[0][0][0] = 2, m-=1;
	int k = 1;
	int max = n+m;
	for(i=1;i<=max;i++)
	{
		for(j=0;j<k;j++)
		{
			if(dp[i-1][j][0] >= 0)
			{
				if(dp[i-1][j][1] >= n)
					dp[i][2*j][0] = -1;
				else
					dp[i][2*j][0] = dp[i-1][j][0]*2, dp[i][2*j][1] = dp[i-1][j][1]+1, dp[i][2*j][2] = dp[i-1][j][2];
				if(dp[i-1][j][2] >= m)
					dp[i][2*j+1][0] = -1;
				else
					dp[i][2*j+1][0] = dp[i-1][j][0]-1, dp[i][2*j+1][1] = dp[i-1][j][1], dp[i][2*j+1][2] = dp[i-1][j][2]+1;
			}
			else
				dp[i][2*j][0] = -1, dp[i][2*j+1][0] = -1;
		}
		k *= 2;
	} 
	for(i=0;i<k;i++)
	{
		if(dp[max][i][0]-1 == 0)
		{
			res++;
			if(res>=10e9+7) res = 0;
		}
	}
	printf("\n%d", res);
	return 0;
}

  第二种方法，递归（可能超时）：

#include

const long long int MAX=10e9+7;
long long int res=0;

void hua(int x, int n, int m); 

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	hua(2, n, m-1);
	printf("%d", res%MAX);
	return 0;
}

void hua(int x, int n, int m)
{
	if(x==1 && n==0 && m==0)
		res+=1;
	if(n > 0)
		hua(x*2, n-1, m);
	if(m > 0)
		hua(x-1, n, m-1);
}

J题：砍竹子 【问题描述】

  这天，小明在砍竹子，他面前有 n 棵竹子排成一排，一开始第 i 棵竹子的高度为 hi。

  他觉得一棵一棵砍太慢了，决定使用魔法来砍竹子。

魔法可以对连续的一段相同高度的竹子使用，假设这一段竹子的高度为 H，那么使用一次魔法可以把这一段竹子的高度都变为 ⌊ ⌊ H 2 ⌋ + 1 \sqrt{⌊ \frac{H}{2} ⌋ + 1} ⌊2H​⌋+1 ​ ⌋，其中 ⌊x⌋ 表示对 x 向下取整。

小明想知道他最少使用多少次魔法可以让所有的竹子的高度都变为 1。

  输入第一行为一个正整数 n，表示竹子的棵数。

  第二行共 n 个空格分开的正整数 hi，表示每棵竹子的高度

  输出一个整数表示答案。

  对于 20% 的数据，保证 n ≤ 1000, hi ≤ 10⁶。

  对于 100% 的数据，保证 n ≤ 2 × 10⁵, hi ≤ 10¹⁸。

【输入样例】

6
2 1 4 2 6 7

【输出样例】

5

【题目解答】

  做到这里已经没时间了，大概扫了一眼也应该不会，就放弃了。