笔触狂放9

这个屌丝很懒，什么也没留下！

热门标签

2021蓝桥杯省赛b组c/c++（蓝桥杯备战）_蓝桥杯省赛2021

作者：笔触狂放9 | 2024-08-22 23:40:58

踩

蓝桥杯省赛2021

今天是2023.4.5号，距离蓝桥杯还有3天，自己就刷了两套真题，刷题的过程中还有好多不会的，真的哭了，感觉第一次蓝桥杯没有准备好，寒假也荒废了，算法也学的好慢。题目感觉好多都没有思路。我感觉还是自己总结的少了，所以最近开始写起了博客，来总结一下，顺便记录一下自己的刷题记录。好了，不说闲话了，开始正题。

引用：蓝桥杯——2021第十二届C/C++真题[省赛][B组]_蓝桥杯c++历年真题_接受平凡努力出众的博客-CSDN博客

【蓝桥杯真题】2021年蓝桥杯省赛B组题目解析+代码（C/C++）_蓝桥杯2021年省赛b组_我的程序跑快快的博客-CSDN博客

A：空间：

在这里插入图片描述

基础知识：1GB=1024MB，1MB=1024KB，1KB=1024字节，1字节=8位

所以答案为256*1024*1024/4=67108864

B:卡片

在这里插入图片描述

思路：开一个数组，将a0,a1到a9赋值为2021，然后遍历数组+分离数字即可，但要注意题意：问的是可以拼到哪个数，不是不能拼成那个数。然而我就错了..

代码如下：


#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#include<deque>
#include<vector>
#include<map>
#include<set>
#include <utility>
using namespace std;
typedef  long  long ll ;
#define pii pair<int,int>
const int inf = 0x3f3f3f3f;
inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}
void print(__int128 num) {
	if(num) {
		print(num/10);
		putchar(num%10+'0');
	}
}
int a[10]={2021,2021,2021,2021,2021,2021,2021,2021,2021};
int flag=0;
int main(){
	for(int i=1;i<=10000;i++){
		int n=i;
		while(n!=0){
			if(a[n%10]>0){
				a[n%10]--;
				n=n/10;
			}else{
				flag=0;
				break;
			}
		}
		if(flag==1){
			printf("%d\n",i);
			break;
		}
	}
 
 
	return 0;
}

C:直线（别人图）：

在这里插入图片描述

思路：直线有多种表示方法：如Ax+By+C=0,或者y=kx+b,用set存储即可;但需要注意x1==x2或者y1==y2的情况，这两种情况单独考虑即可。

采用Ax+By+C=0,一定要记得去除最小公因数，不然答案会多，本人就是忘记了..代码如下：


#include<iostream>
#include<set>
using namespace std;
typedef pair<double, double> PII;
typedef pair<PII, double> PIII;
set<PIII> ss;
int gcd(int a, int b)
{
	if (b == 0) return a;
	return gcd(b, a % b);
}
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 && y1 != y2)
					{
						double a = x2 - x1;
						double b = y1 - y2;
						double c = y2 * x1 - x2 * y1;
						double m = gcd(gcd(a, b), c);//一定要记得除a,b,c的最小共因数，不然答案会多
						ss.insert({ { a / m,b / m }, c / m });
 
						//ss.insert(a);
					}
				}
			}
		}
	}
	cout << ss.size() + 20 + 21;
	return 0;
}

如果采用y=kx+b方法在运算的过程中很有可能会掉精度，所以不推荐使用。

D ：货物摆放在这里插入图片描述

本题可以使用暴力，但是纯暴力是过不去的，程序运行半天也没出结果，但暴力经过优化之后就可以过了

暴力思路：将n分解为a,b,c，设a<=b<=c然后就可以在循环方面做优化了：

代码如下：


