CF1849F 比E简单

· · 题解

复杂度 O(n\log V) 踩标算。

先想已知 S 怎么算其权值。

考虑建立 01trie，我们找到所有极低（数位最低）的，左右儿子各有一个数的节点，算出其左右儿子的异或，然后取 \min 即可。

我们发现权值的计算可以分为两部分，一个是数位前缀的匹配（即上文找到极低节点，它们的异或为 0），一个是剩余位的异或。

于是问题变成这样：给定一棵 01trie，将其分裂为两棵，使得最低的拥有左右儿子的节点最高，在此基础上使其左右儿子异或值最大。

首先解决最低的有双子的节点最高：假如原 trie 上的节点 u 的两个儿子分别满足要么其不存在，要么 size\le 2，这样我们可以从该节点分裂，每个儿子内部染色不同，分裂为 u,u' ，二者均满足存在左右儿子，其子树为链，于是它们是极低的点。于是我们从上到下能分裂就尽早分裂，即得到最高。

然后解决儿子异或最大，这个就很简单了，因为左右儿子内的树各不超过 2 个，暴力枚举一下那两个分到一个树内使得异或的最小值最大即可。

表述可能不是很清楚，见代码：

有什么问题欢迎 hack！

#include<bits/stdc++.h>
#define N 200010
#define M 100010
#define LL long long
#define ULL unsigned long long
#define DB double
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define tep(u) for(int v:e[u])
#define INF 0x3f3f3f3f
#define mp(i,j) make_pair(i,j)
#define fi first
#define se second
using namespace std;
template <typename T> inline void read(T &a)
{
    a=0;T w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){a=(a<<3)+(a<<1)+(ch^48);ch=getchar();}
    a*=w;
}
template <typename T,typename ...Args> inline
void read(T &x,Args &...args){read(x);read(args...);}
int n,k=29,a[N]; 
bool ans[N];
vector<int> a1,a2;
struct TRIE//正常的01tire 
{
    int ch[N<<5][2],cnt[N<<5],id[N<<5],dep[N<<5],pcc;
    inline void init(){dep[0]=30;}
    inline void insert(int v,int x)
    {
        int root=0;cnt[0]++;
        per(i,29,0)
        {
            bool c=(v>>i)&1;
            if(!ch[root][c]) dep[ch[root][c]=++pcc]=dep[root]-1;
            cnt[root=ch[root][c]]++;
        }
        id[root]=x;
    }
}t;
inline void dfs(int u)//求出极低点的最高值 
{
    if((!t.ch[u][0]||t.cnt[t.ch[u][0]]<=2)&&(!t.ch[u][1]||t.cnt[t.ch[u][1]]<=2)) 
        return k=min(t.dep[u]-1,k),void();
    if(t.ch[u][0]) dfs(t.ch[u][0]);
    if(t.ch[u][1]) dfs(t.ch[u][1]);
}
inline void dfs3(int u,bool rt)
{
    if(t.id[u]) return (rt?a2:a1).push_back(t.id[u]),void();
    if(t.ch[u][0]) dfs3(t.ch[u][0],rt);
    if(t.ch[u][1]) dfs3(t.ch[u][1],rt);
}
inline void dfs1(int u)//分类讨论每个极低点 
{
    if((!t.ch[u][0]||t.cnt[t.ch[u][0]]<=2)&&(!t.ch[u][1]||t.cnt[t.ch[u][1]]<=2))
    {
        a1.clear();a2.clear();
        rep(i,0,1) if(t.ch[u][i]) dfs3(t.ch[u][i],i);//把子树内的值找到 
        if(a1.size()>a2.size()) swap(a1,a2);
        int sz1=a1.size(),sz2=a2.size(); 
        if(!sz1) rep(i,0,sz2-1) ans[a2[i]]=i;
        else if(sz1==1)//暴力分讨 
        {
            if(sz2==1) ans[a1[0]]=0,ans[a2[0]]=1;
            if(sz2==2)
            {
                ans[a1[0]]=0;
                ans[a2[0]]=((a[a1[0]]^a[a2[0]])<=(a[a1[0]]^a[a2[1]]));
                ans[a2[1]]=((a[a1[0]]^a[a2[0]])>(a[a1[0]]^a[a2[1]]));
            }
        }
        else if(sz1==2)
        {
            if(min(a[a1[0]]^a[a2[0]],a[a1[1]]^a[a2[1]])>min(a[a1[0]]^a[a2[1]],a[a1[1]]^a[a2[0]]))
            {
                ans[a1[0]]=ans[a2[0]]=0;
                ans[a1[1]]=ans[a2[1]]=1;
            }
            else
            {
                ans[a1[0]]=ans[a2[1]]=0;
                ans[a1[1]]=ans[a2[0]]=1;
            }
        }
        return;
    }
    if(t.ch[u][0]) dfs1(t.ch[u][0]);
    if(t.ch[u][1]) dfs1(t.ch[u][1]);
}
signed main()
{
    read(n);t.init();
    rep(i,1,n) read(a[i]),t.insert(a[i],i);
    dfs(0);dfs1(0);
    rep(i,1,n) printf("%d",ans[i]);printf("\n");
    return 0;
}