P7973题解

EXODUS · 2022-09-03 21:32:44 · 题解

Part 1：前言

图论建模好题！

Part 2：正文

首先观察题目中所给的条件

在这里不妨令 A_x\geq A_y，将其分解为二进制，并把位数对齐，在这里我们假设 A_x,A_y 分解后的结果如下。

不难发现这是一种符合条件的情况，你发现了什么？

首先摆出结论，令 \text{highbit}(x) 表示 x 的最高位 1 的位置（从高位到低位），\text{zero}(x,pos) 表示 x 的第 pos 位是否是 0，则有 \text{zero}(A_x,\text{highbit}(A_y))=1。

考虑如何证明，若 \text{zero}(A_x,\text{highbit}(A_y))=0，则异或后结果的第 \text{highbit}(A_y) 位必然是 0，由于异或后第 1,2,...,\text{highbit}(A_y)-1 位与异或前的均相同，所以此时有 A_x\oplus A_y<A_x。此时如果暴力建边，可以通过维护并查集的方式维护连通块。

注意到 \text{zero}(A_x,\text{highbit}(A_y))=1 与 A_x\oplus A_y>\max(A_x,A_y) 互为充要条件，所以我们可以多维护 30 个并查集，分别表示每一位，然后对每一位 j 记录是否存在 i 使得 \text{highbit}(A_i)=j 以及是否存在 i 使得 \text{zero}(A_i,j)=1。接下来对于每个 A_i，判断他所有有 0 的位 x 是否存在 j，使得 \text{highbit}(A_j)=x，以及对其最高位 y 是否存在 j 使得 \text{zero}(A_j,y)=1，由于上述的处理，这个可以 O(1) 做到。如果存在上述两种情况的话就直接合并它与对应位数的并查集。

输出的时候直接输出该并查集中的 B 的和，带权并查集解决。由于我没写按秩合并，所以时间复杂度是 O(n\log^2n) 的。

Part 3：代码

bool DataS=0,FilE=0;
int T;
void init(){
    return;
}
const int N=2e5+7,B=37;
int n;
int a[N],b[N];
int fa[N],sum[N],hib[N];
bool vis1[N],vis2[N];
int find(int i){while(i!=fa[i])i=fa[i]=fa[fa[i]];return i;}
void merge(int x,int y){x=find(x),y=find(y);if(x==y)return;fa[x]=y,sum[y]+=sum[x];}
signed main(){
    if(FilE){
        freopen("test.in","r",stdin);
        freopen("test.out","w",stdout);
    }
    T=(DataS?read():1);
    while(T--){
        init();
        n=read();
        for(int i=1;i<=n;i++)a[i]=read();
        for(int i=1;i<=n;i++){
            b[i]=read();
            fa[i]=i,sum[i]=b[i];
        }
        int bit=30;
        for(int i=1;i<=bit+1;i++)fa[i+n]=i+n;
        for(int i=1;i<=n;i++){
            for(int j=bit,flag=1;~j;j--){
                if((a[i]&(1<<j))&&flag)vis1[j]=1,flag=0,hib[i]=j;
                if((!(a[i]&(1<<j)))&&(!flag))vis2[j]=1;
            }
        }
        for(int i=1;i<=n;i++){
            if(vis2[hib[i]])merge(i,hib[i]+n+1);
            for(int j=hib[i],flag=1;~j;j--){
                if(!(a[i]&(1<<j))&&vis1[j])merge(i,j+n+1);
            }
        }
        for(int i=1;i<=n;i++){
            int x=find(i);
            printf("%lld\n",sum[x]);
        }
    }
    return 0;
}

Part 4：后文

点赞再走吧（可怜