原题链接

背景：

众嗦粥汁，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;

}