第十二届蓝桥杯省赛C/C++B组2021
A：空间（5分）
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
小蓝准备用 256MB256MB 的内存空间开一个数组，数组的每个元素都是 3232 位 二进制整数，如果不考虑程序占用的空间和维护内存需要的辅助空间，请问 256MB256MB 的空间可以存储多少个 3232 位二进制整数？
思路：
1MB=1024KB；1KB=1024B；1Byte=8bits。
#include <iostream>
using namespace std;
int main()
{
cout<<256/32*1024*1024*8<<endl;//不能写成256*1024*1024*8/32，前面几个数相乘后超过了能表示的范围
return 0;
}
B：卡片
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
小蓝有很多数字卡片，每张卡片上都是数字 00 到 99。 小蓝准备用这些卡片来拼一些数，他想从 11 开始拼出正整数，每拼一个， 就保存起来，卡片就不能用来拼其它数了。 小蓝想知道自己能从 11 拼到多少。 例如，当小蓝有 3030 张卡片，其中 00 到 99 各 33 张，则小蓝可以拼出 11 到 1010， 但是拼 1111 时卡片 11 已经只有一张了，不够拼出 1111。 现在小蓝手里有 00 到 99 的卡片各 20212021 张，共 2021020210 张，请问小蓝可以从 11 拼到多少？ 提示：建议使用计算机编程解决问题
此代码来自B站up主：小鸟嘎吱叫
#include <iostream>//遍历当前数字的每一位， 把对应位卡片数目减1
using namespace std;
int main()
{
int card[10]; //存放0-9这10种卡片的数量
for(int i=0;i<10;i++)
{
card[i]=2021;
}
for(int i=1;;i++)
{
int temp = i;
while(temp!=0)
{
int t=temp%10; //取最右边那一位
if(card[t]==0)
{
cout<<i-1<<endl;
return 0;
}
card[t]--;
temp/=10;
}
}
}
C：直线
以下思路和代码来自B站up主：小鸟嘎吱叫
直线：y=kx+b
（1）在给定范围内，任意两点之间构建一条直线。
（2）求出非重边的条数。
涉及知识点：
（1）相除不是整数，涉及到浮点型数据比较大小：对于double a,b；如果a-b<=1e-8（ 1*10的负8次方），则a和b相等。
（2）非重边：斜率或者截距不相等。
（3）垂直x轴，斜率相等，截距也相等。统计非重边时加上20条垂直x轴的直线。
C/C++对bool operator < (const p &a)const的认识，运算符重载详解
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
const int N=2e5+10; //200000 为什么要加10
struct line //表示直线
{
double k,b;
bool operator<(const line &t) const //对小于号进行重载 重载<操作符。可以对两个line使用<操作符进行比较 括号中的const表示参数t对象不会被修改，最后的const表明调用函数对象不会被修改!
{
if(k!=t.k) //规定了递增排序准则
{
return k<t.k;
}
return b<t.b;
}
} L[N]; //数组存储直线
int n=0;
int main()
{
for(int x1=0;x1<=19;x1++)
{
for(int y1=0;y1<=20;y1++)
{
for(int x2=0;x2<=19;x2++)
{
for(int y2=0;y2<=20;y2++)
{
if(x1!=x2) //不相等的时候才构边
{
double k=(double)(y2-y1)/(x2-x1);
double b=y1-k*x1;
L[n++]={k,b};
}
}
}
}
}
sort(L,L+n); //先给直线一个递增的排序，排序的准则在构建结构体时已经规定了，这里默认
//sort 函数用于C++中，对给定区间所有元素进行排序，默认为升序，也可进行降序排序。sort函数进行排序的时间复杂度为n*log2n，比冒泡之类的排序算法效率要高，sort函数包含在头文件为#include<algorithm>的c++标准库中。
int res=1;
for(int i=1;i<n;i++)
{
if(fabs(L[i].k-L[i-1].k)>1e-8||fabs(L[i].b-L[i-1].b)>1e-8)
{
res++;
}
}
cout<<res+20<<endl;
return 0;
}
D：货物摆放
题目描述
小蓝有一个超大的仓库，可以摆放很多货物。
现在，小蓝有 nn 箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、宽、高。
小蓝希望所有的货物最终摆成一个大的长方体。即在长、宽、高的方向上分别堆 LL、WW、HH 的货物,满足 n = L \times W \times Hn=L×W×H。
给定 nn，请问有多少种堆放货物的方案满足要求。
例如，当 n = 4n=4 时，有以下 66 种方案：1×1×4、1×2×2、1×4×1、2×1×2、2 × 2 × 1、4 × 1 × 11×1×4、1×2×2、1×4×1、2×1×2、2×2×1、4×1×1。
请问，当 n = 2021041820210418n=2021041820210418 （注意有 1616 位数字）时，总共有多少种方案？
提示：建议使用计算机编程解决问题。
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
约数只能对在整数范围内而言,而因数就不限于整数的范围。 例如:6×8=48。既可以说6和8都是48的因数,也可以说6和8都是48的约数
此代码来自B站up主：小鸟嘎吱叫
//#include<bits/stdc++.h>
#include <iostream>
#include<vector>
using namespace std;
typedef long long LL; //这样写就可以直接用ll代替long long的定义了
int main() //vector相关知识点看刘汝佳的算法笔记
{
LL n=2021041820210418;
vector<LL>d; //vector<typename> name;
for(LL i=1;i*i<n;i++)
{
if(n%i==0)
{
d.push_back(i); //在d的末尾添加元素
if(n/i!=i)
{
d.push_back(n/i); //是因子且小于sqrt(n)，则另一个因子大于sqrt(n)
}
}
}
int ans=0;
vector<LL>::iterator a,b,c;//通过迭代器访问vector容器内的元素 ，并且可以通过*a来访问vector中的元素
for(a=d.begin();a!=d.end();a++) //暴力枚举
{
for(b=d.begin();b!=d.end();b++)
{
for(c=d.begin();c!=d.end();c++)
{
if((*a)*(*b)*(*c)==n)
ans++;
}
}
}
cout<<ans<<endl;
return 0;
}
E：路径
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图 中的最短路径。
小蓝的图由 2021 个结点组成，依次编号 1 至 2021。
对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点 之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条 长度为 a 和 b 的最小公倍数的无向边相连。
例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无 向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。
请计算，结点 1 和结点 2021 之间的最短路径长度是多少。
提示：建议使用计算机编程解决问题。
此思路与代码来自B站up主：小鸟嘎吱叫
思路：图论，最短路径，以下代码采用dijkstra算法求解最短路径
最小公倍数：对于数字a,b，假定它们的最大公约数（最大公因子）是d，则它们的最小公倍数=（a*b）/d
memset(G, 0x3f, sizeof(G))含义
abs 与 fabs 区别
#include<iostream>
#include<cmath>
#include<string.h>
#include<algorithm>
using namespace std;
const int N=3000;
int g[N][N]; //使用邻接矩阵来存储图
int gcd(int a,int b) //最大公约数
{
if(b==0)
return a;
else
return gcd(b,a%b);
}
int lem(int a,int b) //最小公倍数
{
int d = gcd(a,b);
return a/d*b;
}
int n;
int dist[N]; //存储最短距离，最后要得到的是dist[n]~dist[2021]
bool st[N];
int dijkstra()
{
memset(dist,0x3f,sizeof dist); //初始化距离为最大
dist[1]=0; //自己到自己距离是0
for(int i=0;i<n-1;i++) //找到当前的t值
{
int t=-1;
for(int j=1;j<=n;j++)
{
if(!st[j]&&(t==-1||dist[j]<dist[t])) //j没有出现且t没有找到或者有更好，距离更小就需要更新t
t=j;
}
for(int j=1;j<=n;j++)
{
dist[j]=min(dist[j],dist[t]+g[t][j]);
}
st[t]=true;
}
if(dist[n]=0x3f3f3f3f)
{
return -1;
}
else return dist[n];
}
int main()
{
cin>>n;
memset(g,0x3f,sizeof g);
//开始建图
for(int i=1;i<=2021;i++)
{
for(int j=1;j<=2021;j++)
{
if(abs(i-j)<=21) //存在一条边
{
int w=lem(i,j); //最小公倍数：权值
g[i][j]=w;
}
}
}
//建图完成
int t=dijkstra();
cout<<t<<endl;
return 0;
}
F：时间显示
题目描述
小蓝要和朋友合作开发一个时间显示的网站。
在服务器上，朋友已经获取了当前的时间，用一个整数表示，值为从 19701970 年 11 月 11 日 00:00:0000:00:00 到当前时刻经过的毫秒数。
现在，小蓝要在客户端显示出这个时间。小蓝不用显示出年月日，只需要显示出时分秒即可，毫秒也不用显示，直接舍去即可。
给定一个用整数表示的时间，请将这个时间对应的时分秒输出。
输入描述
输入一行包含一个整数，表示时间。
输出描述
输出时分秒表示的当前时间，格式形如 HH:MM:SS，其中 HH 表示时，值为 00???? 到 2323????，MM 表示分，值为 00???? 到 5959???，SS 表示秒，值为 00?? 到 5959?。时、分、秒 不足两位时补前导 00。
以下思路来自B站up主：小鸟嘎吱叫
思路:
（1）将毫秒转化为秒
（2）将秒数控制在一天之内
（3）结果转换为HH:MM:SS格式
#include<iostream>
using namespace std;
const int temp=86400; //一天有86400秒
int main()
{
long long int n;
cin>>n;
n /= 1000;
n %= temp; //将秒数控制在一天之内
int hours = n/3600;
int t = n%3600;
int minutes = t/60;
int seconds = t%60;
printf("%02d:%02d:%02d",hours,minutes,seconds);
return 0;
}
%2d是将数字按宽度为2，采用右对齐方式输出，如果数据位数不到2位，则左边补空格。
%02d:默认情况下，数据数据宽度不够2位是用空格填补的，但是因为2d前面有0，表示，数据宽度不足时用0填补。
%.2d和% 02d一样。