Bubble Cup 11 - Finals [Online Mirror, Div. 2], problem (H) Palindrome Pairs 字符处理优化
程序员文章站
2022-03-02 23:24:35
...
此题是字符处理,两两枚举判断时间复杂度为O(n2),不能满足要求,可以利用小写字母只有26个可以优化时间复杂度。如果字符串字母都为偶数或者只有一个字母为奇数,则两两符合条件。统计每个字符串奇数字母并记录再根据上述条件求解即可,时间复杂度为O(n)。
ac代码:
#include <bits/stdc++.h>
#define FOR(I,A,B) for(int I = (A); I < (B); I++)
#define FORE(I,A,B) for(int I = (A); I <= (B); I++)
#define PRII pair<int,int>
#define LL long long
#define INF 1000000001
#define N 200005
using namespace std;
int n;
map<int,int>m;
LL ans;
int main()
{
cin >> n;
FORE(i,1,n){
string s;
int w = 0;
cin >> s;
FOR(j,0,s.length()) w^=1<<(s[j]-'a');
ans+=m[w];
FOR(j,0,26){
if(m.find(w^(1<<j)) != m.end()) ans+=m[w^(1<<j)];
}
m[w]++;
}
cout << ans << endl;
return 0;
}