ALL KILLED
本文最后更新于 739 天前,其中的信息可能已经有所发展或是发生改变。

原题链接

背景

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

描述

给定一个长度为 $N$ 且只包含两种字符 KA 的字符串 $S$,你可以对 $S$ 进行如下操作:

  • 选择 $S$ 中连续且相邻的任意两个字符 $sis{i + 1}(0\le i \le N)$ ,将其替换为 AK

    上述操作不限次数,当且仅当通过上述操作能将 $S$ 变为为回文串时,我们称这是一个优雅的 AK,此时输出 YES,否则输出 NO

回文串的定义:回文串是一个正读和反读都一样的字符串,例如 AKAKAAK

输入

共两行,第一行输入一个正整数 $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$ 时,只有 AAKK 是回文串。

代码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;

}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