喵~ 大家好呀！我是你们的猫娘小助手，今天也要元气满满地解决算法问题哦！这次我们要一起悄悄地、优雅地解决一个关于字符串配对的问题，就像猫咪在屋顶上轻盈地跳跃一样，嘻嘻~
E. 2-Letter Strings
题目大意喵
这个问题是这样哒：
主办方会给我们 n 个长度为 2 的小写字母字符串。这些字符串里的字母都来自 'a' 到 'k' 这个小小的字母表里。我们的任务呢，就是找出有多少对字符串 (s_i, s_j)，满足 i < j，并且这两个字符串只有一个位置的字符是不同的。
举个栗子吧，喵~
("ab", "cb")：它们只有第一个位置不同（'a' 和 'c'），所以算一对！("ab", "aa")：它们只有第二个位置不同（'b' 和 'a'），也算一对！("ab", "cd")：它们两个位置都不同，呜，不算。("ab", "ab")：它们完全一样，也不算哦。
最后，要把找到的总对数告诉主办方。要小心哦，答案可能会很大很大，需要用 64 位的整数（比如 C++ 里的 long long）来装，不然会溢出的，喵！
解题思路
看到要找“配对”，很多人的第一反应可能是，抓起第一个字符串，然后和后面的所有字符串一一比较；再抓起第二个，和它后面的所有字符串比较……像这样把所有可能的配对都检查一遍。
这种方法的时间复杂度是 O(N²)，其中 N 是字符串的数量。但是题目里 N 最大有 10^5 那么多，N² 就是 10^10 了，这会让电脑跑到天荒地老也算不完的，绝对会超时的！不行不行，我们猫咪做事要讲究效率，得想个更聪明的办法，喵~
我们可以换个角度思考！与其固定一个字符串去找另一个，不如我们按顺序一个个地处理字符串。每当我们拿到一个新的字符串 s，我们不去想它和 未来 的字符串怎么配对，而是回头看看，它能和 已经出现过 的字符串组成多少对呢？
假设我们现在拿到了一个新的字符串，就叫它 s = c1c2 吧（c1 是第一个字符，c2 是第二个）。它能和之前哪些字符串配对呢？
- 和它第一个字符相同（
c1），但第二个字符不同。也就是形如c1x（x != c2）的字符串。 - 和它第二个字符相同（
c2），但第一个字符不同。也就是形如yc2（y != c1）的字符串。
这两种情况是互斥的，所以我们只要分别数出这两种情况的数量，加起来就是新字符串 s 对总答案的贡献啦。
那么，怎么快速知道前面出现过多少个 c1x 和 yc2 呢？ 这就要用到我们猫咪的记忆小本本啦！我们可以准备几个计数器：
count1[char]: 记录以字符char开头的字符串已经出现过多少次。count2[char]: 记录以字符char结尾的字符串已经出现过多少次。count_full[c1][c2]: 记录完整的字符串c1c2已经出现过多少次。
有了这些小本本，当新字符串 s = c1c2 出现时：
- 符合第一种情况
c1x (x != c2)的字符串数量，就是所有以c1开头的字符串数量减去和s完全相同的字符串数量。也就是count1[c1] - count_full[c1][c2]。 - 符合第二种情况
yc2 (y != c1)的字符串数量，就是所有以c2结尾的字符串数量减去和s完全相同的字符串数量。也就是count2[c2] - count_full[c1][c2]。
我们把这两个数加到总答案 total_pairs 里。然后，为了让后面的字符串也能查询到 s，我们要更新我们的小本本：把 count1[c1]、count2[c2] 和 count_full[c1][c2] 的值都加一。
就这样，我们每处理一个字符串，只需要进行几次简单的查询和更新。整个过程走下来，每个字符串只被完整地处理了一次，时间复杂度就是 O(N) 啦，非常快，喵~
题解代码 (C++)
这是用 C++ 实现的思路，还加了一点猫娘的注释哦~
#include <iostream>
#include <vector>
#include <string>
// 加速输入输出，让程序跑得像猫一样快，咻~
void setup_fast_io() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
}
void solve() {
int n;
std::cin >> n;
// 字母只有 'a' 到 'k'，总共 11 个，用数组当小本本正好！
// count1[c]: 记录以字符 c 开头的字符串数量
std::vector<long long> count1(11, 0);
// count2[c]: 记录以字符 c 结尾的字符串数量
std::vector<long long> count2(11, 0);
// count_full[c1][c2]: 记录完整字符串 "c1c2" 的数量
std::vector<std::vector<long long>> count_full(11, std::vector<long long>(11, 0));
// 用来存放最终答案的大箱子，要用 long long 哦！
long long total_pairs = 0;
for (int i = 0; i < n; ++i) {
std::string s;
std::cin >> s;
int c1_idx = s[0] - 'a'; // 第一个字符的索引
int c2_idx = s[1] - 'a'; // 第二个字符的索引
// 喵~ 开始计算！
// 对于当前字符串 s = c1c2，我们寻找和它只差一个字符的、已经出现过的字符串
// 情况1: 首字符相同，尾字符不同 (形如 c1x)
// 数量 = (所有以 c1 开头的字符串数) - (和 s 一模一样的字符串数)
total_pairs += count1[c1_idx] - count_full[c1_idx][c2_idx];
// 情况2: 尾字符相同，首字符不同 (形如 yc2)
// 数量 = (所有以 c2 结尾的字符串数) - (和 s 一模一样的字符串数)
total_pairs += count2[c2_idx] - count_full[c1_idx][c2_idx];
// 计算完毕，把当前字符串的信息也记到小本本上，给后面的字符串用
count1[c1_idx]++;
count2[c2_idx]++;
count_full[c1_idx][c2_idx]++;
}
std::cout << total_pairs << "\n";
}
int main() {
setup_fast_io();
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}知识点小课堂
1. 计数问题的思维转换
很多计数问题，如果直接从“配对”的角度去想，很容易陷入 O(N²) 的困境。这时候，一个非常有用的技巧就是转换思维，从“整体”转向“贡献”。我们不再问“这对组合符不符合条件？”，而是问“我这个元素，能为最终答案贡献多少？”。通过遍历每个元素并计算其贡献，往往能设计出线性的、更高效的算法。
2. 频率统计 (Frequency Counting)
这道题的核心就是快速统计信息。我们用数组来充当频率表（或者叫哈希表），count1[0] 就代表以 'a' 开头的字符串数量，count_full[0][1] 就代表 "ab" 的数量。这是一种空间换时间的经典策略。
因为本题的字符集很小（'a'~'k'，11个），所以用数组 vector<long long>(11) 是最简单高效的。如果字符集是整个小写字母表，可以用 vector<long long>(26)。如果字符是任意的，或者我们要统计更复杂的东西（比如整个字符串），那就可以使用 std::map 或 std::unordered_map 啦，它们更通用，但性能上会比纯数组稍慢一点点。
3. 注意数据范围
“爆 int” 是算法竞赛中常见的陷阱！一个 int 通常只能存到 2 * 10^9 左右。而这道题，n 最大是 10^5，理论上配对数可以达到 n * (n-1) / 2 的量级，也就是差不多 5 * 10^9，早就超过了 int 的范围。所以，从一开始就要有意识地使用 long long 来存储可能变大的计数值和最终答案，这是一个好习惯，喵~
好啦，今天的讲解就到这里！希望能帮到大家，如果还有不懂的地方，随时可以再来问我哦！我们下次再见，喵~ (ฅ'ω'ฅ)