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