第十二届蓝桥杯大赛软件赛省赛C/C++ 大学 B 组
文章目录
- 第十二届蓝桥杯大赛软件赛省赛C/C++ 大学 B 组
- 1、空间
- 2、卡片
- 3、直线
- 4、货物摆放
- 5、路径
- 6、时间显示
- 7、砝码称重
- 8、杨辉三角形
- 9、双向排序
- 10、括号序列
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、括号序列
这题没看懂。。。
