题解：P9293 [ROI 2018] Addition without carry

ECEG · 2025-05-28 15:27:43 · 题解

[ROI 2018] Addition without carry题解

毛子的题目就是牛鼻。

首先容易知道「美丽的集合」一定是对于每两个数，在二进制下无交。

也就是说答案 \sum b 在二进制下若某一位为 1，那也只是一个数贡献的，也就是无进位。

我们先确定答案的最高位 p 最小为多少。为了利益最大话，我们尽量去消去一个最大的 a_i（将 b_i 加上 2^p），若消不去就不合法，详细如下。

设 a_i 位数为 |a_i|，最大的为 |A|。

一直检验直到序列为空。

这样就可以判断一个 \sum b 是否合法了。为了方便，后面的 a 都是按倒序排序。

首先很容易发现，对于一个数都需要消耗一个 1，那到每个数的时候要避免一情况，那 p-(i-1)\ge |a_i|（a_i 为第 i 大，前面有 i-1 个数要先操作），即 p\ge \max\{|a_i|+i-1\}，这是一个下界。我们再考虑 \max\{|a_i|+i-1\}+1 即 \max\{|a_i|+i\}，那若 \sum b 二进制下全是 1，那遇到的每种都是上面的第二种情况，一定行，那所以说上界就是 \max\{|a_i|+i\}。

（如果当 p=\max\{|a_i|+i-1\} 时，即使全都是 1，那也有可能遇到第三种情况，导致后面的 1 不够用，所以需要进一步判断。）

好，现在我们明白 p 要么是 \max\{|a_i|+i-1\} 要么是 \max\{|a_i|+i\}，而且 \max\{|a_i|+i\} 一定可行，于是我们就判断下 \max\{|a_i|+i-1\} 就可以了。

于是现在就有个方法了，我们令 \operatorname{check}(a,p)，表示序列 a 的答案最高位是否小于等于 p，顺便返回答案，过程如下。

对于 \operatorname{check} 中的 a 算出一个 h=\max\{|a_i|+i-1\}，若 p\lt h，那一定不行，返回 0。

然后我们判断答案最高是否可以为 h，找到最小的 i 满足 |a_i|+i-1=h，将 h 到 h-i+1 分配给 a_1 到 a_i，删除 a_1 到 a_{i-1}，然后将 a_i 的最高位删去，并重新排序，接着调用 \operatorname{check}(a,h-i)，若返回为 1 的话，就直接可以了。

若返回 0，表示最高位不能为 h，如果 p=h 那 \operatorname{check}(a,p) 只能返回 0 了，否则说明最高位是 h+1。虽然将答案全部设为 1，一定就可以了，但这样是不优的。我们想去改变 h，于是我们就可以仅将最小的 i 满足 |a_i|+i-1=h 之前的所有设为 1，然后再递归下去。具体的方案是将 h+1 到 h-i+2 分配给 a_1 到 a_i，删除 a_1 到 a_i，接着用 \operatorname{check}(a,h-i+1) 去算方案（这次一定返回 1）。

若假设算 h 是 O(1)，删除一个数是 O(1)，惊奇的发现这样时间复杂度是线性的，分析如下：

对于返回为 1 的 \operatorname{check}，每次都会确定答案的一段而且不交，时间复杂度就是 O(\sum |a_i|)。

