Bubble-Cup-11-Finals-Online-Mirror-Div-2-problem-H-Palindrome-Pairs

题目链接

此题是字符处理，两两枚举判断时间复杂度为O(n2)，不能满足要求，可以利用小写字母只有26个可以优化时间复杂度。如果字符串字母都为偶数或者只有一个字母为奇数，则两两符合条件。统计每个字符串奇数字母并记录再根据上述条件求解即可，时间复杂度为O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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;
}