2023ICPC亚洲区域赛(合肥)VP补题题解(48th)

见贤思齐

2023ICPC亚洲区域赛(合肥)VP补题题解记录文章目录2023ICPC亚洲区域赛(合肥)VP补题题解记录写在前面已更新EFGJB，待更新ICFandE(签到题和简单题)G.StreakManipulation题目大意题目分析ac代码参考J.TakeoutDelivering题目大意题目分析ac代码参考B.QueueSorting题目大意题目分析ac代码参考写在前面已更新EFGJB，待更新IC比赛补题链接：Dashboard-The2023ICPCAsiaHefeiRegionalContest(The2ndUniversalCup.Stage12:Hefei)-CodeforcesFandE(签到题和简单题)F直接计数即可ac代码参考(FastIO已省略)defsolve():n=I()dic={}foriinrange(n):c=S()dic[c]=dic.get(c,0)+1mx=0ans=''su=0fork,vindic.items():su+=vifv>mx:mx=vans=kprint1(ansifmx>su/2else"uh-oh")solve()12345678910111213141516171819E分离x和y。ac代码参考#includeusingnamespacestd;typedeflonglongll;constintN=1e3+5;intn,m;mapmp;intcnt;inta[N][N];vectornx[1000005];vectorny[1000005];voidsolve(){ cin>>n>>m; for(inti=1;i>a[i][j]; } for(inti=1;i>t; while(t--) solve(); return0;}1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556G.StreakManipulation题目大意给你一个01串，告诉你串的长度n∈[1,2×105]n\in[1,2\times10^5]n∈[1,2×105]，最多可操作次数m∈[1,n]m\in[1,n]m∈[1,n],以及k∈min⁡(n,5)k\in\min(n,5)k∈min(n,5)。每次操作可将一个000变为111。要我们求，在不超过mmm次操作时，第kkk长的连续为111的串最长是多少。题目分析我们考虑二分答案，即二分在最多mmm次操作后，第kkk长的最小是多少(看到这个最大值最小的是不是很容易想到二分)。想想check函数怎么实现，注意到k∈min⁡(n,5)k\in\min(n,5)k∈min(n,5)。我们考虑dp，以当前是考虑前几个字符为阶段，与前面有jjj个长度大于midmidmid的连续111串和当前字符是0还是1共同构成状态。对于当前的midmidmid,设dp[i][j][0/1]dp[i][j][0/1]dp[i][j][0/1]为前iii个字符，有jjj段长度大于等于midmidmid的连续111串，且当前字符是否位于第jjj段连续111串的末尾（0为假1为真）所需的最少操作次数。考虑状态转移：如果s[i]==′0′s[i]=='0's[i]==′0′dp[i][j][0]=min(dp[i][j][0],dp[i−1][j][0],dp[i−1][j][1])dp[i][j][0]=min({dp[i][j][0],dp[i-1][j][0],dp[i-1][j][1]})dp[i][j][0]=min(dp[i][j][0],dp[i−1][j][0],dp[i−1][j][1])dp[i][j][1]=min(dp[i][j][1],dp[i−1][j][1]+1)dp[i][j][1]=min({dp[i][j][1],dp[i-1][j][1]+1})dp[i][j][1]=min(dp[i][j][1],dp[i−1][j][1]+1)否则：dp[i][j][0]=min(dp[i][j][0],dp[i−1][j][0])dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][0])dp[i][j][0]=min(dp[i][j][0],dp[i−1][j][0])dp[i][j][1]=min(dp[i][j][1],dp[i−1][j][1])dp[i][j][1]=min(dp[i][j][1],dp[i-1][j][1])dp[i][j][1]=min(dp[i][j][1],dp[i−1][j][1])此外在i≥mid and j≥0i\gemid\and\j\ge0i≥mid and j≥0时dp[i][j][1]=min(dp[i][j][1],dp[i−mid][j−1][0]+pre[i]−pre[i−mid])dp[i][j][1]=min(dp[i][j][1],dp[i-mid][j-1][0]+pre[i]-pre[i-mid])dp[i][j][1]=min(dp[i][j][1],dp[i−mid][j−1][0]+pre[i]−pre[i−mid])preprepre记录的是前缀中000的数量。总的时间复杂度为O( knlog⁡(n) )O(\kn\log(n)\)O( knlog(n) )ac代码参考#includeusingnamespacestd;constintN=2e5+5;intdp[N][6][2],pre[N];intn,m,k;strings;voidsolve(){ autocheck=[&](intmid){ for(inti=0;i=mid&j>=1) dp[i][j][1]=min(dp[i][j][1],dp[i-mid][j-1][0]+pre[i]-pre[i-mid]); } } returnmin(dp[n][k][0],dp[n][k][1])>n>>m>>k>>s; s="@"+s; for(inti=1;i>1; if(check(mid))l=mid; elser=mid-1; } if(l) cout<