第十二届蓝桥杯省赛第一场C/C++ B组真题及部分题解

比眉伴天荒 2023-01-14 00:47 113阅读 0赞

**上一篇博客：[算法竞赛常用知识][Link 1]**

>  写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

### 文章目录 ###

*  A 空间
 *   *  题目描述
     *  题解
 *  B 卡片
 *   *  题目描述
     *  题解
 *  C 直线
 *   *  题目描述
 *  D 货物摆放
 *   *  题目描述
 *  E 路径
 *   *  题目描述
     *  题解
     *   *  解题思路
         *  解题代码
 *  F 时间显示
 *   *  题目信息
     *   *  题目描述
         *  输入格式
         *  输出格式
         *  样例输入 1
         *  样例输出 1
         *  样例输入 2
         *  样例输出 2
         *  评测用例规模与约定
     *  题解
 *  G 砝码称重
 *   *  题目描述
     *  输入格式
     *  输出格式
     *  样例输入
     *  样例输出
     *  样例说明
     *  评测用例规模与约定
 *  H 杨辉三角形
 *   *  题目信息
     *   *  题目描述
         *  输入格式
         *  输出格式
         *  样例输入
         *  样例输出
         *  评测用例规模与约定
     *  题解
     *   *  解题思路
         *  解题代码
 *  I 双向排序
 *   *  题目信息
     *   *  题目描述
         *  输入格式
         *  输出格式
         *  样例输入
         *  样例输出
         *  样例说明
         *  评测用例规模与约定
     *  题解
     *   *  解题思路
         *  解题代码

# A 空间 #

## 题目描述 ##

小蓝准备用 **256MB** 的内存空间开一个数组，数组的每个元素都是 **32** 位二进制整数，如果不考虑程序占用的空间和维护内存需要的辅助空间，请问 **256MB** 的空间可以存储多少个 **32** 位二进制整数？

## 题解 ##

**1MB = 1024KB，1KB = 1024Byte，1Byte = 8bit**，32位二进制整数占 **4** 个字节（Byte）。所以本题的答案为：**256 \* 1024 \* 1024 / 4 = 67108864**

# B 卡片 #

## 题目描述 ##

小蓝有很多数字卡片，每张卡片上都是数字 **0** 到 **9**。

小蓝准备用这些卡片来拼一些数，他想从 **1** 开始拼出正整数，每拼一个，就保存起来，卡片就不能用来拼其它数了。

小蓝想知道自己能从 **1** 拼到多少。

例如，当小蓝有 **30** 张卡片，其中 **0** 到 **9** 各 **3** 张，则小蓝可以拼出 **1** 到 **10**，但是拼 **11** 时卡片 **1** 已经只有一张了，不够拼出 **11**。

现在小蓝手里有 **0** 到 **9** 的卡片各 **2021** 张，共 **20210** 张，请问小蓝可以从 **1** 拼到多少？

提示：建议使用计算机编程解决问题。

## 题解 ##

开一个统计数组 **cnt\[\]**，从 **0 ~ 9** 都赋值为 **2021**，然后从 **1** 开始拆数，每用一个数字就将统计数组对应的数字的总数减一，直到统计数组对应的数字的总数为 **0** 时结束循环，`输出当前结果减一就可以，因为题目要求我们求出能拼到第几个数字，而最后那个数字是拼不出来的，因为数字已经不够用了`。

#include<iostream>
    #include<algorithm>
    
    using namespace std;
    
    const int N = 16;
    int cnt[N] = { 2021,2021,2021,2021,2021,2021,2021,2021,2021,2021};
    
    int main() { 
    	int i = 1;
    	bool flag = true;
    	while (flag) { 
    		int x = i;
    		while (x) { 
    			// 当前用到的数不够用了，则退出 
    			if (cnt[x % 10] == 0) { 
    				cout << i << endl;
    				flag = false;
    				break; 
    			}
    			cnt[x % 10]--;
    			x /= 10;
    		}
    		i++;
    	}
    	return 0;
    	// 3181
    }

# C 直线 #