#include<iostream>
using namespace std;
#define n 2021041820210418
//n=a*b*c
typedef long long ll;
int ans = 0;
int main()
{
	for (ll a = 1; a * a * a <= n; a++)//保证a<=b<=c;
	{
		if (n % a == 0)
		{
			for (ll b = a; a * b * b <= n; b++)
			{
				if (n / a % b == 0)
				{
					ll c = n / a / b;
					if (a == b && a == c){
							ans=ans+1;
							continue;
					}
					else if (a == b || a == c || c == b) {
						ans += 3;
						continue;
					}
					else {
						ans += 6;
						continue;
					}
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}

其他思路：如果不考虑暴力的话，可以采用数学的方法，即质因数分解，质因数分解的代码如下：


#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#include<deque>
#include<vector>
#include<map>
#include<set>
#include <utility>
using namespace std;
typedef  long  long ll ;
#define pii pair<int,int>
const int inf = 0x3f3f3f3f;
inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}
void print(__int128 num) {
	if(num) {
		print(num/10);
		putchar(num%10+'0');
	}
}
ll n=2021041820210418;
int main(){
	//质因数分解
	for(ll i=2;i<=n;i++){
		if(n%i==0){
			printf("%lld ",i);
			n=n/i;
			i=1;
		}
	}
 
 
	return 0;
}

将n分解得到2 3 3 3 17 131 2857 5882353；即n=2*3^3*17*131*2857*5882353

先考虑2，17，131，2857，5882353这5个数，一共三个空，每个数有三种可能：即3^5

再来考虑三个3，可以枚举每一个三的方法：

有 3 0 0，0 3 0， 0 0 3， 2 1 0 ，2 0 1， 1 2 0， 0 2 1， 1 2 0， 2 1 0，1 1 1共十种

注意：还有1的情况，当某个空没有放数时，1就补充了。

所以一共有10*3^5方法

E: 在这里插入图片描述

思路：佛洛依德算法，虽然很慢，但简单，我不会，所以学了下：

代码如下：注意a[i][i]赋值为0！！！

i和j的最小公倍数为i*j/gcd(i,j);


#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#include<deque>
#include<vector>
#include<map>
#include<set>
#include <utility>
using namespace std;
typedef  long  long ll ;
#define pii pair<int,int>
const int inf = 0x3f3f3f3f;
inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}
void print(__int128 num) {
	if (num) {
		print(num / 10);
		putchar(num % 10 + '0');
	}
}
int gcd(int a, int b) {
	if (b == 0)return a;
	return gcd(b,a%b);
}
int a[2050][2050];
int main() {
	for (int i = 1; i <= 2021; i++) {
		for (int j = 1; j <= 2021; j++) {
			if (abs(i - j) > 21) {
				a[i][j] = a[j][i] = inf;
			} else {
				if (i == j) {
					a[i][j] = a[j][i] = 0;
				} else {
					a[i][j] = a[j][i] = i * j / gcd(i, j);
				}
			}
		}
	}
	for(int k=1;k<=2021;k++){
		for(int i=1;i<=2021;i++){
			for(int j=1;j<=2021;j++){				
					if(a[i][k]+a[k][j]<a[i][j]){
						a[i][j]=a[i][k]+a[k][j];
				}
			}
		}
	}
	printf("%d\n",a[2021][1]);
 
 
 
 
	return 0;
}

F：签到题直接跳过在这里插入图片描述

G：砝码称重在这里插入图片描述

在考场上很难想到状态转移方程，如果要骗分的话，可以使用搜索。搜索是干什么的？任何问题都可以有搜索解决！！如果没有思路就搜啊！代码如下，注意：打标记的时候一定要加上绝对值，因为左右两盘是等效的！！！


#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#include<deque>
#include<vector>
#include<map>
#include<set>
#include <utility>
using namespace std;
typedef  long  long ll ;
#define pii pair<int,int>
const int inf = 0x3f3f3f3f;
inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}
void print(__int128 num) {
	if (num) {
		print(num / 10);
		putchar(num % 10 + '0');
	}
}
int n;
int a[105];
int vis[100005];
void dfs(int s, int i) {
	if (i == n + 1) {
	//	if (s > 0) {
	//		vis[s] = 1;
	//	}
		return ;
	}
	vis[abs(s)]=1;//注意加绝对值，s是由上一个dfs来的所以可能为负数！！
	vis[abs(s+a[i])]=1;
	vis[abs(s-a[i])]=1;
	dfs(s + a[i], i + 1);
	dfs(s, i + 1);
	dfs(s - a[i], i + 1);
}
int main() {
	scanf("%d", &n);
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		sum = sum + a[i];
	}
	dfs(0, 1);
	int ans = 0;
	for (int i = 1; i <= sum; i++) {
		if (vis[i] == 1) {
			ans++;
		}
	}
	printf("%d\n", ans);
	
	return 0;
}

正确的思路就是dp的背包问题了，yan式dp分析法如下

1，设sum为n件物品的总重量，如果采用就地滚动的方法，需要两次就地滚动，但要注意sum循环的方向，代码如下\


