Bubble Cup 11 - Finals [Online Mirror, Div. 1] I. Palindrome Pairs(字符串hash)
程序员文章站
2022-05-09 21:09:08
...
题目链接:https://codeforces.com/problemset/problem/1045/I
题目大意:
给你N个字符串,问这N个串可以组成多少个回文对。如果两个串合二为一,再对串中的字母进行重新排序得到回文串,那么称这两个串为回文对。题目保证串只含小写字母。
解题思路:
由于合并后的串可以重新排列,我们不妨按照字母出现次数进行Hash处理。当然,对于一个串而言,我们只需要每个字母出现次数的奇偶信息,用0或1表示。如果两个串可以组成回文对,它们hash之后的串最多只有1位有区别(回文串只允许至多一个字母是奇数)。注意,要用unordered_map存储hash串相同的串的数目,因为要进行多次查询,而普通的map查询需要log级别的时间,会超时,unordered_map只需近似O(1)的时间即可完成查询。最后记得答案 / 2。
代码如下:
# include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
unordered_map <string, int> G;
string Hash[maxn];
int cnt[26];
int n;
int main(){
std::ios::sync_with_stdio(false);
while(cin >> n){
string tmp;
for(int i = 0; i < n; ++i){
cin >> tmp;
memset(cnt, 0, sizeof(cnt)); //反正是小数组,直接全初始化
for(int j = 0; j < tmp.length(); ++j)
cnt[tmp[j] - 'a']++;
Hash[i] = "";
for(int j = 0; j < 26; ++j)
Hash[i] += (cnt[j]%2) + '0';
G[Hash[i]]++;
}
long long res = 0;
for(int i = 0; i < n; ++i){
tmp = Hash[i];
res += G[tmp] - 1;
for(int j = 0; j < 26; ++j){
tmp = Hash[i]; //少写了!!!
if(tmp[j] == '0') tmp[j] = '1';
else tmp[j] = '0';
res += 1ll * G[tmp];
}
}
cout << res / 2 << endl;
G.clear();
}
return 0;
}