阅读量:0
CF961（div2）
A. Diagonals（贪心）
题意：有n*n的棋盘，有k个筹码，将这些筹码放在棋盘上，对角线指i+j值相同的，求被占对角线的最少数目
分析:除了第n条对角线只有一条，从1到n-1都有两条
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; void sol(){ int n,k;cin>>n>>k;ll ans=0; if(k==0){ cout<<"0"<<endl; return; } else{ k-=n;ans++; if(k<=0){ cout<<"1"<<endl;return; } else{ for(int i=n-1;i>=1;i--){ ans++; k-=i; if(k<=0)break; ans++; k-=i; if(k<=0)break; } } } cout<<ans<<endl; } int main(){ int t;cin>>t; while(t--)sol(); return 0; } B1. Bouquet (Easy Version)（前缀和，贪心）
题意：k个花瓣花费k枚硬币，想要花束中任何两朵的花瓣数之差不能超过1.先有m枚硬币。能组合的花瓣总数最多是多少
分析：先将花从小到大放好，遍历花瓣，用k找到符合条件的最小的花瓣数，每次遍历，用前缀和求出两朵花之间的最大值。
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; void sol(){ int n;cin>>n; ll m;cin>>m; ll a[n+10],sum[n+10]; for(int i=1;i<=n;i++)cin>>a[i]; sort(a+1,a+n+1); for(int i=1;i<=n;i++){ sum[i]=sum[i-1]+a[i]; }int k=1;ll ans=0; for(int i=1;i<=n;i++){ while(a[i]!=a[k]&&a[i]!=a[k]+1){ k++; } while(sum[i]-sum[k-1]>m){ k++; } ans=max(ans,sum[i]-sum[k-1]); if(ans==m)break; } cout<<ans<<endl; } int main(){ int t;cin>>t; while(t--)sol(); return 0; } B2. Bouquet (Hard Version)（贪心，数学）
题意：与b1不同的是每种花瓣都有相应数量，数据大。 分析：判断相邻两个花瓣是否相差1，先买第一束，如果还有省钱就再买第二束，如果两束没有全买，判断第一束的花是否可以与第二束里的花交换，使得答案越大 代码：
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ll; const int N=2e5+10; struct A{ int x; ll y; }a[N]; bool cmp(A xx,A yy){ return xx.x<yy.x; } void sol(){ int n;cin>>n; ll m;cin>>m; for(int i=1;i<=n;i++)cin>>a[i].x; for(int i=1;i<=n;i++)cin>>a[i].y; sort(a+1,a+n+1,cmp); ll ans=0,sum=0; for(int i=1;i<=n;i++){ ll d=min(a[i].y,m/a[i].x); sum=a[i].x*d; ans=max(ans,sum); } for(int i=1;i<n;i++){ if(a[i+1].x==a[i].x+1){ ll t1=min(a[i].y,m/a[i].x);//第一束花的数量 ll cm=m-t1*a[i].x;//剩下的钱 ll t2=min(a[i+1].y,cm/(a[i+1].x));//第二束花的数量 sum=t1*a[i].x+t2*a[i+1].x; ll s=min(m-sum,min(a[i+1].y-t2,t1)); ll q=sum+s; ans=max(q,ans); } } cout<<ans<<endl; } int main(){ int t;cin>>t; while(t--)sol(); return 0; } C. Squaring（数学）
题意：有一个数组，想让这个数组变成非递减的，可以进行以下操作：ai替换成ai²，至少需要多少次操作 分析：我们可以对ai-1进行负操作，对ai进行正操作，再用前缀和求出操作次数即可。 eg.16 2 4 b1=2 b2=1一共操作3次即可ai=2，ai+1=4时，要算出bi+1操作次数，计算出要ai>ai+1的次数减去即可。 代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+10; void sol(){ int n;cin>>n; int a[n+10]; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<n;i++){ if(a[i]>1&&a[i+1]==1){ cout<<"-1"<<endl; return; } } vector<ll>b(n,0);ll ans=0; for(int i=1;i<n;i++){ ll h=a[i]; ll m=a[i+1]; ll op=0; while(h!=1&&h*h<=m){ op--,h*=h; } while(m<h){ op++,m*=m; } b[i]=max(0ll,b[i-1]+op); } for(int i=1;i<b.size();i++){ ans+=b[i]; } cout<<ans<<endl; } int main(){ int t;cin>>t; while(t--)sol(); return 0; } 