A
先往从左下角到右上角的对角线进行填充，再不断地从两边填充。
#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
const int MAXN=3e5+10;
const int mod=998244353;
using namespace std;
using ll=long long;
void solve();
int main()
{
int t=1;
cin>>t;
while(t--)
{
solve();
}
}
void solve()
{
int n,k; cin>>n>>k;
int ans=0;
if(k==0)
{
cout<<0<<"\n";
return;
}
for(int i=2*n+1;i>=1;i--)
{
if(i==2*n+1)
{
k-=n;
ans++;
}
else
{
k-=(i-1)/2;
ans++;
}
if(k<=0)
{
break;
}
}
cout<<ans<<"\n";
}
|
B1
直接进行统计模拟，需要注意的是：可能存在可以补充的情况。
如果先全取\(x\)，再部分取\(x+1\)，在总和小于\(m\)的情况下，可以少取\(x\)，多取\(x+1\)。
#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
const int MAXN=2e5+10;
const int mod=998244353;
using namespace std;
using ll=long long;
void solve();
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
cin>>t;
while(t--)
{
solve();
}
}
void solve()
{
ll n,m; cin>>n>>m;
vector<ll> a(n);
map<ll,ll> mp;
for(int i=0;i<n;i++)
{
cin>>a[i];
mp[a[i]]++;
}
ll ans=0;
for(auto [x,y]: mp)
{
ll cnt_1=min(y,m/x);
ll tot=cnt_1*x;
if(mp.count(x+1))
{
ll num=mp[x+1];
ll cnt_2=min(num,(m-tot)/(x+1));
tot+=cnt_2*(x+1);
num-=cnt_2;
ll add=min(num,cnt_1);
tot=min(tot+add,m);
}
ans=max(ans,tot);
}
cout<<ans<<"\n";
}
|
B2
思路跟上面一样。
#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
const int MAXN=2e5+10;
const int mod=998244353;
using namespace std;
using ll=long long;
void solve();
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
cin>>t;
while(t--)
{
solve();
}
}
void solve()
{
ll n,m; cin>>n>>m;
vector<ll> a(n);
map<ll,ll> mp;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<n;i++)
{
int x; cin>>x;
mp[a[i]]=x;
}
ll ans=0;
for(auto [x,y]: mp)
{
ll cnt_1=min(y,m/x);
ll tot=cnt_1*x;
if(mp.count(x+1))
{
ll num=mp[x+1];
ll cnt_2=min(num,(m-tot)/(x+1));
tot+=cnt_2*(x+1);
num-=cnt_2;
ll add=min(num,cnt_1);
tot=min(tot+add,m);
}
ans=max(ans,tot);
}
cout<<ans<<"\n";
}
|
C
这题如果直接暴力模拟肯定会溢出，所以不行。
如果多写几个\(a_{i-1}\)，\(a_i\)可以发现：如果两者都进行\(k\)次平方，让\(a_i>a_{i-1}\)的次数和原来是一样的。
使用\(b_i\)表示\(a_i\)需要的操作次数。
如果\(a_i<a_{i-1}\)，模拟计算需要的次数\(cnt\)，并且\(b_i=b_{i-1}+cnt\)。
否则，对\(a_{i-1}\)进行计算（对\(a_i\)进行开方的操作次数\(cnt\)），\(b_i=max(0,b_{i-1}-cnt)\)。（这么搞是可以模拟计算出\(a_i\)需要的操作次数，如果\(cnt>b_{i-1}\)，说明原来就比他大，根本不需要进行操作）。
麻烦的是一些细节，不好调。
#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
const int MAXN=2e5+10;
const int mod=998244353;
using namespace std;
using ll=long long;
void solve();
ll qpower();
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
cin>>t;
while(t--)
{
solve();
}
}
ll qpower(ll a,ll p)
{
ll ans=1;
while(p)
{
if(p&1) ans=ans*a;
a*=a;
p>>=1;
}
return ans;
}
void solve()
{
int n; cin>>n;
vector<ll> a(n);
vector<ll> b(n);
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int ans=0;
for(int i=1;i<n;i++)
{
if(a[i]==1 && a[i-1]>a[i])
{
cout<<-1<<"\n";
return;
}
else
{
if(a[i]<a[i-1])
{
int cnt=0;
ll t1=a[i-1],t2=a[i];
while(t1>t2)
{
t2*=t2;
cnt++;
}
b[i]=b[i-1]+cnt;
}
else
{
int cnt=0;
ll t1=a[i-1],t2=a[i];
if(t1==1) cnt=0;
else
{
while(t1<=t2)
{
t1*=t1;
cnt++;
}
cnt--;
}
b[i]=max(0ll,b[i-1]-cnt);
}
}
}
for(auto &t: b)
{
ans+=t;
}
cout<<ans<<"\n";
}
|