对于返回为 0 的 \operatorname{check}，若是在 p\lt h 返回的话，是不用管的，所以就是在 p=h 的地方返回 0，而且也说明 \operatorname{check}(a,h-i) 返回的 0，那时间复杂度就是 T(\operatorname{check}(a,p))=T(\operatorname{check}(a',p-i))+O(i)=O(p) （加上的 O(i) 仅是删除 i 个数的时间）。

若有一个返回 1 的 \operatorname{check} 在第一次返回 0，那返回为 0 的 \operatorname{check}(a,h-i) 的时间为 O(h-i)=O(|a_i|)，又因为第二次的 \operatorname{check} 直接将 a_i 删除了，故在后面 a_i 不会再贡献，那总的时间复杂度就是 O(\sum |a_i|)。

所以目前只需要维护一下算 h 和删除一个数就可以了。直接大力上线段树，上面的 i 其实就是第几大，那对于每个节点维护下所管区间的最大 |a_i|+i-1 和最大值的位置。

对于删除最高位的操作可以这样，我们把 a_i 的每一位都扔进线段树中，但最开始就只有最高位是存在的，其他都是不存在，当删除最高位是，可以修改叶子节点的是否存在信息即将最最大位的对应的叶子改不存在，将次大位从不存在改为存在，所以查询第几大就是查询所有比他大的又多少是存在的。

代码：

struct _{
    std::pair<int,int>mx;/*最大值和所对应位置*/int cnt/*存在个数*/,lazy;
}tree[maxn<<2];
#define mid ((l+r)>>1)
void put_tag(int k,int val){tree[k].mx.first+=val;tree[k].lazy+=val;}
void push_up(int k){tree[k].mx=std::max(tree[k<<1].mx,tree[k<<1|1].mx),tree[k].cnt=tree[k<<1].cnt+tree[k<<1|1].cnt;}
void push_down(int k){if(tree[k].lazy)put_tag(k<<1,tree[k].lazy),put_tag(k<<1|1,tree[k].lazy),tree[k].lazy=0;}
int query(int k,int l,int r,int x,int y){//查询有多少个存在
    if(x>y)return 0;
    if(x<=l&&r<=y)return tree[k].cnt;
    push_down(k);int res=0;
    if(x<=mid)res+=query(k<<1,l,mid,x,y);
    if(y>mid)res+=query(k<<1|1,mid+1,r,x,y);
    return res;
}
void change(int k,int l,int r,int x,int y,int z){//修改一个点，也就是将存在性修改，同时改一下对于h的贡献
    if(l==r)return tree[k].mx.first=y,tree[k].cnt=z,void();
    push_down(k);
    if(x<=mid)change(k<<1,l,mid,x,y,z);
    else change(k<<1|1,mid+1,r,x,y,z);
    push_up(k);
}
void add(int k,int l,int r,int x,int y,int val){//加入一个数肯定会将一段的排名+1
    if(x>y)return;
    if(x<=l&&r<=y)return put_tag(k,val),void();
    push_down(k);
    if(x<=mid)add(k<<1,l,mid,x,y,val);
    if(y>mid)add(k<<1|1,mid+1,r,x,y,val);
    push_up(k);
}
void build(int k,int l,int r){
    if(l==r)return tree[k]={{-1e9,l},0,0},void();
    build(k<<1,l,mid);build(k<<1|1,mid+1,r);push_up(k);
}
std::set<int,std::greater<int> >st;//greater可能是取反的意思，反正这样写才是优先取大的数
int n,tmp[maxn],maxx,a[maxn],tot,net[maxn];char s[maxn];std::basic_string<int>E[maxn];bool ans[maxn<<1];
void insert(int k){add(1,1,tot,1,k-1,1);change(1,1,tot,k,a[k]+query(1,1,tot,k+1,tot),1);st.insert(k);}
void erase(int k){add(1,1,tot,1,k-1,-1);change(1,1,tot,k,-1e9,0);st.erase(k);}
void print(){
    int sb=n+maxx;
    for(;!ans[sb];)sb--;
    for(int i=sb;i>=0;--i)putchar(ans[i]+'0');
}
bool solve(int p){
    if(st.size()==0)return print(),1;
    auto[h,id]=tree[1].mx;
    if(p<h)return 0;
    int now=h;std::basic_string<int>sss;
    for(;;){
        int x=*st.begin();
        erase(x);sss+=x;ans[now--]=1;
        if(x==id)break;
    }
    // fprintf(stderr,"%d",net[id]);
    if(net[id]&&net[id]!=1e9)insert(net[id]);
    if(solve(now))return 1;
    if(net[id]&&net[id]!=1e9)erase(net[id]);
    if(p==h){
        for(int i=h;i>now;--i)ans[i]=0;
        for(int x:sss)insert(x);
        return 0;
    }
    ans[now+1]=0;ans[h+1]=1;//这里由于[h,h-i+1]和[h+1,h-i+2]又两个位置不一样
    return solve(now+1);
}
signed main(){
    read(n);
    for(int i=1;i<=n;++i){
        scanf("%s",s+1);int len=strlen(s+1);std::reverse(s+1,s+len+1);maxx=std::max(maxx,len);
        for(int j=1;j<=len;++j)if(s[j]=='1')E[j]+=i,tot++;
    }
    int lp=0;
    for(int i=1;i<=maxx;++i){
        std::sort(E[i].begin(),E[i].end(),[](int x,int y){return tmp[x]<tmp[y];});//若当前这位一样，还有让后面的小，这样才能让a是单增的
        for(int x:E[i])net[++lp]=tmp[x],tmp[x]=lp,a[lp]=i-1;
    }
    build(1,1,tot);
    for(int i=1;i<=n;++i)insert(tmp[i]);
    solve(n+maxx);
    return 0;
}