[CF1799C] Double Lexicographically Minimum 题解

aeiouaoeiu · 2025-11-12 16:17:22 · 题解

字典序最小化的一个一般做法就是按位确定。设 t_i 翻转后对应 t_{to_i}，从左到右逐位确定 t，若当前确定 t_i=c，其中 c 是还剩有的最小字符，为了使 t 翻转后 t'_i 不变为一个更大的字符，需要尽可能使得 t_{to_i}=c。

如果能够满足，就向两端填入 c。否则，一个明显的想法是，设次小字符为 d，则令 t_i=d,t_{to_i}=c，这样保证了 t_{\max} 一定为 t 本身，然后剩下的字符从小到大从左往右填进去。

但是，设次次小字符为 e\neq d，若 e 不存在，可以将 c 挪到字符串中央，显然这样是最优的。否则，c 进行移动时需要在 c 曾经停留的地方放入 d 来保证还有可能使得 t_{\max}=t，此时 e 一定会向前移动，一定不优。于是分讨这样的 e 是否存在即可。

::::info[code]

#include<bits/stdc++.h>
#define pb emplace_back
#define mp make_pair
using namespace std;
typedef unsigned long long ll;
typedef __int128 LL;
const ll maxn=200007,ee=1e18;
ll n;
string s,ans;
void solve(void){
    for(ll i=0;2*i+1<n;i++){
        if(s[2*i]==s[2*i+1]) ans[i]=ans[n-1-i]=s[2*i];
        else{
            ans[i]=s[2*i+1],ans[n-1-i]=s[2*i];
            if(2*(i+1)>=n) return;
            if(s[n-1]==s[2*i+1]){
                for(ll j=i;j<=n-1-i;j++) ans[j]=s[n-1];
                ans[n/2]=s[2*i];
                return;
            }
            for(ll j=i+1,c=2*i+2;j<n-1-i;j++,c++) ans[j]=s[c];
            return;
        }
    }
    if(n&1) ans[n/2]=s[n-1];
}
int main(void){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0);
    ll T=1; cin>>T;
    for(;T--;){
        cin>>s,n=s.length();
        ans.resize(n);
        sort(s.begin(),s.end());
        solve();
        cout<<ans<<"\n";
    }
    return 0;
}

::::