2021第十二届蓝桥杯CC++B组省赛 第一场 部分题目总结

试题A:

思路：考计算机基础知识
bit:位，又名比特，缩写是b,是计算机中最小的数据单位，其实就是0,1这样的二进制位
Byte:字节，缩写是B,是计算机文件大小的基本计算单位，一个字符是1Byte,如果是汉字，则是2Byte
1Byte=8bit
1Byte=8bit(1B=8b) 1个字节=8位,即一个字节由8个二进制位构成
1KB=1024Byte
1MB=1024KB
1GB=1024MB
1TB=1024GB
所以本题：
1个32位二进制数占4个字节
25610241024/4=67108864
答案：67108864

试题B：卡片

思路：签到题，用一个数组去存0-9的卡片，然后从1开始暴力枚举每一个数，拆分出每一位x，对应的数组中x的个数减一，如果这个数对应的卡片数量用完了，那么就不能再继续拼下去了

#include
using namespace std;
int a[10];
int ans=0;
int check(int n)
{
	while(n>0)
	{
		int x=n%10;
		a[x]--;
		n/=10;
		if(a[x]==0)
		{
			return 0;
		}
	}
	return 1;
} 
int main()
{
	for(int i=0;i<=9;i++)
	{
		a[i]=2021;
	}
	for(int i=1;;i++)
	{
		 int flag=check(i);
		 if(flag==0)
		 {
		 	ans=i;
		 	break;
		 }
	} 
	cout<<ans<<endl;
}

答案：3181

试题C 直线

这个题要特别注意map容器的用法，这里的键是一个数对

思路：先4重循环枚举可以组成的点的所有斜率k和截距b,其中注意类型转换，其中截距b的计算不能通过k直接求出，要通过两个点的坐标得出，减少误差，为了避免除数为0的情况，如果两个点的横坐标一样，要单独计算,所以最后的答案要加20，利用map容器去标记，然后统计即可

#include
#include
using namespace std;
map<pair<double, double>, int> mapp;
int main() {
	int ans = 0;
	for (int i = 0; i <= 19; i++) {//枚举第一个点的横坐标 
		for (int j = 0; j <= 20; j++) {//枚举第一个点的纵坐标 
			for (int k = 0; k <= 19; k++) {//枚举第一个点的横坐标 
				for (int h = 0; h <= 20; h++) {//枚举第一个点的纵坐标 
					double i1 = i;//类型转换 
					double j1 = j;
					double k1 = k;
					double h1 = h;
					if ((k1 - i1) != 0) {
						double kk = (h1 - j1) / (k1 - i1);//斜率 
						double bb = (i1 * h1 - k1 * j1) / (i1 - k1);
						if (mapp[ {kk, bb}] == 0) {
							mapp[ {kk, bb}] = 1;
							ans++;

						}
					}
				}
			}
		}
	}
  /*	map, int> ::iterator iter;
	for (iter = mapp.begin(); iter != mapp.end(); iter++) {
		cout << (*iter).first.first << " " << (*iter).first.second << endl;
	}*/
	cout << ans+20 << endl;
}

答案：40257

试题D 货物摆放

思路： n达到了1e16,所以暴力枚举肯定TLE，那么我们可以这样想，如果
n=LWH,那么L,W,H都是n的因子，所以我们就可以枚举n的因数，求因子的时间复杂度在sqrt(n)级别，把n降到1e8,那么这个时间复杂度就是可以接受的，所有的因数存到数组中,然后再三层循环枚举数组中相乘能组成2021041820210418的数，输出即可

