题目链接
题目大意
给定一个仅包含 \(0,2,5\) 的字符串，你可以在这个字符串中加入不超过 \(a\) 个 \(5\)，\(b\) 个 \(2\) 和 \(c\) 个 \(0\)，要求最后得到的字符串中连续的 \(520\) 的个数最多是多少。
Solution
贪心思路，从需要补得个数来看，优先级为：本身存在的 \(520\) 大于本身存在的 \(52,50,20\) 大于本身存在的 \(5,2,0\) 大于本身没有存在后续拼出的 \(520\)。
通过上面的优先级，我们一个一个来处理。首先从头到尾扫一遍，找出本身就已经存在的 \(520\)，并把这些位置标记，防止下面再次扫到。然后我们统计 \(50,52,20\) 这三种情况，他们分别对应着需要补 \(2,0,5\) 即 \(b,c,a\)，如果可以补就补全，因为补一个就一定比补两个或三个更优，所以在这里能补就全部补上。最后我们在统计 \(5,2,0\) 的情况，我们用补 \(5\) 和 \(2\) 的情况去算出补 \(0\) 的情况，当然在补完所有的 \(5,2,0\) 后如果 \(a,b,c\) 都还有剩余要在统计上他们能拼成的 \(520\) 的个数。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1018;
inline int read(){int x=0,f=1;char c=getchar();while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}return x*f;
}
int T=read(),cnt1,cnt2,cnt3,num0,num2,num5;
char ch[N];
bool vis[N];
signed main(){while(T--){memset(vis,false,sizeof(vis));int n=read(),a=read(),b=read(),c=read(),ans=0;scanf("%s",ch+1);for(int i=1;i+2<=n;i++){//找本来就存在的520 if(ch[i]=='5' && ch[i+1]=='2' && ch[i+2]=='0' && !vis[i] && !vis[i+1] && !vis[i+2]){vis[i]=vis[i+1]=vis[i+2]=true;ans++;}}cnt1=cnt2=cnt3=num0=num2=num5=0;for(int i=1;i<=n;i++){if(!vis[i]){if(ch[i]=='5'){vis[i]=true;if(i<n && ch[i+1]=='2' && !vis[i+1])//找本来就存在的52vis[i+1]=true,cnt1++;else if(i<n && ch[i+1]=='0' && !vis[i+1])//找本来就存在的50vis[i+1]=true,cnt3++;else num5++;//找本来就存在的5}else if(ch[i]=='2'){vis[i]=true;if(i<n && ch[i+1]=='0' && !vis[i+1])//找本来就存在的20vis[i+1]=true,cnt2++;else num2++;//找本来就存在的2}elsevis[i]=true,num0++;//找本来就存在的0}}int aa=min(cnt2,a),bb=min(cnt3,b),cc=min(cnt1,c);//能补完的尽量补 c-=cc,ans+=cc;a-=aa,ans+=aa;b-=bb,ans+=bb;int maxx=0;for(int i=0;i<=num5;i++)//枚举补5的个数 for(int j=0;j<=num2;j++){//枚举补2的个数 if(i+j>c || i>b || j>a)//如果补不了直接跳出 continue;int k=min({b-i,a-j,num0});//算出补0的个数 maxx=max(maxx,i+j+k+min({a-j-k,b-i-k,c-i-j}));//最后别忘加上剩下可以拼出来的 }printf("%lld\n",ans+maxx);}return 0;
}
千万不要搞反顺序并且需要注意优先级，我就是因为同时处理 \(50,52,20\) 和 \(5,2,0\) 这两种情况才导致赛时只拿了 \(40\) 分。
你说的对，但 \(5\) 月 \(20\) 号真的是刘浩存的生日。