## 题目描述 ##

在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上，那么这些点中任意两点确定的直线是同一条。

给定平面上 **2 × 3** 个整点 **\{(x, y)|0 ≤ x < 2, 0 ≤ y < 3, x ∈ Z, y ∈ Z\}**，即横坐标是 **0** 到 **1** (包含 **0** 和 **1**) 之间的整数、纵坐标是 **0** 到 **2** (包含 **0** 和 **2**) 之间的整数的点。这些点一共确定了 **11** 条不同的直线。

给定平面上 **20 × 21** 个整点 **\{(x, y)|0 ≤ x < 20, 0 ≤ y < 21, x ∈ Z, y ∈ Z\}**，即横坐标是 **0** 到 **19** (包含 **0** 和 **19**) 之间的整数、纵坐标是 **0** 到 **20** (包含 **0** 和 **20**) 之间的整数的点。请问这些点一共确定了多少条不同的直线。

# D 货物摆放 #

## 题目描述 ##

小蓝有一个超大的仓库，可以摆放很多货物。

现在，小蓝有 **n** 箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、宽、高。

小蓝希望所有的货物最终摆成一个大的立方体。即在长、宽、高的方向上分别堆 **L、W、H** 的货物，满足 **n = L × W × H**。

给定 **n**，请问有多少种堆放货物的方案满足要求。

例如，当 **n = 4** 时，有以下 **6** 种方案：**1×1×4、1×2×2、1×4×1、2×1×2、 2 × 2 × 1、4 × 1 × 1**。

请问，当 **n = 2021041820210418** （注意有 16 位数字）时，总共有多少种方案？

提示：建议使用计算机编程解决问题。

# E 路径 #

## 题目描述 ##

小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。

小蓝的图由 **2021** 个结点组成，依次编号 **1** 至 **2021**。

对于两个不同的结点 **a, b**，如果 **a** 和 **b** 的差的绝对值大于 **21**，则两个结点之间没有边相连；如果 **a** 和 **b** 的差的绝对值小于等于 **21**，则两个点之间有一条长度为 **a** 和 **b** 的最小公倍数的无向边相连。

例如：结点 **1** 和结点 **23** 之间没有边相连；结点 **3** 和结点 **24** 之间有一条无向边，长度为 **24**；结点 **15** 和结点 **25** 之间有一条无向边，长度为 **75**。

请计算，结点 **1** 和结点 **2021** 之间的最短路径长度是多少。

提示：建议使用计算机编程解决问题。

## 题解 ##

### 解题思路 ###

本题主要考察 `Dijkstra算法`，可以使用该算法解决本题，关于该算法的详细思路请看之前的博客：**[朴素Dijkstra算法][Dijkstra]**。最小公倍数的求法详见之前的博客：**[如何求最小公倍数][Link 2]**。本题答案：**10266837**

### 解题代码 ###

#include<iostream>
    #include<cstring>
    #include<algorithm>
    
    using namespace std;
    
    const int N = 2030;
    int g[N][N];
    int dist[N];
    bool st[N];
    
    int gcd(int m, int n) { 
    	return n ? gcd(n, m % n) : m;
    }
    
    int dijkstra() { 
    	memset(dist, 0x3f, sizeof dist);
    	dist[1] = 0;
    	for (int i = 0; i < 2021; i++) { 
    		int t = -1;
    		// 找出距离源点最近的点 
    		for (int j = 1; j <= 2021; j++) { 
    			if (!st[j] && (t == -1 || dist[j] < dist[t])) t = j;
    		}
    		st[t] = true;
    		// 遍历 t 的所有出边
    		for (int j = 1; j <= 2021; j++) { 
    			dist[j] = min(dist[j], dist[t] + g[t][j]);
    		} 
    	}
    	return dist[2021];
    }
    
    int main() { 
    	memset(g, 0x3f, sizeof g);
    	for (int i = 1; i <= 2021; i++) { 
    		for (int j = 1; j <= 2021; j++) { 
    			if (i != j && j - i <= 21) g[i][j] = i * j / gcd(i, j); 
    		}
    	}
    	cout << dijkstra() << endl;
    	return 0;
    }

