CTU Open Contest 2019 G. Beer Mugs（异或前缀和 + 记忆化存储）

Beer Mugs
mugs.c, mugs.cpp, Mugs.java, mugs.py
Damian is a beer mug collector. His collection fills most of the shelves in his vintage wooden cabinet where all mugs are proudly displayed. The mugs are of various brands. There might be, and often are, more mugs of the same brand in the collection.
Mugs on a shelf in Damian’s collection always form a single symmetric row. Specifically, the symmetry of the row means that the sequence of particular mug brands in the row is the same when the mugs are being admired one by one from left to right and when the mugs are being admired one by one from right to left. There is still one empty shelf in the cabinet and Damian looks for an opportunity to fill it with a new set of mugs.
The widely recognized Mastodon brewery (admired for its Woolly Mammoth beer) organizes annually the so-called beer season. Participants of the season are engaged in daily beer brewing activities and are rewarded each day by a special collector mug. Each day in the season is assigned a particular mug brand. The mug brands for all days in the season are known in advance, some brands may appear repeatedly in the season.
A participant may subscribe for the whole season or just for a part of the season. However, all days of his or her participation have to be in one uninterrupted sequence of days, a participant cannot leave the season and then come back again after some days of absence.
Damian is keen to take part in the beer season. He decided that the set of mugs he brings home should be suited for his display without adding or removing any mug, and that the set should be as big as possible.
Given the list of mug brands provided by the brewery for all days in the beer season, find the size of the biggest set of mugs suitable for Damian’s display which can be obtained by subscribing to some appropriately chosen part of the beer season.
Input Specification
The first input line contains integer N (1 < N ≤ 300000) the number of days in the brewery beer season. The next line contains N characters representing the list of all beer mug brands offered in the season, day by day. The list is naturally ordered from the first day to the last day of the season. Each brand is coded by a single lower case letter, from ’a’ to ’t’. The list contains no blanks.
Output Specification
Print a single integer representing the size of the biggest set of mugs which Damian can bring home from the brewery beer season and which is suitable, without changes, for his collection display.
Sample Input 1
6

abcabc

Output for Sample Input 1
6

Sample Input 2
20

ghjahjghsajdjhlfslja

Output for Sample Input 2
7

Sample Input 3
12

aabbccddabcd

Output for Sample Input 3
9

题意：

寻找最长的重组后可以构成回文串的连续子串

思路：（来源于题解）

将 ' a ' - ' t '对应 2 ^ 0 --- 2 ^ 19，从左到右记录异或前缀和，用unordered_map存储不同前缀和的第一次的出现位置。

mp.count() 查看数据有没有出现过

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const int N = 3e5 +10;

int main()
{
    int n;
    string s;
    while(~scanf("%d", &n))
    {
        getchar();
        getline(cin, s);
        s = '#' + s;
        ll ans = 0, sum = 0;
        unordered_map<ll, ll>mp;
        mp[0] = 0;
        for(int i = 1; i <= n; ++i)
        {
            sum ^= (1 << (s[i] - 'a'));
            if(!mp.count(sum))
            {
                mp[sum] = i;
            }
            else
            {
                ans = max(ans, i - mp[sum]);
            }
            for(char j = 'a'; j <= 't'; ++j)
            {
                ll tmp = 1 << (j - 'a');
                if(mp.count(tmp ^ sum))
                {
                    ans = max(ans, i - mp[tmp ^ sum]);
                }
            }
        }
        printf("%lld\n", ans);
        mp.clear();
    }
    return 0;
}