[ARC209B] Minimize Even Palindrome

· · 题解

找性质题。

思路：

显然，发现一个偶回文串中间会出现两个相邻的相同字符。

先考虑能否构造出一个串相邻字符不同，显然充要条件是 \max cnt_i \le n - \max cnt_i + 1，此时没有偶回文串：

否则 \max cnt_i > n - \max cnt_i + 1 时，显然是把 \max cnt_i 对应的字符 c 分成若干段，显然一段长度为 len 的相同段造成的贡献是 O(len^2) 的，所以显然若要划分为 p 段的话，应该是一堆长度为 \lfloor \frac{cnt_c}{p} \rfloor 或者 \lfloor \frac{cnt_c}{p} \rfloor + 1 的。

但是这样还不是最优，因为考虑 aabaabaa，此时存在着以中间 aa 开始的拼接其它外面段的偶数回文串，怎么避免呢？显然若每个段长都是奇数，那么就不可能以它为中心出现别的偶数回文串。

同时注意到对于两个偶回文串 len, len，改成 len - 1, len + 1 后它们内部的偶回文串数量之和是不变的，还改变了两个偶数段的奇偶性。

于是判断一下偶数段数量的奇偶性即可，如果是奇数则剩下一个偶数段放到最后也不会造成贡献。

时间复杂度是 O(n)。

完整代码：

 #include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define add(x, y) ((x + y >= mod) ? (x + y - mod) : (x + y))
#define dec(x, y) ((x - y < 0) ? (x - y + mod) : (x - y))
#define popcnt(x) __builtin_popcount(x)
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const int N = 2e5 + 10, M = 26;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
int T, n, mx, id;
char s[N];
int cnt[M];
inline void solve1(){
    priority_queue<pair<int, char>> Q;
    for(int i = 0; i < M; ++i)
      if(cnt[i])
        Q.push({cnt[i], (char)('a' + i)});
    while((int)Q.size() >= 2){
        auto x = Q.top();
        Q.pop();
        auto y = Q.top();
        Q.pop();
        putchar(x.se);
        putchar(y.se);
        if(x.fi > 1)
          Q.push({x.fi - 1, x.se});
        if(y.fi > 1) 
          Q.push({y.fi - 1, y.se});
    }
    if(!Q.empty()){
        assert(Q.top().fi == 1);
        putchar(Q.top().se);
    }
    putchar('\n');
}
inline void solve2(){
    int p = n - mx + 1;
    int y = mx % p, x = p - y;
    int len = mx / p;
    assert(len * x + (len + 1) * y == mx);
    int c1 = 0, c2 = 0, c3 = 0, c4 = 0, end = 0; // len - 1, len, len + 1, len + 2, end
    if(len & 1){
        c2 += x;
        c2 += (y >> 1);
        c4 += (y >> 1);
        if(y & 1)
          end = len + 1;
    }
    else{
        c3 += y;
        c1 += (x >> 1);
        c3 += (x >> 1);
        if(x & 1)
          end = len;
    }
    stack<char> stk;
    for(int i = 1; i <= n; ++i)
      if(s[i] - 'a' != id)
        stk.push(s[i]);
    while(c1--){
        for(int i = 1; i <= len - 1; ++i)
          putchar('a' + id);
        if(stk.size())
          putchar(stk.top()), stk.pop();
    }
    while(c2--){
        for(int i = 1; i <= len; ++i)
          putchar('a' + id);
        if(stk.size())
          putchar(stk.top()), stk.pop();
    }
    while(c3--){
        for(int i = 1; i <= len + 1; ++i)
          putchar('a' + id);
        if(stk.size())
          putchar(stk.top()), stk.pop();
    }
    while(c4--){
        for(int i = 1; i <= len + 2; ++i)
          putchar('a' + id);
        if(stk.size())
          putchar(stk.top()), stk.pop();
    }
    if(end){
        for(int i = 1; i <= end; ++i)
          putchar('a' + id);
    }
    putchar('\n');
}
inline void solve(){
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for(int i = 0; i < M; ++i)
      cnt[i] = 0;
    for(int i = 1; i <= n; ++i)
      ++cnt[s[i] - 'a'];
    mx = id = 0;
    for(int i = 0; i < M; ++i){
        if(cnt[i] > mx){
            mx = cnt[i];
            id = i;
        }
    }
    if(mx <= n - mx + 1)
      solve1();
    else
      solve2();
}
int main(){
    T = read();
    while(T--)
      solve();
    return 0;
}