第十二届蓝桥杯大赛软件赛省赛 C/C++ 大学 B 组

1、空间

1MB = 1024KB
1KB = 1024byte
1byte=8bit
// cout<<"256*1024*1024/4"; // 记住 1024 即可

2、卡片

往简单的讲就是一个排列组合的问题，因为可以选自身，所以 n 张卡片最多有 n + C2n 中方案。 我们可以把它想象成一个开口向上的二次函数然后根据 x 去求最小的 y 值。

#include<iostream>
#define ll long long
using namespace std;
ll n,k;
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	// (x^2+x)/2 = n
	// 2n = x^2+x
	// x^2+x-2n=0 求x
	for(ll i=1;i<=1e9;i++){
		if(i*i+i>=2*n){
			cout<<i;
			return 0;
		}
	}
	return 0;
}

3、直线

#include<iostream>
#include<set>
#define pii pair<double,double>
#define ll long long
using namespace std;
int x=20,y=21;
set<pii> st;
void check(int x1,int y1,int x2,int y2){
	if(x1==x2||y1==y2)return;
	double k=(y2-y1)*1.0/(x2-x1);
	// y1=k*x1+b y2=k*x2+b
	// k=(y2-y1)/(x2-x1)替代即可算出b=(x2*y1-x1*y2)/(x2-x1)
	double b=(x2*y1-x1*y2)*1.0/(x2-x1);
	st.insert({k,b});
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	for(int i=0;i<y;i++){
		for(int j=0;j<x;j++){
			for(int k=0;k<y;k++){
				for(int t=0;t<x;t++){
					check(j,i,t,k);
				}
			}
		}
	}
	cout<<st.size()+x+y;
	return 0;
}

4、货物摆放

先去找到这个数的所有因子，再去枚举这些因可能成为的结果。最后计算这些结果。

#include<iostream>
#include<cmath>
#define ll long long
using namespace std;
ll n = 2021041820210418;
ll a[50001],cnt=0;
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	for(int i=1;i<=sqrt(n);i++){
		if(n%i==0){
			a[++cnt]=i;
			if(i*i!=n)a[++cnt]=n/i;
		}
	}
	int res=0;
	for(int l=1;l<=cnt;l++)
		for(int w=1;w<=cnt;w++)
			for(int h=1;h<=cnt;h++)
				if(a[l]*a[w]*a[h]==n)res++;
	cout<<res;
	return 0;
}

5、路径

#include<iostream>
#define ll long long
using namespace std;
const int n = 2025;
//ll d[n][n];
ll INF = 1e17;
// 循环遍历超时，辗转相除法高效
int gcd(int a,int b){
	if(a%b==0)return b;
	return gcd(b,a%b);
}
int lcm(int a, int b){return a / gcd(a, b) * b;}
//void floyd(){
//	for(int k=1;k<=n;k++)
//		for(int i=1;i<=n;i++)
//		 	for(int j=1;j<=n;j++)
//		 		if(d[i][k]!=INF&&d[k][j]!=INF)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
//}

int d[n];
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	for(int i=0;i<n;i++)d[i]=INF;
	d[1]=0;
	for(int i=1;i<n;i++)
		for(int j=i+1;j<n&&j-i<=21;j++){
			d[j]=min(d[j],lcm(i,j)+d[i]);
		}
	cout<<d[2021];
	return 0;
}

6、时间显示

时间换算，思维创新。

#include<iostream>
#define ll long long
using namespace std;
ll n,h,m,s;
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	n=n/1000;//舍弃毫秒 1s = 1000ms
	n=n%(24*60*60);// 一天24小时
	h=n/3600;
	m=(n-h*3600)/60;
	s=n-3600*h-60*m;
	if(h<10){
		cout<<"0"<<h<<":";
	}else{
		cout<<h<<":";
	}
	if(m<10){
		cout<<"0"<<m<<":";
	}else{
		cout<<m<<":";
	}
	if(s<10){
		cout<<"0"<<s;
	}else{
		cout<<s;
	}
	return 0;
}

7、砝码称重

#include<iostream>
#include<queue>
#include<cmath>
#include<cstring>
using namespace std;
const int N = 1e5+10;
queue<int> q;
int n,w,cnt;
bool ans[N];
int main(){
	memset(ans,0,sizeof(ans));
	cin>>n;
	q.push(0);
	for(int i=0;i<n;i++){
		cin>>w;
		queue<int> tmp_q;
		while(!q.empty()){
			int x=q.front();
			q.pop();
			if(ans[x+w]==false){
				ans[x+w]=true;
				cnt++;
				tmp_q.push(x+w);
			}
			if(ans[abs(x-w)]==false){
				ans[abs(x-w)]=true;
				cnt++;
				tmp_q.push(abs(x-w));
			}
			tmp_q.push(x);
		}
		q=tmp_q;
	}
	cout << cnt-1;//为0的情况不要
	return 0;
}

8、杨辉三角形

只会写朴素算法，优化的算法，还没看懂。。。。。 这个只能过 40%。

#include<iostream>
#define ll long long
using namespace std;
const int N = 2e3+5;
int dp[N][N],n;
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	if(n==1){
		cout<<"1";return 0;
	}
	dp[1][1]=dp[2][1]=dp[2][2]=1;
	for(int i=3;i<N-1;i++){
		for(int j=1;j<=i;j++){
			if(j==1||j==i){
				dp[i][j]=1;
			}else{
				dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
			}
			if(dp[i][j]==n){
				// （a1+an)/2  a1=i,an=i-1,多出来的 + j
				cout<<i*(i-1)/2+j;
				return 0;
			}
		}
	}
	return 0;
}

9、双向排序

直接暴力截决。只能过 60%。

#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
int n,m;
vector<int> v;
bool cmp(int a,int b){
	return a>b;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)v.push_back(i);

	for(int i=1;i<=m;i++){
		int p,q;cin>>p>>q;
		if(p==0)sort(v.begin(),v.begin()+q,cmp);
		else sort(v.begin()+q-1,v.end());
	}

	for(const auto& x:v)cout<<x<<' ';
	return 0;
}

10、括号序列

这题没看懂。。。