# F 时间显示 #

## 题目信息 ##

### 题目描述 ###

小蓝要和朋友合作开发一个时间显示的网站。在服务器上，朋友已经获取了当前的时间，用一个整数表示，值为从 **1970** 年 **1** 月 **1** 日 **00:00:00** 到当前时刻经过的毫秒数。

现在，小蓝要在客户端显示出这个时间。小蓝不用显示出年月日，只需要显示出时分秒即可，毫秒也不用显示，直接舍去即可。

给定一个用整数表示的时间，请将这个时间对应的时分秒输出。

### 输入格式 ###

输入一行包含一个整数，表示时间。

### 输出格式 ###

输出时分秒表示的当前时间，格式形如 **HH:MM:SS**，其中 **HH** 表示时，值为 **0** 到 **23**，**MM** 表示分，值为 **0** 到 **59**，**SS** 表示秒，值为 **0** 到 **59**。时、分、秒不足两位时补前导 **0**。

### 样例输入 1 ###

**46800999**

### 样例输出 1 ###

**13:00:00**

### 样例输入 2 ###

**1618708103123**

### 样例输出 2 ###

**01:08:23**

### 评测用例规模与约定 ###

对于所有评测用例，给定的时间为不超过 **1018** 的正整数。

## 题解 ##

注意 *输出格式* 以及 `1s = 1000ms` 即可。

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    
    using namespace std;
    typedef long long LL; 
    LL n;
    int h, m, s;
    
    int main() { 
    	cin >> n;
    	n /= 1000; // 一共多少秒
    	s = n % 60;
    	n -= n % 60;
    	n /= 60;
    	
    	m = n % 60;
    	n -= n % 60;
    	n /= 60;
    	
    	h = n % 24;
    	
    	printf("%02d:%02d:%02d", h, m, s);
    	
    	return 0;
    }

# G 砝码称重 #

## 题目描述 ##

你有一架天平和 **N** 个砝码，这 **N** 个砝码重量依次是 **W1, W2, · · · , WN**。 请你计算一共可以称出多少种不同的重量？

注意砝码可以放在天平两边。

## 输入格式 ##

输入的第一行包含一个整数 **N**。  
 第二行包含 **N** 个整数：**W1, W2, · · · , WN**。

## 输出格式 ##

输出一个整数代表答案。

## 样例输入 ##

> **3  
> 1 4 6**

## 样例输出 ##

> **10**

## 样例说明 ##

能称出的 **10** 种重量是：**1、2、3、4、5、6、7、9、10、11**。  
1 = 1；  
2 = 6 − 4 (天平一边放 6，另一边放 4)；  
3 = 4 − 1；  
4 = 4；  
5 = 6 − 1；  
6 = 6；  
7 = 1 + 6；  
9 = 4 + 6 − 1；  
10 = 4 + 6；  
11 = 1 + 4 + 6。

## 评测用例规模与约定 ##

对于 **50%** 的评测用例，**1 ≤ N ≤ 15**。  
 对于所有评测用例，**1 ≤ N ≤ 100**，**N** 个砝码总重不超过 **100000**。

# H 杨辉三角形 #

## 题目信息 ##

### 题目描述 ###

下面的图形是著名的杨辉三角形：  
![杨辉三角形][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_000000_t_70]  
 如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列：

**1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, …**

给定一个正整数 **N**，请你输出数列中第一次出现 **N** 是在第几个数？

### 输入格式 ###

输入一个整数 **N**。

### 输出格式 ###

输出一个整数代表答案。

### 样例输入 ###

> **6**

### 样例输出 ###

> **13**

### 评测用例规模与约定 ###

对于 **20%** 的评测用例，**1 ≤ N ≤ 10**；  
 对于所有评测用例，**1 ≤ N ≤ 1000000000**。

## 题解 ##

### 解题思路 ###

感觉像是一个滚动数组的题目，但是没有看出规律。打了一个 **1 ~ 10** 的表，早知道就多打点表，多骗一些分了233。