#include
/*#include
#include
#include
#include
using namespace std;
long long int a[10000 + 10];
int main() {
	long long int n = 2021041820210418;
	int k=0;
	for (int i = 1; i <= sqrt(n); i++) {
		if (n % i == 0) {
            a[k++]=i;
            if(i!=(n/i))
            a[k++]=n/i;
		}
	}
	int ans=0;
	for(int i=0;i<=k;i++)
	{
		for(int j=0;j<=k;j++)
		{
			for(int h=0;h<=k;h++)
			{
				if(a[i]*a[j]*a[h]==n)
				{
					ans++;
					
				}
			}
		}
	}
	cout<<ans<<endl;
}

答案：2430

试题E:路径

思路：涉及到两个知识点，单源最短路径，dijkstra算法板子以及简单数论欧几里得求最小公倍数

#include
using namespace std;
int mapp[2022][2022];
int dis[2022];
int book[2022];
#define inf 0x3f3f3f3f
int gcd(int i, int j) {
	if (i % j == 0) {
		return j;
	} else {
		return gcd(j, i % j);
	}
}
int main() {
	//初始化mapp数组
	for (int i = 1; i <= 2021; i++) {
		for (int j = 1; j <= 2021; j++) {
			if (i == j) {
				mapp[i][j] = 0;
			} else if (abs(i - j) <= 21 && (i != j)) {
				mapp[i][j] = (i * j) / gcd(i, j);
				//	mapp[j][i] = (i * j) / find(i, j);
			} else if (abs(i - j) > 21) {
				mapp[i][j] = inf;
				mapp[j][i] = inf;
			}
		}
	}
	//初始化dis数组，dis数组是指从原点到当前点的距离
	for (int i = 1; i <= 2021; i++) {
		dis[i] = mapp[1][i];
	}
	book[1] = 1;
	int u;
	//dijkstra算法部分
	for (int i = 1; i <= 2021; i++) {
		int minn = inf;
		for (int j = 1; j <= 2021; j++) { //找离原点最近的点
			if (dis[j] < minn && book[j] == 0) {
				minn = dis[j];
				u = j;
			}
		}
		book[u] = 1;
		for (int v = 1; v <= 2021; v++) {
			if (mapp[u][v] < inf && book[v] == 0) {
				if (dis[v] > dis[u] + mapp[u][v]) {
					dis[v] = dis[u] + mapp[u][v];
				}
			}
		}
	}
	cout << dis[2021] << endl;
}

答案：10266837

试题F：时间显示

思路：编程题的签到题，直接做

#include
using namespace std;
int main()
{
	long long int n;
	cin>>n;
	n=n/1000;//毫秒->秒 
	int h=n/60/60%24;//小时 
	int m=n/60%60;//分 
	int s=n%60;//秒 
	printf("%02d:%02d:%02d",h,m,s);	//注意补0 
	return 0; 
}

试题G

dp/bfs 暂时空着，以后来补

试题H：杨辉三角形

根据递推公式，暴力枚举前2000行，得不了全分

#include
using namespace std;
int a[2001][2001];
int N;
int main() {
	cin >> N;
	for (int i = 0; i <= 2000; i++) {
		for (int j = 0; j <= 2000; j++) {
			a[i][j] = 0; //数组全部初始化为0
		}
	}
	a[0][0] = 1;
	for (int i = 0; i <= 2000; i++) {
		a[i][0] = 1;
	}
	a[1][0] = 1;
	a[1][1] = 1;
	int flag = 0;
	int index1 = 0;
	int index2 = 0;
	int i, j;
	for ( i = 2; i <= 2000; i++) {
		for ( j = 1; j <= i; j++) {
			a[i][j] = a[i - 1][j] + a[i - 1][j - 1];
			if (a[i][j] == N) {
				index1 = i;
				index2 = j;
				flag = 1;
				break;
			}
		}
		if (flag == 1) {
			break;
		}
	}
	int sum = 0;
	for (int i = 1; i <= index1; i++) {
		sum += i;
	}
	sum += index2;
	cout << sum + 1 << endl;
}

试题I：双向排序

直接sort了，应该就能过前几个样例

#include
using namespace std;
int a[100000+10];
int main()
{
	int n,m;
	int p,q;
	cin>>n>>m;
	for(int i=0;i<=100000;i++)
	{
		a[i]=i+1;
	}
	while(m--)
	{
		cin>>p>>q;
		if(p==0)//a1,a2....aqi降序排列 
		{
			sort(a,a+q,greater<int>());
		}
		else if(p==1)
		{
			sort(a+q-1,a+n);
		}
	}
	for(int i=0;i<n;i++)
	{
		cout<<a[i]<<" ";
	}
	return 0;
}

试题F：括号序列

放弃,if骗分