蓝桥杯第十四届校内赛（第三期） C/C++ B组

浅浅的花香味﹌ 2023-09-26 18:19 174阅读 0赞

## 一、填空题 ##

## （一）最小的十六进制 ##

问题描述  
　　请找到一个大于 2022 的最小数，这个数转换成十六进制之后，所有的数位（不含前导 0）都为字母（A 到 F）。  
　　请将这个数的十进制形式作为答案提交。  
答案提交  
　　这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。  
![ffaf627d7d714ac0a1816426981174c7.png][]

## （二）Excel的列 ##

在 Excel 中，列的名称使用英文字母的组合。前 26 列用一个字母，依次为 A 到 Z，接下来 26\*26 列使用两个字母的组合，依次为 AA 到 ZZ。

请问第 2022 列的名称是什么？

![a759d8a315174aa8a1b7b2722d53bf18.png][]

## （三）相等日期 ##

借鉴 [zoeil][]

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <stack>
    #include <queue> 
    using namespace std;
    #define fi first
    #define se second
    typedef long long LL;
    typedef pair<int, int> PII;
     
    int month[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    int get(int x) {
    	int res = 0;
    	while(x) {
    		res += x % 10;
    		x /= 10;
    	}
    	return res;
    }
    int main()  {
    	int ans = 0;
    	for(int i = 1900; i <= 9999; i ++) {
    		int syear = get(i);
    		bool is_leap = !(i % 400) || (i % 100 && !(i % 4));
    		for(int j = 1; j <= 12; j ++) {
    			if(j == 2 && is_leap) month[2] = 29;
    			else month[2] = 28;
    			for(int k = 1; k <= month[j]; k ++)
    			{
    				int smd = get(j) + get(k);
    				if(smd == syear) {
    					ans ++;
    				}
    			}
    		}
    	}
    	cout << ans << endl;
    	return 0;
    }

## （四）多少种取法 ##

![89203b782bd9472bb1f2efffa1b1f841.png][]

## （五）最大连通分块 ##

小蓝有一个 30 行 60 列的数字矩阵，矩阵中的每个数都是 0 或 1 。

110010000011111110101001001001101010111011011011101001111110

010000000001010001101100000010010110001111100010101100011110

001011101000100011111111111010000010010101010111001000010100

101100001101011101101011011001000110111111010000000110110000

010101100100010000111000100111100110001110111101010011001011

010011011010011110111101111001001001010111110001101000100011

101001011000110100001101011000000110110110100100110111101011

101111000000101000111001100010110000100110001001000101011001

001110111010001011110000001111100001010101001110011010101110

001010101000110001011111001010111111100110000011011111101010

011111100011001110100101001011110011000101011000100111001011

011010001101011110011011111010111110010100101000110111010110

001110000111100100101110001011101010001100010111110111011011

111100001000001100010110101100111001001111100100110000001101

001110010000000111011110000011000010101000111000000110101101

100100011101011111001101001010011111110010111101000010000111

110010100110101100001101111101010011000110101100000110001010

110101101100001110000100010001001010100010110100100001000011

100100000100001101010101001101000101101000000101111110001010

101101011010101000111110110000110100000010011111111100110010

101111000100000100011000010001011111001010010001010110001010

001010001110101010000100010011101001010101101101010111100101

001111110000101100010111111100000100101010000001011101100001

101011110010000010010110000100001010011111100011011000110010

011110010100011101100101111101000001011100001011010001110011

000101000101000010010010110111000010101111001101100110011100

100011100110011111000110011001111100001110110111001001000111

111011000110001000110111011001011110010010010110101000011111

011110011110110110011011001011010000100100101010110000010011

010011110011100101010101111010001001001111101111101110011101

如果从一个标为 1 的位置可以通过上下左右走到另一个标为 1 的位置，则称两个位置连通。与某一个标为 1 的位置连通的所有位置（包括自己）组成一个连通分块。

请问矩阵中最大的连通分块有多大？ （简单递归即可）

![d56f5074200941b199592a63f01bd0a4.png][]

## 二、编程题 ##

## （六）哪一天 ##

给定一天是一周中的哪天，请问 n 天后是一周中的哪天？

输入格式

输入第一行包含一个整数 w，表示给定的天是一周中的哪天，w 为 1 到 6 分别表示周一到周六，w 为 7 表示周日。

第二行包含一个整数 n。

输出格式

输出一行包含一个整数，表示 n 天后是一周中的哪天，1 到 6 分别表示周一到周六，7 表示周日。

样例输入

样例输出

评测用例规模与约定

对于所有评测用例，1 <= n <= 1000000。

![5f64d5061ad74a019315c662cec81a1f.png][]

## （七）信号覆盖 ##

小蓝负责一块区域的信号塔安装，整块区域是一个长方形区域，建立坐标轴后，西南角坐标为 (0, 0)， 东南角坐标为 (W, 0)， 西北角坐标为 (0, H)， 东北角坐标为 (W, H)。其中 W, H 都是整数。

他在 n 个位置设置了信号塔，每个信号塔可以覆盖以自己为圆心，半径为 R 的圆形（包括边缘）。

为了对信号覆盖的情况进行检查，小蓝打算在区域内的所有横纵坐标为整数的点进行测试，检查信号状态。其中横坐标范围为 0 到 W，纵坐标范围为 0 到 H，总共测试 (W+1) \* (H+1) 个点。

给定信号塔的位置，请问这 (W+1)\*(H+1) 个点中有多少个点被信号覆盖。

输入格式

输入第一行包含四个整数 W, H, n, R，相邻整数之间使用一个空格分隔。

接下来 n 行，每行包含两个整数 x, y，表示一个信号塔的坐标。信号塔可能重合，表示两个信号发射器装在了同一个位置。

输出格式

输出一行包含一个整数，表示答案。

样例输入

10 10 2 5

0 0

7 0

样例输出

评测用例规模与约定

对于所有评测用例，1 <= W, H <= 100，1 <= n <= 100, 1 <= R <= 100, 0 <= x <= W, 0 <= y <= H。 （思路和第八题一样 ）

![d941afe286d0444cbdcc58be8843bcc6.png][]

## （八）清理水草 ##

小蓝有一个 n \* m 大小的矩形水域，小蓝将这个水域划分为 n 行 m 列，行数从 1 到 n 标号，列数从 1 到 m 标号。每行和每列的宽度都是单位 1 。

现在，这个水域长满了水草，小蓝要清理水草。

每次，小蓝可以清理一块矩形的区域，从第 r1 行（含）到第 r2 行（含）的第 c1 列（含）到 c2 列（含）。

经过一段时间清理后，请问还有多少地方没有被清理过。

输入格式

输入第一行包含两个整数 n, m，用一个空格分隔。

第二行包含一个整数 t ，表示清理的次数。

接下来 t 行，每行四个整数 r1, c1, r2, c2，相邻整数之间用一个空格分隔，表示一次清理。请注意输入的顺序。

输出格式

输出一行包含一个整数，表示没有被清理过的面积。

样例输入

2 3

1 1 1 3

1 2 2 2

样例输出

样例输入

30 20

5 5 10 15

6 7 15 9

样例输出

519

评测用例规模与约定

对于所有评测用例，1 <= r1 <= r2 <= n <= 100, 1 <= c1 <= c2 <= m <= 100, 0 <= t <= 100。

思路和第七题一样，甚至更简单

![37b5c61cc00a4ef5a7ea11c822093187.png][]

## （九）最长滑行 ##

小蓝准备在一个空旷的场地里面滑行，这个场地的高度不一，小蓝用一个 n 行 m 列的矩阵来表示场地，矩阵中的数值表示场地的高度。

如果小蓝在某个位置，而他上、下、左、右中有一个位置的高度（严格）低于当前的高度，小蓝就可以滑过去，滑动距离为 1 。

如果小蓝在某个位置，而他上、下、左、右中所有位置的高度都大于等于当前的高度，小蓝的滑行就结束了。

小蓝不能滑出矩阵所表示的场地。

小蓝可以任意选择一个位置开始滑行，请问小蓝最多能滑行多远距离。

输入格式

输入第一行包含两个整数 n, m，用一个空格分隔。

接下来 n 行，每行包含 m 个整数，相邻整数之间用一个空格分隔，依次表示每个位置的高度。

输出格式

输出一行包含一个整数，表示答案。

样例输入

4 5

1 4 6 3 1

11 8 7 3 1

9 4 5 2 1

1 3 2 2 1

样例输出

样例说明

滑行的位置一次为 (2, 1), (2, 2), (2, 3), (3, 3), (3, 2), (4, 2), (4, 3)。

评测用例规模与约定

对于 30% 评测用例，1 <= n <= 20，1 <= m <= 20，0 <= 高度 <= 100。

对于所有评测用例，1 <= n <= 100，1 <= m <= 100，0 <= 高度 <= 10000。

同第五题一样的思路，简单递归即可，只不过会有重复递归（n<=100,递归还能承，应该不会超时，若n再大点，就不行了），可以研究效率更高的算法。

![ec87e47d66c049cd9d9fb4bc5090203c.png][]

## （十）区间最小值 ##

小蓝有一个序列 a\[1\], a\[2\], …, a\[n\]。

给定一个正整数 k，请问对于每一个 1 到 n 之间的序号 i，a\[i-k\], a\[i-k+1\], …, a\[i+k\] 这 2k+1 个数中的最小值是多少？当某个下标超过 1 到 n 的范围时，数不存在，求最小值时只取存在的那些值。

输入格式

输入的第一行包含一整数 n。

第二行包含 n 个整数，分别表示 a\[1\], a\[2\], …, a\[n\]。

第三行包含一个整数 k 。

输出格式

输出一行，包含 n 个整数，分别表示对于每个序号求得的最小值。

样例输入

5 2 7 4 3

样例输出

2 2 2 3 3

评测用例规模与约定

（1）对于 30% 的评测用例，1 <= n <= 1000，1 <= a\[i\] <= 1000。

（2）对于 50% 的评测用例，1 <= n <= 10000，1 <= a\[i\] <= 10000。

这都不苟分吗，多容易啊

![82fe75801ec54fe295f9c5c5d1540e95.png][]

（可能有部分测评用例是超时的）

（3）对于所有评测用例，1 <= n <= 1000000，1 <= a\[i\] <= 1000000。

可以用算法 单调队列、线段树、动态规划、记忆搜索……

当然，也还能用“暴力”

![8fea07062d9245bd83da83a62c78ae28.png][]

##     ##

[ffaf627d7d714ac0a1816426981174c7.png]: https://img-blog.csdnimg.cn/ffaf627d7d714ac0a1816426981174c7.png
[a759d8a315174aa8a1b7b2722d53bf18.png]: https://img-blog.csdnimg.cn/a759d8a315174aa8a1b7b2722d53bf18.png
[zoeil]: https://blog.csdn.net/m0_62946761
[89203b782bd9472bb1f2efffa1b1f841.png]: https://img-blog.csdnimg.cn/89203b782bd9472bb1f2efffa1b1f841.png
[d56f5074200941b199592a63f01bd0a4.png]: https://img-blog.csdnimg.cn/d56f5074200941b199592a63f01bd0a4.png
[5f64d5061ad74a019315c662cec81a1f.png]: https://img-blog.csdnimg.cn/5f64d5061ad74a019315c662cec81a1f.png
[d941afe286d0444cbdcc58be8843bcc6.png]: https://img-blog.csdnimg.cn/d941afe286d0444cbdcc58be8843bcc6.png
[37b5c61cc00a4ef5a7ea11c822093187.png]: https://img-blog.csdnimg.cn/37b5c61cc00a4ef5a7ea11c822093187.png
[ec87e47d66c049cd9d9fb4bc5090203c.png]: https://img-blog.csdnimg.cn/ec87e47d66c049cd9d9fb4bc5090203c.png
[82fe75801ec54fe295f9c5c5d1540e95.png]: https://img-blog.csdnimg.cn/82fe75801ec54fe295f9c5c5d1540e95.png
[8fea07062d9245bd83da83a62c78ae28.png]: https://img-blog.csdnimg.cn/8fea07062d9245bd83da83a62c78ae28.png