打卡信奥刷题（3171）用C++实现信奥题 P7919 [Kubic] ABC

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变为pCpCpC，pA,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

输入 #1

5 ABBAA

输出 #1

1 3 4 BAC

输入输出样例 #2

输入 #2

5 ABCBA

输出 #2

0

说明/提示

对于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}。

评分方法

以下情况将会使你在该测试点获得000分：

• 输出格式不满足要求。

• 输出多余信息（包括空格和换行符）

• 构造的方案操作次数与标准答案不同。

• 构造的方案不符合题目要求。

• 时间超限。

如果没有上述情况，你在该测试点获得满分。

保证 SPJ 占用不超过100ms⁡,10MB⁡100\operatorname{ms},10\operatorname{MB}100ms,10MB。

样例解释 1

一种操作过程如下：

ABBAA

ABABA

可以证明没有更优的方案。

样例解释 2

初始序列已经符合题目要求，直接输出一行000即可。

C++实现

#include<cstdio>intn,x,y,t;chars[5003];intl[5003],r[5003];intmain(){scanf(" %d %s",&n,s+1);x=1,y=n;while(x<y){while(x<y&&s[x]!=s[x+1])++x;while(y>x&&s[y]!=s[y-1])--y;if(x==y)break;l[++t]=++x,r[t]=--y;}printf("%d\n",t);if(l[t]>r[t])r[t]=n;for(inti=1;i<=t;++i)printf("%d %d BCA\n",l[i],r[i]);return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容