P7919 [Kubic] ABC题目背景建议先看 D 题题目背景。题目描述给定一个长度为nnn的只包含A,B,C\texttt{A,B,C}A,B,C的字符串SSS你可以进行若干次操作每次操作为先选择一个区间[l,r][l,r][l,r]你需要保证1≤l≤r≤n1\le l\le r\le n1≤l≤r≤n。再选择三个字符pA,pB,pC∈{A,B,C}pA,pB,pC\in\{\texttt{A,B,C}\}pA,pB,pC∈{A,B,C}并将Sl…rS_{l\dots r}Sl…r​中所有A\texttt{A}A变为pApApA所有B\texttt{B}B变为pBpBpB所有C\texttt{C}C变为pCpCpCpA,pB,pCpA,pB,pCpA,pB,pC可以相等。求出最少需要进行多少次操作才能使得SSS中任意相邻两个字符不同并输出构造方案。输入格式第一行一个整数nnn。第二行一个长度为nnn的字符串SSS。输出格式第一行一个整数mmm表示你所构造的方案的操作次数。接下来mmm行每行两个整数l,rl,rl,r和三个字符pA,pB,pCpA,pB,pCpA,pB,pC。你需要保证1≤l≤r≤n,pA,pB,pC∈{A,B,C}1\le l\le r\le n,pA,pB,pC\in\{\texttt{A,B,C}\}1≤l≤r≤n,pA,pB,pC∈{A,B,C}。注意pA,pB,pCpA,pB,pCpA,pB,pC之间不需要也不应该加空格参考样例输出。输入输出样例 #1输入 #15 ABBAA输出 #11 3 4 BAC输入输出样例 #2输入 #25 ABCBA输出 #20说明/提示对于100%100\%100%的数据1≤n≤5×103,Si∈{A,B,C}1\le n\le 5\times 10^3,S_i\in\{\texttt{A,B,C}\}1≤n≤5×103,Si​∈{A,B,C}。分值nnn特殊性质Subtask⁡1\operatorname{Subtask}1Subtask1111无特殊限制∀i∈[1,n),Si≠Si1\forall i\in[1,n),S_i\neq S_{i1}∀i∈[1,n),Si​Si1​Subtask⁡2\operatorname{Subtask}2Subtask2191919≤10\le 10≤10无Subtask⁡3\operatorname{Subtask}3Subtask3101010无特殊限制SiAS_i\texttt{A}Si​ASubtask⁡4\operatorname{Subtask}4Subtask4202020无特殊限制Si∈{A,B}S_i\in\{\texttt{A,B}\}Si​∈{A,B}Subtask⁡5\operatorname{Subtask}5Subtask5202020≤100\le 100≤100无Subtask⁡6\operatorname{Subtask}6Subtask6303030无特殊限制无评分方法以下情况将会使你在该测试点获得000分输出格式不满足要求。输出多余信息包括空格和换行符构造的方案操作次数与标准答案不同。构造的方案不符合题目要求。时间超限。如果没有上述情况你在该测试点获得满分。保证 SPJ 占用不超过100ms⁡,10MB⁡100\operatorname{ms},10\operatorname{MB}100ms,10MB。样例解释 1一种操作过程如下ABBAAABABA可以证明没有更优的方案。样例解释 2初始序列已经符合题目要求直接输出一行000即可。C实现#includecstdiointn,x,y,t;chars[5003];intl[5003],r[5003];intmain(){scanf( %d %s,n,s1);x1,yn;while(xy){while(xys[x]!s[x1])x;while(yxs[y]!s[y-1])--y;if(xy)break;l[t]x,r[t]--y;}printf(%d\n,t);if(l[t]r[t])r[t]n;for(inti1;it;i)printf(%d %d BCA\n,l[i],r[i]);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容