ALL-KILLED

原题链接

背景：

众所周知，AK 是 ALL KILLED 的简称，代表着算法竞赛选手在赛场上解决掉了全部的题目。我们的 HF 学长每次都能轻松 AK，因此他觉得算法比赛十分的枯燥，于是他准备进行一个优雅的 AK。

描述：

给定一个长度为 \(N\) 且只包含两种字符 K 和 A 的字符串 \(S\)，你可以对 \(S\) 进行如下操作：

• 选择 \(S\) 中连续且相邻的任意两个字符 \(s_i s_{i+1}(0\le i \le N-2)\)，将其替换为 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;
}