P6878 [JOI 2020 Final] JJOOII 2题目描述定义有连续K KK个J \tt JJ和连续K KK个O \tt OO和连续K KK个I \tt II组成的字符串为K KK阶 JOI 串。比如J J O O I I \tt JJOOIIJJOOII为2 22阶 JOI 串但是注意要有顺序比如O O J J I I \tt OOJJIIOOJJII就不是2 22阶 JOI 串。现在给定一个长度为N NN的字符串S SS可以对他进行3 33种操作操作1 11删除S SS开头的字符操作2 22删除S SS结尾的字符操作3 33删除S SS除了开头和结尾之外的一个字符我们要通过这些操作让S SS变为K KK阶 JOI 串。但是我们想让操作3 33尽量的少。所以我们想知道变为K KK阶 JOI 串操作3 33最少需要进行多少次如果不能变为K KK阶 JOI 串那么输出− 1 -1−1。输入格式第一行两个整数N , K N,KN,K代表字符串长度和要构造的 JOI 串的阶数。第二行N NN个字符代表字符串S SS。输出格式一行一个整数代表操作3 33的最小进行次数。如果不能变为K KK阶 JOI 串那么输出− 1 -1−1。输入输出样例 #1输入 #110 2 OJIJOIOIIJ输出 #12输入输出样例 #2输入 #29 3 JJJOOOIII输出 #20输入输出样例 #3输入 #39 1 IIIOOOJJJ输出 #3-1说明/提示样例 1 解释进行一次操作1 11变为J I J O I O I I J \tt JIJOIOIIJJIJOIOIIJ。进行一次操作2 22变为J I J O I O I I \tt JIJOIOIIJIJOIOII。进行一次操作3 33删掉字符2 22变为J J O I O I I \tt JJOIOIIJJOIOII。进行一次操作3 33删掉字符4 44变为J J O O I I \tt JJOOIIJJOOII。样例 2 解释J J J O O O I I I \tt JJJOOOIIIJJJOOOIII已经是3 33阶 JOI 串了所以不需要进行操作。样例 3 解释I I I O O O J J J \tt IIIOOOJJJIIIOOOJJJ无法变为1 11阶 JOI 串无解。数据规模与约定本题采用捆绑测试。Subtask 11 ptsN ≤ 21 N \le 21N≤21。Subtask 212 ptsN ≤ 3000 N \le 3000N≤3000。Subtask 387 pts无特殊限制。对于100 % 100\%100%的数据3 ≤ N ≤ 2 × 10 5 3 \le N \le 2 \times 10^53≤N≤2×105。1 ≤ K ≤ N 3 1 \le K \le \dfrac{N}{3}1≤K≤3N​。S SS只包含J \tt JJO \tt OOI \tt II且长度为N NN。说明翻译自 第19回日本情報オリンピック 本選 B JJOOII 2。C实现#includebits/stdc.h#defineN200005#defineinf0x3f3f3f3fusingnamespacestd;intcntj[N],cnto[N],cnti[N],n,k,cj,co,ci,lo,li,end,ans;string s;intmain(){ios::sync_with_stdio(false);cin.tie(0);intend0;while(cinnks){s s;cjcoci0;for(inti1;in;i){//记录位置if(s[i]J)cntj[cj]i;if(s[i]O)cnto[co]i;if(s[i]I)cnti[ci]i;}loli1;ansinf;for(inti1;icj;i){//遍历每一个Jif(ik-1cj)break;//如果后面不足k个跳出循环。后同理。//注意lo和li不用每次从1开始位置是单调递增的。endcntj[ik-1];while(cnto[lo]endloco)lo;if(lok-1co)break;endcnto[lok-1];while(cnti[li]endlici)li;if(lik-1ci)break;ansmin(ans,cnti[lik-1]-cntj[i]1-3*k);//总区间减去不用删除的长度即3*k}if(ans!inf)coutansendl;elsecout-1endl;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容