### 解题代码 ###

#include<iostream>
    
    using namespace std;
    
    const int N = 20;
    
    int q[N] = { 0,1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,1,5,10};
    
    int main() { 
    	int n;
    	cin >> n;
    	for (int i = 0; i < N; i++) { 
    		if(q[i] == n) { 
    			cout << i;
    			break;
    		}
    	}
    	return 0;
    }

# I 双向排序 #

## 题目信息 ##

### 题目描述 ###

给定序列 **(a1, a2, · · · , an) = (1, 2, · · · , n)**，即 **ai = i**。

小蓝将对这个序列进行 **m** 次操作，每次可能是将 **a1, a2, · · · , aqi** 降序排列，或者将 **aqi , aqi+1, · · · , an** 升序排列。

请求出操作完成后的序列。

### 输入格式 ###

输入的第一行包含两个整数 **n, m**，分别表示序列的长度和操作次数。

接下来 **m** 行描述对序列的操作，其中第 i 行包含两个整数 **pi, qi** 表示操作类型和参数。当 **pi = 0** 时，表示将 **a1, a2, · · · , aqi** 降序排列；当 **pi = 1** 时，表示将 **aqi , aqi+1, · · · , an** 升序排列。

### 输出格式 ###

输出一行，包含 **n** 个整数，相邻的整数之间使用一个空格分隔，表示操作完成后的序列。

### 样例输入 ###

> **3 3  
> 0 3  
> 1 2  
> 0 2**

### 样例输出 ###

> **3 1 2**

### 样例说明 ###

原数列为 **(1, 2, 3)**。  
 第 **1** 步后为 **(3, 2, 1)**。  
 第 **2** 步后为 **(3, 1, 2)**。  
 第 **3** 步后为 **(3, 1, 2)**。与第 **2** 步操作后相同，因为前两个数已经是降序了。

### 评测用例规模与约定 ###

对于 **30%** 的评测用例，**n, m ≤ 1000**；  
 对于 **60%** 的评测用例，**n, m ≤ 5000**；  
 对于所有评测用例，**1 ≤ n, m ≤ 100000，0 ≤ pi ≤ 1，1 ≤ qi ≤ n**。

## 题解 ##

### 解题思路 ###

直接用 **sort()** 做的，但是拿不到全部的分数，最多能拿 **60%** 的分数。

### 解题代码 ###

#include<iostream>
    #include<algorithm>
    #include<cstdio>
    
    using namespace std;
    
    const int N = 100010;
    int arr[N];
    
    // 降序排列规则 
    bool cmp(int x, int y) { 
    	return x > y; 
    } 
    
    int main() { 
    	int n, m;
    	cin >> n >> m;
    	for (int i = 0; i < n; i++) arr[i] = i + 1;
    	for (int i = 1; i <= m; i++) { 
    		int p, q;
    		scanf("%d%d", &p, &q);
    		if (p == 0) { 
    			// 首先判断是否是升序，如果是升序则sort，否则不sort 
    			if (arr[0] < arr[1]) sort(arr, arr + q, cmp);  
    		}
    		if (p == 1) { 
    			// 先判断是否是降序，如果是降序则改为升序
    			if (arr[n - 1] < arr[n - 2]) sort(arr + q - 1, arr + n); 
    		}
    	}
    	
    	for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    	return 0; 
    }

--------------------

> 未完待续，持续更新中……  
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_ffffff_t_70][]![赶紧学习，缩小差距][20210423170423644.png]

[Link 1]: https://ac-fun.blog.csdn.net/article/details/115498226
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[Dijkstra]: https://ac-fun.blog.csdn.net/article/details/114372108
[Link 2]: https://ac-fun.blog.csdn.net/article/details/90902890
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_000000_t_70]: /images/20221022/ae2a26dce79048319217f7b25ac926a8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_ffffff_t_70]: https://img-blog.csdnimg.cn/20210221121326191.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3,size_16,color_ffffff,t_70
[20210423170423644.png]: https://img-blog.csdnimg.cn/20210423170423644.png