【摘要】 第十二届蓝桥杯大赛C++ B组省赛题解
A 空间
8位二进制=1字节 1024字节=1KB 1024KB=1MB
25610241024*8/32=67108864
B 卡片
3181
#include<bits/stdc++.h>
using namespace std;
int a[10];
int main(){
for(int i=1;i<=100…
第十二届蓝桥杯大赛C++ B组省赛题解
A 空间
8位二进制=1字节
1024字节=1KB
1024KB=1MB
25610241024*8/32=67108864
B 卡片
3181
#include<bits/stdc++.h>
using namespace std;
int a[10];
int main(){
for(int i=1;i<=100000000;i++){
for(int j=0;j<=9;j++){ if(a[j]>=2021){ cout<<i-1<<endl; return 0; }
}
int n=i;
while(n){ a[n%10]++; n/=10;
}
}
}
C 直线
40257
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
vector<pair<double,double> >ve;
for(int i=0;i<20;i++){
for(int j=0;j<21;j++){ ve.push_back(pair<double,double>(i*1.0,j*1.0));
}
}
set<pair<double,double> > se;
double k,b;
for(int i=0;i<ve.size();i++){
for(int j=0;j<ve.size();j++){ if(ve[i].first==ve[j].first||ve[i].second==ve[j].second) continue; k=(ve[i].second-ve[j].second)/(ve[i].first-ve[j].first); b=(ve[j].first*ve[i].second-ve[j].second*ve[i].first)/(ve[j].first-ve[i].first); se.insert(pair<double,double>{k,b});
}
}
cout<<se.size()+20+21<<endl;
return 0;
}
D 货物摆放
2430
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n=2021041820210418;
ll a[2000];
int idx=0;
map<ll,ll> mp;
int main(){
for(ll i=1;i<=sqrt(n);i++){
if(n%i==0){ a[idx++]=i; mp[a[idx-1]]=1;
}
}
ll p=idx;
for(int i=0;i<p;i++){
if(n%a[i]==0){ if(mp[n/a[i]]==1) continue; a[idx++]=n/a[i];
}
}
ll ans=0;
for(int i=0;i<idx;i++){
for(int j=0;j<idx;j++){ for(int k=0;k<idx;k++){ if(a[i]*a[j]*a[k]==n){ //cout<<a[i]<<" "<<a[j]<<" "<<a[k]<<endl; ans++; } }
}
}
cout<<ans<<endl; //system("pause");
return 0;
}
E 路径
10266837
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll maps[2023][2023];
int gcd(int a,int b){
int k;
while(a%b){
k=b;
b=a%b;
a=k;
}
return b;
}
int main(){
memset(maps,0x3f3f3f3f,sizeof(maps));
for(int i=1;i<=2021;i++){
maps[i][i]=0;
for(int j=i+1;j<=i+21&&j<=2021;j++){ ll val=(i*j)/gcd(i,j); maps[i][j]=maps[j][i]=val;
}
}
for(int k=1;k<=2021;k++){
for(int i=1;i<=2021;i++){ for(int j=1;j<=2021;j++){ if(maps[i][j]>maps[i][k]+maps[k][j]){ maps[i][j]=maps[i][k]+maps[k][j]; } }
}
}
cout<<maps[1][2021]<<endl;
return 0;
}
F 时间显示
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=86400000;
int main(){
ll n;
cin>>n;
n%=mod;
n/=1000;
ll shi=0,fen=0,miao=0;
miao=n%60;
fen=(n/60)%60;
shi=(n/3600)%24;
//cout<<shi<<":"<<fen<<":"<<miao<<endl;
if(shi<10) cout<<0;
cout<<shi<<":";
if(fen<10) cout<<0;
cout<<fen<<":";
if(miao<10) cout<<0;
cout<<miao<<endl;
return 0;
}
G 砝码称重
50%写法（暴力去重）：
TLE了。
#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
int n;
int w[maxn];
int dp[maxn];
set<int> se;
set<int>::iterator it;
int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>w[i]; se.insert(w[1]); se.insert(0); se.insert(0-w[1]); for(int i=2;i<=n;i++){ vector<int> ve; for(it=se.begin();it!=se.end();it++){ ve.push_back(*it+w[i]); ve.push_back(*it-w[i]); } for(int i=0;i<ve.size();i++){ se.insert(ve[i]); } } int ans=0; for(it=se.begin();it!=se.end();it++){ if(*it<=0) continue; ans++; //cout<<*it<<endl; } cout<<ans; //system("pause"); return 0;
}
100%写法（背包）:
sum为计算的背包容量，第i个数正好是w[i]-0转移过来的，所以把dp[0][0]初始化成1，为了使每个重量进来时能把它自己标记成1。其它的，看递推式就懂了。
#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
const int N=2e5+10;
int n;
int w[maxn];
int dp[maxn][N];
int main(){ cin>>n; int sum=0; for(int i=1;i<=n;i++){ cin>>w[i]; sum+=w[i]; } dp[0][0]=1; for(int i=1;i<=n;i++){ for(int j=0;j<=sum;j++){ dp[i][j]=dp[i-1][j]||dp[i-1][j+w[i]]||dp[i-1][abs(j-w[i])]; } } int ans=0; for(int i=1;i<=sum;i++){ if(dp[n][i]) ans++; } cout<<ans; //system("pause"); return 0;
}
H 杨辉三角形
20%写法（假算法）：
#include<bits/stdc++.h>
using namespace std;
const int maxn=2000;
typedef long long ll;
ll a[maxn][maxn];
int ans[maxn];
int main(){
a[1][1]=1;
ans[1]=1;
int num=1;
for(int i=2;i<=10;i++){
num++;
for(int j=1;j<=num;j++){ a[i][j]=a[i-1][j]+a[i-1][j-1]; if(!ans[a[i][j]]) ans[a[i][j]]=((i-1)*(i))/2+j;
}
}
int n;
cin>>n;
cout<<ans[n]<<endl;
return 0;
}
30%写法（这个好像更假）：
简单说一下思路吧，首先是去找到第几行的第四个数出现比1e9大的数，确定行数，开始循环。
第一种情况是在循环的过程中找到了我们需要的n，我们就根据当前位置的i,j，前i-1行用求和公式表明前i行有多少个数，因为是差为1的等差数列，当前行+j表明当前行有多少个数，相加即为第一次出现n的第几个数。
通过观察我们还发现，第一列的数都是1，即C(0,n)，第二列的数都是n，即C(1,n)，第三行的数自然是C(2,n)，我们已知第四行的数一定比1e9大了，我们去找第三行的数是不是等于n，如果不是直接回到第二行，一定能找到一个n，然后通过之前的方法计算出这是第几个数。
（思路假）
#include<bits/stdc++.h>
using namespace std;
const int maxn=2021;
typedef long long ll;
ll a[maxn][maxn];
int main(){
ll n;
cin>>n;
a[1][1]=1;
int num=1;
for(int i=2;i<=2000;i++){
num++;
for(int j=1;j<=num;j++){ a[i][j]=a[i-1][j]+a[i-1][j-1]; //cout<<a[i][j]<<" "; if(a[i][j]==n){ cout<<((i-1)*(i))/2+j; return 0; }
}
//cout<<endl;
}
if((double)(n*(n-1))/2.0==(double)n){
cout<<n*(n+1)/2+3;
}else{
cout<<(n+1)*(n+2)/2+2;
return 0;
}
return 0;
}
100%做法（组合数的二分查找）：
菜死了菜死了菜死了！这是看y总视频%的，自己根本没想出来，只会暴力。
二分掌握的还是不熟练，有点小弯就卡死。
特判1的情况，1在第一次就出现，不用采用等差数列求和公式计算。
理解： 除了1特判，其它的均采用组合数解决，因为C(16,32) < 1e9 且C(17,34) > 1e9 ，所以在主函数的循环里，我们只遍历到第17行就行(0~16) 。32–>34 看的是斜行，第一行全是1，第二行是2,3,4…，第三行是6,10,15…根据斜行计算，从下往上，从外往里，去找。
（l，r 的意思见注释）当我们找到C(m,n)中这个n是多少，即它恰好在这一行，再往下答案就变大，再往上找不到，去遍历(16~1)倒序，找到与n相等的组合数 找到之后根据求和公式算出当前的数是第几个，最不济也会找到C(1,n)=n
#include<bits/stdc++.h>
using namespace std;
const int maxn=2000;
typedef long long ll;
int n;
ll cal(int a,int b){ ll res=1; for(int i=a,j=1;j<=b;i--,j++){ res=res*i/j; if(res>n) return res; } return res;
}
bool check(int k){ ll l=k*2,r=n; //l 因为每一行左半边与右半边相同，所以我们只要左半边，所以l=k*2 //C(m,n) m--k,n--l 所以最小l就是恰好在中间，如6恰好是C(2,4); //C(m,n) m--k,n--r 最大r就是恰好在最左边，如7恰好是C(1,7); while(l<r){ ll mid=l+r>>1; if(cal(mid,k)>=n) r=mid; else l=mid+1; } if(cal(r,k)!=n) return false; cout<<r*(r+1)/2+k+1<<endl; return true;
}
int main(){
cin>>n;
if(n==1){ cout<<1<<endl;return 0;
} for(int k=16;;k--){ if(check(k)) break; } //system("pause");
return 0;
}
I : 双向排序
50%做法（两个sort）：
会卡到n=5000,m=5000
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
int a[maxn];
int n,m;
int p,q;
bool cmp(int a,int b){ return a>b;
}
void output(){ for(int i=1;i<=n;i++){ cout<<a[i]<<" "; } cout<<endl;
}
int main(){
cin>>n>>m; for(int i=1;i<=n;i++){ a[i]=i; } while(m--){ cin>>p>>q; if(p){ sort(a+q,a+n+1); //output(); }else{ sort(a+1,a+q+1,cmp); //output(); } } for(int i=1;i<=n;i++){ cout<<a[i]<<" "; } //system("pause");
return 0;
}
100%做法（思维题）：
跟着y总的视频过了一遍。
(1) m次 分0和1 简化 维护成01相间的状态，因为如果二者状态相同，起点（或终点）相同，在较大区间的排序下，如果之前是一个更小的区间，那可以直接用这次取代；如果之前是更大的区间，那这次排序完全没有必要，因为之前的大区间已经保持有序，那当前的小区间一定是有序的，不需要再次排序。
(2) 对操作做成01相间的状态之后，就是要去把答案数组给维护出来。因为是栈的结构，栈底是最先入栈的情况。选择先从栈底开始操作，从最终的数开始向数组中填。栈空数组也就填完，输出即可。
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
const int maxn=1e5+10;
pi st[maxn];
int top;
int ans[maxn];
int n,m;
int p,q;
int main(){
scanf("%d%d",&n,&m); while(m--){ scanf("%d%d",&p,&q); if(!p){ while(top&&st[top].x==0) q=max(q,st[top--].y); while(top>=2&&st[top-1].y<=q) top-=2; st[++top]={0,q}; }else if(top){ while(top&&st[top].x==1) q=min(q,st[top--].y); while(top>=2&&st[top-1].y>=q) top-=2; st[++top]={1,q}; } } int k=n,l=1,r=n; for(int i=1;i<=top;i++){ if(st[i].x==0){ while(r>st[i].y&&l<=r) ans[r--]=k--; }else{ while(l<st[i].y&&l<=r) ans[l++]=k--; } if(l>r) break; } if(top%2){ while(l<=r) ans[l++]=k--; }else{ while(l<=r) ans[r--]=k--; } for(int i=1;i<=n;i++) printf("%d ",ans[i]); //system("pause");
return 0;
}
J 括号序列
留了一道，晚点写。DP永远是大爹。
文章来源: blog.csdn.net，作者：iuk11，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/iuk11/article/details/115904897
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/4d3cf227a85d7e79f5d6b4efb6bde3e8.jpg)
![[桜井宁宁] 爆乳奶牛少女cos写真-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/d40483e126fcf567894e89c65eaca655.jpg)
