📝 题目大意

有 $N$ 根棒，每根棒上插有若干写有字母的球，用字符串 $S_i$ 表示。两根棒相同当且仅当 $S_i = S_j$ 或 $S_i$ 等于 $S_j$ 的反转。求不同棒的种类数。

💡 解题思路

1. 题目分析：$N$ 和字符串总长度 $\sum |S_i|$ 均不超过 $2 \times 10^5$，可以使用 $O(N \cdot |S_i|)$ 或 $O(N \log N)$ 级别的算法，直接两两比较会超时。关键在于如何高效判断两个字符串是否互为反转——即如何将"相同或互为反转"的字符串归为一类。

2. 算法推导：

   • 对于每个字符串 $S_i$，构造其反转字符串 $rev\_s$。
   • 取 $S_i$ 和 $rev\_s$ 中字典序较小的那个作为该字符串的标准形式（standard = min(s, rev_s)）。
   • 将所有字符串的标准形式插入 set<string> 中，利用集合自动去重。
   • 最终 set 的大小即为答案。
   • 核心原理：若 $S_i$ 与 $S_j$ 相同或互为反转，则它们的标准形式必然相同（因为标准形式取的是两者中字典序较小的那个，而反转操作不会改变集合 $\{s, rev(s)\}$）。

3. 边界与细节：

   • 单字符字符串无需特殊处理，反转后仍是自身，min(s, rev_s) 结果正确。
   • 回文串（如 aba）反转后与原串相同，min 返回自身，不影响去重。
   • 注意 reverse 需要 <algorithm> 头文件，不过 #include <bits/stdc++.h> 已包含。

⏱️ 复杂度分析

• 时间复杂度：$O(\sum |S_i| \cdot \log N)$，每条字符串需要 $O(|S_i|)$ 进行反转和比较，set 插入操作为 $O(\log N)$。
• 空间复杂度：$O(\sum |S_i|)$，存储所有字符串的标准形式。

💻 标准代码 (C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    string s;
    cin >> n;
    set<string> st;                     // 用于存储每种棒的标准形式，自动去重
    for (int i = 0; i < n; ++i) {
        cin >> s;
        string rev_s = s;
        reverse(rev_s.begin(), rev_s.end()); // 反转字符串
        string standard = min(s, rev_s);     // 取字典序较小的作为标准形式
        st.insert(standard);                 // 插入集合，相同形式自动去重
    }
    cout << st.size() << endl;               // 集合大小即为不同棒的种类数
    return 0;
}