AC

Crystal's fortune predict system is successfully developed!

The predict system is a distributed system consists of $N$ computers. When it receives a predict request, each computer will generate one lowercase letter as its output. The final fortune predict result is determined by the concentration of all $N$ outputs.

Tired of getting bad predictions like $\texttt{awful: millions of bugs}$ , Ben decides to hack into the predict system and modify the predict result. He has already got the access permission of every computer in the predict system, so he can modify their output to any letter arbitrarily.

As Ben is going to take part in ICPC Asia Regional Kunming Site 2077, he wants predictions like $\texttt{suitable for writing codes}$ or $\texttt{will get accepted for every problem}$ . He has found that the more times the substring $\texttt{ac}$ occurs in the concentration of all $N$ outputs, the luckier he will get in the contest. But as the contest is coming soon, he only has time to modify at most $K$ outputs of the computers in the predict system.

As Ben is busy hacking into the system, could you tell him how to get the most $\texttt{ac}$ substrings after his modification?

Output two lines. The first line contains a single integer, denotes the maximum number of $\texttt{ac}$ substring Bob can get, after his modification. The second line contains the final modified predict string. If there are multiple ways that results in the maximum number of $\texttt{ac}$ substring, print any.

#include<bits/stdc++.h> #define pii pair<int,int> using namespace std; const int M=5e5+9; int n,k,ans; int pre[M],nex[M],a[M],l[M],r[M]; char s[M]; bool vis[M]; priority_queue<pii>q; int main(){ scanf("%d%d%s",&n,&k,s+1); for(int i=1;i<=n;++i)pre[i]=i-1,nex[i]=i+1,l[i]=r[i]=i; for(int i=1;i<n;++i){ a[i]=(s[i]!='a')+(s[i+1]!='c'); q.push({-a[i],i}); } a[0]=a[n]=1e8; nex[0]=1;pre[n+1]=n; while(!q.empty()&&-q.top().first<=k){ int val=q.top().first,id=q.top().second; q.pop(); if(vis[id])continue; k+=val; ans++; r[id]=r[nex[id]]; l[id]=l[pre[id]]; a[id]=a[pre[id]]+a[nex[id]]+val; vis[pre[id]]=vis[nex[id]]=1; pre[id]=pre[pre[id]]; nex[id]=nex[nex[id]]; pre[nex[id]]=nex[pre[id]]=id; q.push({-a[id],id}); } printf("%d\n",ans); for(int id=1;id<=n;++id){ if(vis[id])continue; for(int i=l[id]+1;i<r[id];i+=2)s[i]='a',s[i+1]='c'; } printf("%s\n",s+1); return 0; }

详情