Public Judge

pjudge

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100

# 21730. 【CTS Round #1 Day 2】删串

统计

提示:如果你的判定性正确,但输出了一个不合法的方案(而非 $M=0$ 的方案),你有可能会得到 Wrong Answer 且 $0$ 分的结果,请注意这一点。

给定一个长度为 $N$ 的,且仅由字符 AB 构成的串 $S$,你可以进行以下操作:

  • 选择连续的 $2$ 个或 $3$ 个元素,满足这些元素的值均相等。随后,将这些元素从串中移除。

你想要知道是否有可能将整个串删空。如果可行,你还要输出一组合法的方案。

输入格式

输入的第一行包含一个整数 $N$。

接下来一行,包含一个长为 $N$ 的,仅由字符 AB 组成的串 $S$。

输出格式

若不存在合法的方案将 $S$ 删空,则输出一行 No

否则,输出的第一行应为 Yes

随后,输出的第一行应包含一个整数 $M$,表示你的方案所需的操作次数。

接下来 $M$ 行,每行包含两个整数 $i, j$,表示删除元素 $i \sim i+j-1$ 共 $j$ 个元素。你需要保证 $j \in \{2, 3\}$ 且 $1\le i \le n-j+1$。串中的元素将从 $1$ 开始标号,且在删除后后续元素的标号也会被更新。详情可见样例数据及其解释。

请注意,本题中如果你只能够判断解是否存在,而无法构造正确的方案,你将可以取得部分分。此时,请在输出时不要输出方案,或输出一个 $M=0$ 的方案,否则可能会导致你无法正常获得这些分数。

样例数据

样例 1 输入

9
AABBBBAAA

样例 1 输出

Yes
4
3 2
3 2
1 3
1 2

样例 1 解释

  • 起始,$S = \texttt{AABBBBAAA}$,从第 $3$ 个字符开始连续删除 $2$ 个字符 $\texttt{B}$,串变为 $S = \texttt{AABBAAA}$
  • 随后,$S = \texttt{AABBAAA}$,从第 $3$ 个字符开始连续删除 $2$ 个字符 $\texttt{B}$,串变为 $S = \texttt{AAAAA}$
  • 随后,$S = \texttt{AAAAA}$,从第 $1$ 个字符开始连续删除 $3$ 个字符 $\texttt{A}$,串变为 $S = \texttt{AA}$
  • 随后,$S = \texttt{AA}$,从第 $1$ 个字符开始连续删除 $2$ 个字符 $\texttt{A}$,串变为空串。

以下输出可以获得 $60\%$ 的分数:

Yes

样例 2 输入

2
AB

样例 2 输出

No

子任务

对于所有数据,$1 \le N = |S| \le 10^6$。

对于一个测试点,如果你只能够判断方案是否存在而无法给出具体的构造,那么你可以获得 $60\%$ 的分数。

子任务 $N \le$ 分值
$1$ $15$ $8$
$2$ $300$ $15$
$3$ $6\,000$ $34$
$4$ $10^6$ $43$