Moe's CF Life

喵~ 各位算法大师们好呀！这里是你们最爱的小猫娘，今天又要和大家一起玩耍，哦不，是一起解决一道有趣的构造问题啦！这道题就像是给小猫娘准备的毛线球，只要找到线头，一下子就能解开啦，喵~

Problem A: Special Characters

题目大意

这道题的要求很简单哦~ 给你一个整数 n，你需要构造一个只包含大写英文字母的字符串。这个字符串里必须正好有 n 个“特殊字符”。

那什么是“特殊字符”呢？如果一个字符和它的左邻居、右邻居中，有且仅有一个和它自己长得一样，那它就是特殊哒！

举个栗子🌰：在字符串 AAABAACC 中：

第一个 A (位置1): 只有一个邻居 A，和自己一样。所以它特殊。
第二个 A (位置2): 邻居是 A 和 A，有两个和自己一样的。所以它不特殊。
第三个 A (位置3): 邻居是 A 和 B，只有一个和自己一样的。所以它特殊。
...以此类推，这个字符串里一共有 6 个特殊字符。

如果能找到符合条件的字符串，就输出 "YES" 和你构造的字符串；如果找不到，就告诉人家 "NO" 就好啦，喵~

解题思路 (小猫娘的脑内风暴)

看到这种构造题，小猫娘的直觉告诉我，肯定有非常简单的规律！我们来分析一下怎么才能制造出“特殊字符”吧，喵~

一个字符要变得“特殊”，它的身边必须有且只有一个同类。

如果我们放一个单独的字符，比如 ...XAY... (X 和 Y 都不是 A)，那这个 A 身边没有同类，它就不特殊。
如果我们放三个连在一起的，比如 ...XAAAY...，中间的那个 A 左右都是 A，有两个同类，它也不特殊。

那最简单的方法是什么呢？当然是成对出现啦！就像这样：AA。

第一个 A：它的右边是 A，只有一个同类邻居。它特殊！
第二个 A：它的左边是 A，也只有一个同类邻居。它也特殊！

哇！AA 这一个简单的组合，就一下子给我们带来了 2 个特殊字符！

这个发现太重要啦！每次我们用一对相同的字母，就能稳定地获得 2 个特殊字符。这意味着我们创造的特殊字符数量总是成双成对地出现的。

那么，如果题目要求的 n 是一个奇数，比如 3，那不就怎么也凑不出来了吗？无论我们怎么组合，特殊字符的数量都应该是偶数才对呀。所以，当 n 是奇数时，肯定无解！直接回答 "NO" 就好啦。

如果 n 是偶数呢？那就太棒了！我们想要 n 个特殊字符，只需要 n / 2 对像 AA 这样的组合就行了。为了不让这些组合互相干扰（比如 AAAA 就不行），我们可以用不同的字母来构造每一对。

比如 n = 6：

我们需要 6 / 2 = 3 对。
第一对，我们用 A，得到 AA。
第二对，我们用 B，得到 BB。
第三对，我们用 C，得到 CC。
把它们拼在一起，就是 AABBCC！

我们来检查一下 AABBCC：

A ( pos 1 ): 邻居 A。特殊。
A ( pos 2 ): 邻居 A, B。特殊。
B ( pos 3 ): 邻居 A, B。特殊。
B ( pos 4 ): 邻居 B, C。特殊。
C ( pos 5 ): 邻居 B, C。特殊。
C ( pos 6 ): 邻居 C。特殊。

喵！6个字符全都特殊！完美解决了问题！所以，对于任何偶数 n，我们都可以用 n/2 对不同的字母来构造答案。

题解代码

下面就是把小猫娘的想法变成代码啦，非常简单直观哦~

cpp

#include <iostream>
#include <string>
#include <vector>

void solve() {
    int n;
    std::cin >> n;

    // 如果 n 是奇数，那就不可能做到啦，喵~
    if (n % 2 != 0) {
        std::cout << "NO\n";
        return;
    }

    // 如果 n 是偶数，那肯定有解！
    std::cout << "YES\n";
    std::string result = "";
    // 我们需要 n/2 对字母
    for (int i = 0; i < n / 2; ++i) {
        // 每次用一个新字母，'A', 'B', 'C'...
        char c = 'A' + i;
        // 把这对字母加到结果里
        result += c;
        result += c;
    }
    std::cout << result << "\n";
}

int main() {
    // 加速输入输出，让程序跑得像小猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Problem A: Special Characters ​

题目大意 ​

解题思路 (小猫娘的脑内风暴) ​

题解代码 ​

相关知识点介绍 ​

Problem A: Special Characters

题目大意

解题思路 (小猫娘的脑内风暴)

题解代码

相关知识点介绍