第十二届蓝桥杯大赛软件赛省赛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 求xfor(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、括号序列

这题没看懂。。。