2021年第十二屆藍橋杯省賽B組C/C++題解
這次藍橋杯總的來說要比前幾年會難一些，因為大多數涉及到思維，所以普遍分低，希望今年自己還能有省一，
這里是我自己寫的一些題解，答案核對后一般是正確的給大家講講我的思路，
沒什么好說的：
1MB=1024KB 1KB=1024B 32位bit是4位元組
所以答案是256* 1024 *1024 / 4 =67108864
答案：67108864
計算每個數字的使用情況，最后不夠的時候停止，此時是第一個不能拼出的使用要減去一個
#include<iostream>
using namespace std;
int main(){
int cnt[10];
for(int i=0;i<10;i++)
cnt[i]=2021;
for(int i=1;;i++){
int t=i;
while(t){
int a=t%10;
if(cnt[a]>0)cnt[a]--;
else break;
t/=10;
}
if(t){
cout<<i;
break;
}
}
return 0;
}
//3181
答案：3181
本質不同，計算他的y=kx+b中的k和b的值，然后排一下重即可
#include<bits/stdc++.h>
using namespace std;
typedef pair<double,double> pdd;
set<pdd> m;//存斜率k和截距b
const int N=30;
pdd point[N*N];
#define x first
#define y second
int main(){
int cnt=0;
for(int i=0;i<20;i++){
for(int j=0;j<21;j++){
point[cnt].x=i;
point[cnt].y=j;
cnt++;
}
}
int ans=20+21;
for(int i=0;i<cnt;i++){
for(int j=0;j<cnt;j++){
if(point[i].x==point[j].x||point[i].y==point[j].y)
continue;
double k=(point[j].y-point[i].y)/(point[j].x-point[i].x);
double b=(point[j].x*point[i].y-point[j].y*point[i].x)/(point[j].x-point[i].x);
m.insert({k,b});
}
}
for(auto it=m.begin();it!=m.end();it++)
ans++;
cout<<ans<<endl;
}
//40257
答案：40257
分解一下n的所有因數然后排序，最后組合所有數判斷是否能組成n即可
#include<iostream>
using namespace std;
const int N=1e3+7;
typedef long long ll;
ll s[N];
int main(){
ll n=2021041820210418;
ll cnt=0;
ll res=0;
for(int i=1;i<=n/i;i++)
if(n%i==0){
s[cnt++]=i;
s[cnt++]=n/i;
}
for(int i=0;i<cnt;i++)
for(int j=0;j<cnt;j++)
for(int k=0;k<cnt;k++)
if(s[i]*s[j]*s[k]==n)
res++;
cout<<res;
return 0;
}
//2430
答案：2430
很簡單的最短路，最多8e8的資料量，暴力一下就好了
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
//#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define _for(i,a,b) for(int i=a,i<b;i++)
#define x first
#define y second
#define pb push_back
#define lowit(x) (x&-x)
#define io ios::sync_with_stdio(false); \
cin.tie(nullptr); \
cout.tie(nullptr);
const int N=3000;
typedef long long ll;
typedef pair<int,int> PII;
ll lu[N][N];
ll _gcd(ll a,ll b){
return b==0?a:_gcd(b,a%b);
}
void solve(){
memset(lu,0x3f3f3f3f,sizeof(lu));
for(ll i=1;i<=2021;i++)
for(ll j=i+1;j<=i+21;j++)
lu[i][j]=lu[j][i]=i*j/_gcd(i,j);
//cout<<i*j/_gcd(i,j)<<" ";
for(int i=1;i<=2021;i++)
for(int j=i+1;j<=2021;j++)
for(int k=i+1;k<j;k++)
lu[i][j]=min(lu[i][j],lu[i][k]+lu[k][j]);
cout<<lu[1][2021];
}
int main(){
io;
int T=1;
//T=read();
while(T--){
solve();
}
return 0;
}
//10266837
答案：10266837
注意幾點，補前導0，這里還要開到整形的long long不然會爆，我考的時候沒看到，還測驗了一下會不會超過1e18如果超過可以開__int128_t或者手寫高精度
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
int main(){
ll cnt;
cin>>cnt;
cnt/=1000;
cnt%=86400;
printf("%02d:%02d:%02d",cnt/3600,cnt/60%60,cnt%60);
return 0;
}
這題我們要判斷可以得到的數，如果暴力配對太麻煩了，所以我們采用背包來壓縮狀態，注意他一個砝碼只能用一次又要前后都同時改變，所以得開二維陣列不相互影響，但是空間給的不夠全開，所以我們用二維的滾動陣列優化一下即可
#include<iostream>
using namespace std;
#define io ios::sync_with_stdio(false); \
cin.tie(nullptr); \
cout.tie(nullptr);
const int M=1e6+7;
typedef long long ll;
bool dp[2][M];
int main(){
io;
int n,t,sum=0,res=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>t;
sum+=t;
for(int j=1;j<=sum;j++){
if(j<=t)
dp[i&1][j]=dp[!(i&1)][j+t]||dp[!(i&1)][j]||dp[!(i&1)][t-j];
else
dp[i&1][j]=dp[!(i&1)][j+t]||dp[!(i&1)][j-t]||dp[!(i&1)][j];
dp[i&1][t]=1;
}
}
for(int i=1;i<=sum;i++)
if(dp[n&1][i]){
res++;
}
cout<<res;
return 0;
}
這題有幾個槽點，資料比較離譜，而且好像沒啥規律，有想過二分但是最后得不出來最后答案所以暴力加剪枝出來了，時間復雜度sqrt(n)用滾動資料可以不用開額外空間
#include<iostream>
using namespace std;
#define endl "\n"
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n,res=1;
cin>>n;
for(int i=1;;i++){
ll j,cnt=1,flag=0;
if((i*i-1)/2>n){res=n*(n+1)/2+2;break;}
if(cnt==n)break;
for(j=0;j<=(i+1)/2;j++){
if(cnt>n)break;
else if(cnt==n){res+=j+1;flag=1;break;}
cnt=cnt*(i-j)/(j+1);
}
if(flag)
break;
else
res+=i+1;
}
cout<<res;
return 0;
}
這題用后綴的思想倒著排，然后只有中間的數是需要我們配對的有一個數學規律，但是比賽懶的想了，用的桶排能過60%
#include<iostream>
using namespace std;
const int N=1e5+7;
bool p[N];
int s[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
s[i]=i;
while(m--){
int k,q;
//cin>>k>>q;
k=rand()%2;q=rand()%n+1;
if(k){
for(int i=1;i<=q;i++)
p[s[i]]=0;
for(int i=1,j=n;i<=q;i++)
if(!p[j--])
s[i]=j+1;
}
else{
for(int i=q;i<=n;i++)
p[s[i]]=0;
for(int i=q,j=1;i<=n;i++)
if(!p[j++])
s[i]=j-1;
}
}
for(int i=1;i<=n;i++)
cout<<s[i]<<" ";
}
比賽的時候就想到是卡特蘭數，但是配對的有點問題，所以不想繼續想了，隨便暴力了交了一發，代碼太丑不想發，之后有時間補，
總結：這次藍橋杯非常有趣，雖然大家都說傻逼，但是還是非常鍛煉思維的，藍橋杯這樣發展下去就可以脫離暴力杯的業界口碑了，需要繼續努力，我們也要從藍橋杯逐漸成為acmer，加油加油加油，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/278550.html
標籤：其他