题解 CF1045I 【Palindrome Pairs】

一道乱搞题 根据字符出现的奇偶性，我们可以将一个字符串化成一个$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); } ```