I. Palindrome Pairs - 哈希

I. Palindrome Pairs

题意：

给你n个字符串 将这两个字符串拼接在一起 字母间可以换位子 求有几对字符串能拼接后能组成回文串

思路：

对于每个字符串如果一个字母出现偶数次就就可以直接消掉 因为它可以在两边各放一个字符串来构造字符串 如果出现奇数次 那么通过两边各放一个的操作

最后会剩下一个

对于每个字符串我们可以预处理 删去偶数个数的字母 保留单个奇数个数的字母 转换成一个不含重复字母的字符串 然后只要对比两个字符串是否含有相同的字母

或者其中一个字符串比另一个字符串多一个字母

上述字符串的对比可以用哈希来实现 将a-z对应二进制数第i位的1 将新的字符串转换为二进制01串 用map记录每个01串的个数 

然后 遍历map 每次将当前01串的1位 1变成0 形成新的字符串 两个字符串出现的次数的乘积贡献给答案 答案还要加上01相等的情况

以为map已经键值排序了 每次转换一位1 肯定比当前小 所以不会重复 

#include
#define ll long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

const ll inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-4;
const int N = 1e6 + 5;
const int M = 1e5 + 5;
ll n, base[N], a[N], hs[N];
string s;

mapmp, cnt;
void solve()
{
    cin >> n;
        //预处理 转化二进制为十进制
    base[0] = 1;
    for (int i = 1; i <= 26; i++) {
        base[i] = base[i - 1] * 2;
    }
        //cnt 用于存储某个01串的个数
    cnt.clear();
    for (int j = 1; j <= n; j++) {
                //用于存储单个字符串 的某个字母出现的次数
        mp.clear();
        cin >> s;
        for (int i = 0; i < s.size(); i++) {
            mp[s[i] - 'a' + 1]++;
        }
        for (int i = 1; i <= 26; i++) {
            if (mp[i] % 2) hs[j] += base[i];
        }
        cnt[hs[j]]++;
    }
    map::iterator it;
    ll ans = 0;
    for (it = cnt.begin(); it != cnt.end(); it++) {
                ll x = it->first;
        ans += (it->second - 1) * (it->second) / 2;
        for (int i = 1; i <= 26; i++) {
            if ((x >> i) % 2) {
                if(cnt[x - (1 << i)])
                    ans += cnt[x - (1 << i)] * cnt[x];
            }
        }
    }
    cout << ans << "\n";
}

int main()
{
    IOS;
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
}