Day 1
蓝桥杯模拟赛 4
[蓝桥杯 2022 省 B] 刷题统计
思路：统计有多少整周，再统计最后一周的天数
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int N=1e5+10,INF=1e9,M=1e5+10;
int main(){
cin.tie(0),cout.tie(0);
ll a,b,n,ans=0;
cin>>a>>b>>n;
ans+=(n/(5*a+2*b)*7);
n%=(5*a+2*b);
if(n!=0){
int t=n/a;
if(t>5){
ans+=5;
n-=(a*5);
ans+=(n/b);
if(n%b)ans++;
}
else{
ans+=t;
if(n%a)ans++;
}
}
cout<<ans;
return 0;
}
View Code
[蓝桥杯 2022 国 B] 齿轮
思路：由公式v=wr，得到最左边的半径是最右边半径的q倍；i从1到最大半径/q枚举r数组中是否存在i*q；或者求出r中所有存在的倍数，将r从小到大排序，ri的约数，若在r数组中存在，则存下其倍数
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int N=2e5+5;
int n,q,r[N],t;
bool a[N];
int main(){
cin.tie(0),cout.tie(0);
cin>>n>>t;
int ma=0;
for(int i=1;i<=n;++i){
cin>>r[i];a[r[i]]=true;
ma=max(r[i],ma);
}
while(t--){
cin>>q;
bool ok=false;
for(int i=1;i<=ma/q;++i){
if(a[i]&&a[i*q]){
ok=true;
break;
}
}
if(ok)cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
}
View Code
[蓝桥杯 2022 省 A] 求和
思路：求所有ai乘上a[i+1,...,n]的和
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int N=2e5+10,INF=1e9,M=1e5+10;
ll n,a[N],s[N];
int main(){
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i];
s[i]=s[i-1]+a[i];
}
ll ans=0;
for(int i=1;i<n;++i){
ll b=a[i]*(s[n]-s[i]);
ans+=b;
}
cout<<ans;
return 0;
}
View Code
[蓝桥杯 2022 省 B] 修建灌木
思路：最高高度为修剪一个轮回的长度
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int N=2e5+10,INF=1e9,M=1e5+10;
int n;
int main(){
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;++i){
if(i<=n/2){
cout<<(n-i)*2<<'\n';
}
else{
cout<<(i-1)*2<<'\n';
}
}
return 0;
}
View Code
[蓝桥杯 2022 省 B] 李白打酒加强版
思路：dp f[i,j,k]： 状态表示：所有遇花i次，到店j次，酒k斗的种类 状态计算：1.到店，=f[i,j-1,k/2] 2.遇花，=f[i-1,j,k+1] 初始化：f[i,j,k]=0，f[0,0,2]=1
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int N=110,M=1e9+7;
int n,m,f[N][N][N];
int main(){
cin.tie(0),cout.tie(0);
cin>>m>>n;
for(int i=0;i<=n;++i){
for(int j=0;j<=m;++j){
for(int k=0;k<N;++k){
if(i==0&&j==0&&k==2)
f[i][j][k]=1;
if(i==0&&j==0)continue;
if(i>0)
f[i][j][k]=(f[i][j][k]+f[i-1][j][k+1])%M;
if(j>0&&k%2==0)
f[i][j][k]=(f[i][j][k]+f[i][j-1][k/2])%M;
}
}
}
cout<<f[n-1][m][1];
return 0;
}
View Code
[蓝桥杯 2022 国 C] 斐波那契数组
思路：斐波那契数组都满足a0=a1，且an=an-1+an-2，若数组不同，它们都呈倍数关系，求出前n项斐波那契数组，记录次数最多的倍数，可使修改次数最小
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int N=1e5+10,INF=1e9,M=1e6+10;
ll n,a[M],b[N];
int main(){
cin.tie(0),cout.tie(0);
cin>>n;
b[1]=b[2]=1;
for(int i=3;i<=n;++i){
b[i]=b[i-1]+b[i-2];
}
ll ans=0,x,ma=0;
for(int i=1;i<=n;++i){
cin>>x;
ma=max(ma,x);
if(x%b[i]==0)
a[x/b[i]]++;
}
for(int i=1;i<=ma;++i){
ans=max(ans,a[i]);
}
cout<<n-ans;
return 0;
}
View Code
[蓝桥杯 2022 省 A] 数的拆分
思路：引理：如果能把一个数表示为x1y1*x2y2(y1,y2>=2) 的形式，那么一定可以表示为 u2⋅v3 的形式。
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int N=4010;
int prime[N],tot;
bool not_prime[N];
void init(int n){
for(int i=2;i<=n;++i)
if(!not_prime[i]){
prime[++tot]=i;
for(int j=i+i;j<=n;j+=i)not_prime[j]=true;
}
}
bool check(ll x)
{
ll y = pow(x, 0.5);
if(y * y == x || (y + 1) * (y + 1) == x)
return true;
y = pow(x, 1.0 / 3);
if(y * y * y == x || (y + 1) * (y + 1) * (y + 1) == x || (y + 2) * (y + 2) * (y + 2) == x)
return true;
return false;
}
int main(){
cin.tie(0),cout.tie(0);
init(4000);
int t;
cin>>t;
while(t--){
ll x;
cin>>x;
if(check(x)){
cout<<"yes\n";
continue;
}
bool ok=true;
for(int i=1;i<=tot;++i){
if(x%prime[i]==0){
int cnt=0;
while(x%prime[i]==0){
cnt++;x/=prime[i];
}
if(cnt==1){
ok=false;
break;
}
}
}
if(ok&&check(x)){
cout<<"yes\n";
}
else cout<<"no\n";
}
return 0;
}
View Code
[蓝桥杯 2022 国 B] 卡牌
思路：将每种卡牌按卡牌数从小到大排序，每次增加前i种的卡牌，加到与i+1种卡牌数目相同，直到m减到小于i时加不了了，当加到第n种卡牌时，加m/n副牌
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int N=2e5+5;
ll n,m,a[N],b[N];
int main(){
cin.tie(0),cout.tie(0);
cin>>n>>m;
ll mma=1e9;
for(int i=1;i<=n;++i)cin>>a[i];
for(int i=1;i<=n;++i){
cin>>b[i];
mma=min(mma,a[i]+b[i]);
}
ll ans=0;
sort(a+1,a+n+1);
for(int i=1;i<=n;++i){
if(i==n){
ans+=m/n;
break;
}
ll t=a[i+1]-a[i];
if(m>=i&&t!=0){
ans=a[i]+min(t,m/i);
m=m-min(t*i,m/i*i);
}
if(m<i||ans>=mma)break;
}
cout<<min(ans,mma);
return 0;
}
View Code
标签：typedef,int,ll,cin,long,tie,week7 From： https://www.cnblogs.com/bible-/p/17117433.html