quhengyi11 的博客

quhengyi11 的博客

题解 CF1045I 【Palindrome Pairs】

posted on 2019-04-12 19:43:21 | under 题解 |

一道乱搞题

根据字符出现的奇偶性,我们可以将一个字符串化成一个$26$元组,并且每个字符用$0/1$表示这个元素出现偶数$/$奇数次,可以直接表示成一个$26$位的二进制数

然后所谓匹配就是两个数的海明距离$<=1$,直接将这些数暴力排序,海明距离$=0$就是找有多少个相等的数,$=1$每次枚举改变一位然后去所有数字里找就行,可以一个$upper\_bound$和$lower\_bound$一气呵成,详见代码

时间复杂度$O(26nlogn)$

#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);
}