本文最后更新于 852 天前,其中的信息可能已经有所发展或是发生改变。
背景:
众嗦粥汁,AK
是 ALL KILLED
的简称,代表着算法竞赛选手在赛场上解决掉了全部的题目。我们的 HF 学长每次都能轻松 AK
,因此他觉得算法比赛十分的枯燥,于是他准备进行一个优雅的 AK
。
描述:
给定一个长度为 且只包含两种字符 K
和 A
的字符串 ,你可以对 进行如下操作:
-
选择 中连续且相邻的任意两个字符 $sis{i + 1}(0\le i \le N)$ ,将其替换为
AK
。上述操作不限次数,当且仅当通过上述操作能将 变为为回文串时,我们称这是一个优雅的
AK
,此时输出YES
,否则输出NO
。
回文串的定义:回文串是一个正读和反读都一样的字符串,例如 AKA
,KAAK
。
输入:
共两行,第一行输入一个正整数 ,代表字符串的长度。
接下来读入 个字符,是 包含的字符。
输出:
共一行,输出 YES
,或 NO
。
数据范围:
样例输入:
样例输出:
思想:
- 当 为 时,不需要操作就是回文串。
- 接下来明确以下两个性质:
- 当第一个字符为
A
时,无论如何操作都无法将其变为K
; - 当最后一个字符为
K
时,无论如何操作都无法将其变为A
。
- 当第一个字符为
- 因此当第一个字符为
A
且最后一个字符为K
时,无论如何操作都无法变成回文串。 - 我们先考虑第一个字符为
K
的情况:- 当第一个字符为
K
且 的长度至少为 时,由于不限制操作次数,那么我们最终一定可以通过操作得到类似KAAA...AAAK
的字符串,故是回文串。
- 当第一个字符为
- 类似的考虑最后一个字符为
A
的情况:- 当最后一个字符为
A
且 的长度至少为 时,由于不限制操作次数,那么我们最终一定可以通过操作得到类似AKKK...KKKA
的字符串,故是回文串。
- 当最后一个字符为
- 其他情况,当 长度为 时,只有
AA
和KK
是回文串。
代码1:
代码2: