题目链接： https://hihocoder.com/contest/offers55/problem/2
解题思路： 可以发现，这种朋友关系，没什么传递性之类的特征。只能考虑暴力统计，但是20000个字符串之间的比较计算太大，考虑到字符串的长度是10，所有可以查看每个字符串的变化有哪些。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 string s[20005]; 5 int a[20005]; 6 int n; 7 map<string, int> mp; 8 9 int judge(string s1, string s2) 10 { 11 int p1=-1, p2=-1; 12 int len1 = s1.length(); 13 int len2 = s2.length(); 14 if (len1 != len2) return 0; 15 for (int i = 0; i < len1; ++i) 16 { 17 if (s1[i] != s2[i]) 18 { 19 if (p1 == -1) 20 { 21 p1 = i; 22 } 23 else if (p2 == -1) 24 { 25 p2 = i; 26 } 27 else 28 { 29 return 0; 30 } 31 } 32 } 33 //printf("p1=%d p2=%d ", p1, p2); 34 return s1[p1] == s2[p2] && s1[p2] == s2[p1]; 35 } 36 37 int main() 38 { 39 //cout<<judge("aaab", "aaba")<<endl; 40 scanf("%d", &n); 41 long long ans = 0; 42 mp.clear(); 43 for (int i = 1; i <= n; ++i) 44 { 45 cin>>s[i]; 46 if (mp.find(s[i]) == mp.end()) 47 { 48 mp[s[i]] = 1; 49 } 50 else 51 { 52 mp[s[i]] += 1; 53 } 54 //cout<<"insert:"<<s[i]<<endl; 55 } 56 int sn = s[1].length(); 57 //printf("sn= %d ", sn); 58 for (auto it = mp.begin(); it != mp.end(); ++it) 59 { 60 //printf("%s ", (*it).first.c_str()); 61 char s[15]; 62 const char *ts = (*it).first.c_str(); 63 strcpy(s, ts); 64 //printf("s=%s ", s); 65 for (int i = 0; i < sn; ++i) 66 { 67 for (int j = i+1; j < sn; ++j) 68 { 69 if (s[i] != s[j]) 70 { 71 swap(s[i], s[j]); 72 //printf("search=%s ", s); 73 if (mp.find(string(s)) != mp.end()) 74 { 75 ans += mp[string(s)]; 76 } 77 swap(s[i], s[j]); 78 } 79 } 80 } 81 } 82 printf("%lld ", ans/2); 83 return 0; 84 }