第⼗三届蓝桥杯模拟赛（第⼆期）试题与题解C++
第⼗三届蓝桥杯模拟赛（第⼆期）试题与题解
1、试题A
【问题描述】
⼩蓝的IP地址为 192.168. * .21，其中 * 是⼀个数字，请问这个数字最⼤可能是多少 ?
题解
IP地址由四个字节组成，每个字节是⼀个8⽐特位的⽆符号数，最⼤为255
所以答案是255
2、试题B
【问题描述】
如果⼀个整数 g 能同时整除整数 A 和 B，则称 g 是 A 和 B 的公约数。例如：43 是 86 和 2021 的公约数。
请问在 1（含） 到 2021（含） 中，有多少个数与 2021 存在⼤于 1 的公约数。请注意 2021 和 2021 有⼤于 1 的公约数，因此在计算的时候要算⼀个。
题解：枚举
//答案 89
#include<iostream>
using namespace std;
int gcd(int a,int b){
return(a % b ==0)? b :gcd(b, a % b);
}
int main(){
int ans =0;
for(int i =1; i <=2021; i++){
if(gcd(2021, i)>1) ans++;
}
cout << ans << endl;
return0;
}
3、试题C
【问题描述】
2021 是⼀个⾮常特殊的数，它可以表⽰成两个⾮负整数的平⽅差，2021 = 45 * 45 - 2 * 2。
2025 也是同样特殊的数，它可以表⽰成 2025 = 45 * 45 - 0 * 0。
请问，在 1 到 2021 中有多少个这样的数？
请注意，有的数有多种表⽰⽅法，例如 9 = 3 * 3 - 0 * 0 = 5 * 5 - 4 * 4，在算答案时只算⼀次
⽅法⼀：枚举
假设有: x = a^2 - b^2 = (a + b) * (a - b)
可知 (a + b) 和 (a - b) 是 x 的⼀对约数
反过来，要判断 x 是否符合条件
可以出 x 的每⼀对约数，判断两约数是否能变成 (a + b) * (a - b)的形式，并且 a 和 b 都是正整数
因为 (a + b) + (a - b) = 2a (a + b) - (a - b) = 2b
所以判断这⼀对约数的和与差是否为偶数即可
若两数之和为偶数，那么两数之差也为偶数，所以两者判断其⼀即可
//答案 1516
#include<bits/stdc++.h>
using namespace std;
bool check(int x){
int n =sqrt(x);
for(int i =1; i <= n; i++){
if(x % i ==0&&(i + x / i)%2==0){
return true;;
}
}
return false;
}
int main(){
int ans =0;
for(int i =1; i <=2021; i++){
ans +=check(i);
}
cout << ans << endl;
return0;
}
⽅法⼆：枚举因数
⽅法⼀是为判断某个数是否是特别的数，⽅法⼆是枚举出特别的数，判断是否在 1 ~ 2021 范围内
令 i 代替 (a + n)，j 代替 (a - b) 枚举，若 (i + j) 是偶数并且 (i * j) 在范围内就打上标记，最后查有多少个数被标记
//答案 1516
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[2022]={0};
for(int i =1; i <=2021; i++){
for(int j =1; j <= i; j++){
if((i + j)%2==0&& i * j <=2021){
a[i * j]=1;
}
}
}
int ans =0;
for(int i =1; i <=2021; i++){
ans += a[i];
}
cout << ans << endl;
return0;
}
4、试题D
【问题描述】
⼩蓝要⽤01串来表达⼀段⽂字，这段⽂字包含 a, b, c, d, e, f 共 6 个字母，每个字母出现的次数依次为：a 出现 10 次，b 出现 20 次，c 出现 3 次，d 出现 4 次，e 出现 18 次，f 出现 50 次。
⼩蓝准备分别对每个字母使⽤确定的 01 串来表⽰，不同字母的 01 串长度可以不相同。
　在表⽰⽂字时，将每个字母对应的 01 串直接连接起来组成最终的 01 串。为了能够正常还原出⽂字，⼩蓝的编码必须是前缀码，即任何⼀个字符对应的 01 串都不能是另⼀个字符对应的 01 串的前缀。
例如，以下是⼀个有效的编码：
a: 000
b: 111
c: 01
d: 001
e: 110
f : 100
其中 c 的长度为 2，其它字母的编码长度为 3，这种⽅式表⽰这段⽂字需要的总长度为：103 + 203 + 32 + 43 + 183 + 503 = 312。
上⾯的编码显然不是最优的，将上⾯的 f 的编码改为 10，仍然满⾜条件，但是总长度为 262，要短 50。
要想编码后的总长度尽量⼩，应当让出现次数多的字符对应的编码短，出现次数少的字符对应的编码长。
请问，在最优情况下，编码后的总长度最少是多少？
题解：哈夫曼编码
将每个字符出现的次数作为权值，每次取出最⼩的两个权值，作为⼆叉树的左右节点，再将权值之和作为⽗节点，放回队列中，循环此过程构建哈夫曼树
⾃⼆叉树根节点开始，向左为 0，向右为 1，得出每个字符的编码，结果如下：
左右⼦节点的位置不同，会使编码结果不同，但位数相同
a:1101(4位)    b:10(2位) c:11000(5位)
d:11001(5位)  e:111(3位)    f:0(1位)
所以答案为：4*10+2*20+5*3+5*4+3*18+1*50=219
5、试题E
【问题描述】
下⾯的矩阵中包含 ABCDEF 六种字符，请问出现最多的字符出现了⼏次？
FFEEFEAAECFFBDBFBCDA
DACDEEDCCFFAFADEFBBA
FDCDDCDBFEFCEDDBFDBE
EFCAAEECEECDCDECADDC
DFAEACECFEADCBFECADF
DFBAAADCFAFFCEADFDDA
EAFAFFDEFECEDEEEDFBD
BFDDFFBCFACECEDCAFAF
EFAFCDBDCCBCCEADADAE
BAFBACACBFCBABFDAFBE
FCFDCFBCEDCEAFBCDBDD
BDEFCAAAACCFFCBBAAEE
CFEFCFDEEDCACDACECFF
BAAAFACDBFFAEFFCCCDB
FADDDBEBCBEEDDECFAFF
CDEAFBCBBCBAEDFDBEBB
BBABBFDECBCEFAABCBCF
FBDBACCFFABEAEBEACBB
DCBCCFADDCACFDEDECCC
BFAFCBFECAACAFBCFBAF
题解：哈希表
⽤数组代替哈希映射即可
//⽤题⽬中的矩阵作为输⼊可得出答案
//答案 78
#include<iostream>
using namespace std;
int mp[200], idx =0;
string str;
int main(){
for(int i =0; i <20; i++){
cin >> str;
for(int j =0; j < str.length(); j++){
mp[str[j]]++;
}
}
for(int i =0; i <200; i++){
if(mp[i]){
cout <<char(i)<<"  "<< mp[i]<< endl;
if(mp[i]> mp[idx]) idx = i;
}
}
cout <<"ans = "<< mp[idx]<< endl;
return0;
}
6、试题F
【问题描述】
⼩蓝要到店⾥买铅笔。
铅笔必须⼀整盒⼀整盒买，⼀整盒 12 ⽀，价格 p 元。
⼩蓝⾄少要买 t ⽀铅笔，请问他最少花多少钱？
【输⼊格式】
输⼊⼀⾏包含两个整数 p、t，⽤⼀个空格分隔。
【输出格式】
输出⼀⾏包含—个整数，表⽰答案。
【样例输⼊】
5 30
【样例输出】
15
【评测⽤例规模与约定】
对于所有评测⽤例， 1 <= p <= 100，1 <= v <= 10000。题解
t / 12 表⽰盒数，若 t % 12 不为 0 就多买⼀盒
#include<iostream>
using namespace std;
int main(){
int p, t;
cin >> p >> t;
int k =(t /12)+bool(t %12);
cout << k * p << endl;
return0;
}
7、试题G
【问题描述】
给定⼀个三⾓形的三条边的长度 a, b, c，请问这个三⾓形是不是⼀个直⾓三⾓形。
【输⼊格式】
输⼊⼀⾏包含三个整数 a, b, c，表⽰三⾓形三边的长度，相邻整数之间⽤⼀个空格分隔。【输出格式】
如果是直⾓三⾓形，输出 “YES”（全⼤写），否则输出 “NO”（全⼤写）。
【样例输⼊】
3 4 5
namespace是干嘛的【样例输出】
YES
【样例输⼊】
4 5 4
【样例输出】
NO
【评测⽤例规模与约定】
对于50%的评测⽤例， 1 <= a, b, c <= 1000。
题解
排序，最⼩的两个数的平⽅和等于最⼤数的平⽅，就是直⾓三⾓形

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。