最近距离(关键词-字符串)

Question

小猴有 n 个水晶球排成一排，每一个水晶球的颜色都是红、橙、黄、绿、蓝等等 26 种颜色中的一种，这些水晶球从左到右依次编号为1,2,…,n。
小猴最近刚刚学完回文相关知识点：如果一个字符串不论是从左向右看，还是从右向左看，内容都一样，那么这个字符串就是一个回文字符串。例如YRURY 和 Q 都是回文字符串，而 BC 则不是。
猴博士想要测试一下小猴是否完全理解了回文这一知识点，向他提出了 q 个相关问题。其中第 i 个问题是：小猴能否使用编号在l i到r i之间（包括两个端点）的所有水晶球，经过任意的重排，使得l i 到 r i之间的所有水晶球在颜色上的排列能构成一个回文，即第l i个水晶球颜色与第r i个水晶球颜色相同，第 l i+1 个水晶球颜色与第 r i−1 个水晶球颜色相同，第 l i−2 个水晶球颜色与第r i−2 个水晶球颜色相同，…。
请你帮助小猴统计 q 个问题中一共有多少个问题的结果是能够构成回文。

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

---

要解决这个问题，我们首先需要理解回文字符串的性质。一个字符串能够成为回文，当且仅当它满足以下条件：

1. 字符串的长度是奇数时，中心的字符可以是任意字符。
2. 字符串的长度是偶数时，中心两侧的字符必须相同。
3. 除了中心的字符（如果长度为奇数），其他任意两个对称位置的字符必须相同。

对于给定的问题，我们可以通过以下步骤来判断水晶球颜色序列能否构成回文：

1. 统计颜色分布：首先，我们需要统计在给定范围内（l_i 到 r_i）每种颜色的水晶球数量。
2. 检查奇数长度：如果序列长度是奇数，我们需要确保至少有一种颜色的水晶球数量是奇数，以便放在中心位置。
3. 检查偶数长度：如果序列长度是偶数，我们需要确保所有颜色的水晶球数量都是偶数。
4. 计算回文构成的可能性：如果满足以上条件，那么这个序列就可以通过任意重排构成回文。

下面是C++代码实现的示例：

#include <iostream>
#include <vector>
#include <unordered_map>

int canFormPalindrome(const std::vector<char>& balls, int l, int r) {
    // 统计颜色分布
    std::unordered_map<char, int> colorCount;
    for (int i = l; i <= r; ++i) {
        colorCount[balls[i]]++;
    }

    // 检查能否构成回文
    int oddCount = 0; // 奇数计数
    for (auto& pair : colorCount) {
        if (pair.second % 2 != 0) {
            oddCount++;
        }
    }

    // 如果序列长度是奇数，需要至少一个奇数颜色
    // 如果序列长度是偶数，所有颜色的数量都必须是偶数
    int len = r - l + 1;
    return (len % 2 == 0 && oddCount == 0) || (len % 2 == 1 && oddCount <= 1);
}

int main() {
    // 示例：水晶球颜色序列和问题数量
    std::vector<char> balls = {'R', 'O', 'Y', 'G', 'B', 'O', 'R'};
    int q = 3; // 问题数量
    std::vector<std::pair<int, int>> queries = {{0, 2}, {1, 4}, {2, 6}};

    int canForm = 0; // 能构成回文的问题数量
    for (auto& query : queries) {
        if (canFormPalindrome(balls, query.first, query.second)) {
            canForm++;
        }
    }

    std::cout << "可以构成回文的问题数量: " << canForm << std::endl;
    return 0;
}

这段代码定义了一个函数 canFormPalindrome 来检查给定范围内的水晶球颜色序列能否构成回文。然后在 main 函数中，我们定义了一个示例水晶球颜色序列和几个查询，统计了能构成回文的问题数量。

至于参考资料，你可以查看以下资源来获取更多关于回文字符串和C++编程的信息：

1. GeeksforGeeks - Palindrome String
2. C++ Standard Library - unordered_map
3. C++ Programming - Strings

请注意，这些链接可能需要根据你的具体需求进行选择和调整。