题解 CF1654F Minimal String Xoration

Little09 · 2022-03-22 22:37:08 · 题解

难点：这题让你求找到一个 x 使得字符串字典序最小，但是事实上是可以求出第 k 小的。

令 f(x,k) 表示取 x 作为 xor 的值，得到字符串的前 2^k 个字符的子串。那么有一个很重要的性质：

加号表示字符串的拼接。证明比较简单，对于前 2^{k-1} 位的 i，满足 i\text{ xor }x=(i+2^{k-1})\text{ xor }(x \text{ xor } 2^{k-1})，所以拼接是可行的。

所以我们倍增地做。枚举 k，每次对所有 x 按字符串的字典序排序。拼接时先考虑前面的字符串，再考虑后面的就行了。

复杂度是 O(n^2\times 2^n)。两个 n 其中一个是枚举 k，另一个是对 2^n 个数排序的 \log。

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
char s[N];
int a[N],v[N];
int t[N],n,m;
int l;
bool cmp(int x,int y)
{
    if (v[x]==v[y]) return v[x^l]<v[y^l];
    return v[x]<v[y];
}

int main()
{
    scanf("%d",&n);
    scanf("%s",&s);
    m=(1<<n);
    for (int i=0;i<m;i++) a[i]=i;
    for (int i=0;i<m;i++) v[i]=s[i]-'a';
    sort(a,a+m,cmp);
    for (int i=1;i<=n;i++)
    {
        l=(1<<(i-1));
        sort(a,a+m,cmp);
        int cnt=0;
        for (int j=0;j<m;j++)
        {
            if (j==0||cmp(a[j-1],a[j])) t[a[j]]=++cnt;
            else t[a[j]]=cnt;
        }
        for (int j=0;j<m;j++) v[j]=t[j];
    }
    int ans=a[0];
    for (int i=0;i<m;i++) printf("%c",s[i^ans]);
    return 0;
}