题解 CF1045I 【Palindrome Pairs】
HomuraCat
2019-04-12 19:43:21
一道乱搞题
根据字符出现的奇偶性,我们可以将一个字符串化成一个$26$元组,并且每个字符用$0/1$表示这个元素出现偶数$/$奇数次,可以直接表示成一个$26$位的二进制数
然后所谓匹配就是两个数的海明距离$<=1$,直接将这些数暴力排序,海明距离$=0$就是找有多少个相等的数,$=1$每次枚举改变一位然后去所有数字里找就行,可以一个$upper\_bound$和$lower\_bound$一气呵成,详见代码
时间复杂度$O(26nlogn)$
```cpp
#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mod 998244353
#define eps 1e-4
#define lowbit(x) (x & -x)
#define N 100005
int n;
int head[N], tot, a[N], u[N];
struct node{
int nxt, v, cnt;
}e[N << 1];
int tmp[26];
char ch;
ll ans;
inline void read (int &x)
{
memset(tmp, 0, sizeof tmp);
ch = getchar();
while (!isalpha(ch)) ch = getchar();
while (isalpha(ch)) ++tmp[ch - 'a'], ch = getchar();
fo (i, 0, 25) x = (x << 1) | (tmp[i] & 1);
}
int now, x;
int main ()
{
scanf("%d", &n);
fo (i, 1, n) { read(a[i]); u[i] = a[i]; }
std::sort(u + 1, u + n + 1);
fo (i, 1, n)
{
ans += std::upper_bound(u + 1, u + n + 1, a[i]) - std::lower_bound(u + 1, u + n + 1, a[i]) - 1;
fo (j, 0, 25)
{
now = a[i] ^ (1 << j);
x = std::upper_bound(u + 1, u + n + 1, now) - std::lower_bound(u + 1, u + n + 1, now);
ans += x;
}
}
printf("%lld", ans >> 1);
}
```