#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#include<deque>
#include<vector>
#include<map>
#include<set>
#include <utility>
using namespace std;
typedef  long  long ll ;
#define pii pair<int,int>
const int inf = 0x3f3f3f3f;
inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}
void print(__int128 num) {
	if (num) {
		print(num / 10);
		putchar(num % 10 + '0');
	}
}
ll ans = 0;
int dp[100105];
int vis[100105];
int a[105];
int main() {
	int n;
	scanf("%d", &n);
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		sum = sum + a[i];
	}
	dp[0] = 1;
	vis[0]=1;
	for (int i = 1; i <= n; i++) {
		for (int j = sum; j >= a[i]; j--) {
			dp[j] = dp[j - a[i]] | dp[j];//dp[j-a[i]等效dp[i-1][j-a[i]];
			if (dp[j] == 1) {
				vis[j] = 1;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j =0;j<=sum; j++) {
			dp[j] = dp[j] | dp[j + a[i]];//dp[j+a[i]]等效于dp[i-1][j+a[i]];
			if (dp[j] == 1 ) {
				vis[j] = 1;
			}
		}
	}
	for(int i=1;i<=sum;i++){
		if(vis[i]){
			ans++;
		}
	}
	printf("%lld\n", ans);
 
 
	return 0;
}

2.如果用dp[i][j]=dp[i-1][j] | dp[i-1][j+a[i]] |dp[i-1][j-a[i]]时，要注意j-a[i]可能为负数，但左右两边又是等效的，所以dp[i][j]=dp[i-1][j] | dp[i-1][j+a[i]] |dp[i-1][abs(j-a[i])],这题跟登录—专业IT笔试面试备考平台_牛客网非常相似

代码如下


#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#include<deque>
#include<vector>
#include<map>
#include<set>
#include <utility>
using namespace std;
typedef  long  long ll ;
#define pii pair<int,int>
const int inf = 0x3f3f3f3f;
inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}
void print(__int128 num) {
	if (num) {
		print(num / 10);
		putchar(num % 10 + '0');
	}
}
ll ans = 0;
int dp[105][100105];//前i个数重量为j;
int a[105];
int main() {
	int n;
	scanf("%d", &n);
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		sum = sum + a[i];
	}
	dp[0][0] = 1;
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= sum; j++) {
			dp[i][j]=dp[i-1][j]|dp[i-1][j+a[i]]|dp[i-1][abs(j-a[i])];		
		}
	}
 
	for (int j = 1; j <= sum; j++) {
		if (dp[n][j])ans++;
	}
	printf("%d\n", ans);
	return 0;
}

H：在这里插入图片描述

我没啥思路，只能暴力骗分，过了5个样例，骗了9分，开心，代码如下，但我在测试的过程中，如果把dp数组开到dp[3000][3000]就过了2个样例，难道还跟数组的大小有关？不明白..


#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#include<deque>
#include<vector>
#include<map>
#include<set>
#include <utility>
using namespace std;
typedef  long  long ll ;
#define pii pair<int,int>
const int inf = 0x3f3f3f3f;
inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}
void print(__int128 num) {
	if(num) {
		print(num/10);
		putchar(num%10+'0');
	}
}
ll dp[1020][1002];
int main(){
	int n;
	scanf("%d",&n);
	if(n==1){
		printf("1\n");
		return 0;
	}
	for(int i=1;i<=1000;i++){
		dp[i][1]=dp[i][i]=1;
	}
	for(int i=3;i<=1000;i++){
		for(int j=2;j<=i-1;j++){
			dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
			if(dp[i][j]==n){
				cout<<(1+i-1)*(i-1)/2+j;
				return 0; 	
			}
		}
	}
	return 0;
}

正确思路：蓝桥杯——2021第十二届C/C++真题[省赛][B组]_蓝桥杯c++历年真题_接受平凡努力出众的博客-CSDN博客

自己写的代码


#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#include<deque>
#include<vector>
#include<map>
#include<set>
#include <utility>
using namespace std;
typedef  long  long ll ;
#define pii pair<int,int>
const int inf = 0x3f3f3f3f;
inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}
void print(__int128 num) {
	if(num) {
		print(num/10);
		putchar(num%10+'0');
	}
}
ll n;
ll calc(ll a,ll b){
	ll ans=1;
	for(ll i=a,j=1;j<=b;i--,j++){
		ans=ans*i/j;
		if(ans>n)return ans;
	}
	return ans;
}
bool check(int k){
	ll left=2*k;
	ll right=max(left,n);
	while(left<=right){
		ll mid=(left+right)/2;
		if(calc(mid,k)>=n){
			right=mid-1;
		}else{
			left=mid+1;
		}	
	}
	if(calc(right+1,k)==n){
		cout<<(right+2)*(right+1)/2+k+1;
		return 1;
	}else{
		return 0;
	}
}
int main(){
	cin>>n;
	for(int i=16;i>=0;i--){
		if(check(i)){
			break;
		}
	}
	return 0;
}

最后I和J题，实在不想做了，通过暴力骗点分吧。

总结：考察的算法：dp，二分，搜索，最短路，数论，图论等等

题目感觉不是很难（事后诸葛亮，考试时蒙圈），但考察的很细节啊

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】