题解：P9293 [ROI 2018] Addition without carry

· · 题解

这个题出得真的好 qwq。

题意

稍加分析（或者题目名字已经很明显地说了），就能得出这个题的意思：对于 a_1,\dots,a_n 找出 b_1,\dots,b_n，使得 b_i 加和不产生进位，显然，就是要求 b_i \operatorname{and} b_j =0(i\neq j)，即两两不交，在此基础上最小化 \sum{b_i}。

判定化问题

首先考虑判定一个特定的 \sum{b_i}=s 的过程。为了方便起见，后文提到的序列 a 默认按降序排序。

从高到低位考虑，一个很直觉的贪心就是，让当前最高为 1 的位 h，尝试消掉最大的数。如果存在消不掉的就不合法。具体来说，假设当前最高位是 h 而最大的数是 A，其最高位是 \lvert A\rvert：

由于 b_i 之间两两不交，我们 s 的一位只会拿去消掉一个 a_i，表示在它对应的 b_i 上加上 2^h。

正确性可以用调整法随便做做就可以得到了（真的不难，但是要严谨说明会比较繁琐，如果有时间会在结尾附上）。

上下界分析

注意这并没有单调性，所以我们得找到一种比较好的方法来确定范围。既然是最小化，那我们从最高位逐位确定。为了统一书写记号，我们让最低位从 1 开始，这样使得 \operatorname{highbit}(x)=\lvert x\rvert：

假定答案最高位是 H，确定其上界。做的时候肯定能一眼发现一个：\lvert a_1\rvert + n，因为这样肯定能把 a_i 全都用远超过它们的二的幂次消掉。但是不够紧。不过形式上应该很像才对！

在此之前不一定有思路，我们先看看下界：H\geq \lvert a_i\rvert + i-1，这是比较能够想到的，因为如果第 i 个数能被处理，应该至少有一个位擦在它的最高位上，而其前面还有 i-1 个位数比它多的数等待处理，这就决定了最高位至少应当是 h_0=\max_{i=1}^{n}\{\lvert a_i\rvert +i-1\}。如果我们再仔细一点，把这个方案画成图，会长成左边这样：

其中不同的矩形表示了不同的 a_i，其长度表示位数，左边的橙色的线表示了先前说明的下界。这是一种方便直观理解的刻画。而且我们一旦把这个下界向左挪 1，它马上就变成右边的样子，我们很自然地能够构造出这样的上界了，即 =h_0+1=\max_{i=1}^{n}\{\lvert a_i\rvert +i\}。

而且我们再观察下界的图，如果我们取出那个使 a_k+k-1 取到最大值的 k，发现 [1,k-1] 是全都被比自己高的位覆盖了的。

流程、时间复杂度

哦，我们现在有一种非常好的描述方案步骤的方法了，而且可以通过搜索模拟出来：

  1. 找到目前使得 \lvert a_k\rvert +k-1 取到最大的最小的 k（我们维护当前没有被消掉的 \{a_i\}，下标表示其排名）；
  2. 尝试下界 h_0，即：删除 a_1,\dots,a_{k-1}，让 a_k 删掉自己的最高位后重新插入集合，递归判断现在的集合 \{a\} 是否有解，如果失败，还原序列并进入下一步；否则我们确定了现在的最高位就是最优的，就得到了一组最优方案。
  3. 尝试 h_0+1。注意，其实我们这个地方必然有解，正如同先前的图那样，把 1 填满一段前缀就是一个解）；但是我们有时没有必要只填前缀——我们可能有更好的方案，于是我们可以把 [1,k] 全部删掉，接着递归判断。

这个搜索过程看起来，每一步都可能搜两次，这不是指数级的吗？但是仔细一看，好像完全不可能跑满。我们来试着分析一下：

如果我们成功执行了步骤 2，则不会回溯，可以认为对递归次数贡献为 O(1)；如果失败，我们能够 O(1) 判断出步骤 3 是否有解！为什么呢？我们前面已经知道：如果当前最高位限制是 b，表示接下来的答案最高位只能是 b。而当 h_0+1\leq b 的时候我们就可以 直接知道存在一组合法解了（这就是它是上界的原因），此时下去做就必然能够拿到一组最优解（因为前面每一步都已经必要地最优了）；而如果 h_0+1>b，我们知道，这个时候填不了 h_0，而且也填不了 h_0+1，更不可能填 h_0+2,\dots，这样肯定不符合上面对最高位的限制。但这还不足够。它要是每次走到头了才回溯，回溯到头了再通过操作 3 下来走一遍呢？这样不就炸了吗？

我们更加知道一件事：每次递归下去，我们选中的那个 k，一定是相同长度里排名最靠后那个，要么在操作 2 里面长度减 1，要么进入操作 3 直接被删掉了，而且两种情况里比它更大的全都被删掉了。也就是说：每次递归，局面里存在的最长的长度就会严格变小，对于这个选中的 a_k，它限制了接下来的递归次数是 O(\lvert a_k\rvert) 的。

于是必然经过 O(\lvert a_k\rvert) 次递归之后就会回溯，然后它会把自己删掉进入操作 3。这里有明显的势能关系，O(\lvert L\rvert) 的串，至多对应 O(\lvert L\rvert) 次递归。或者这里有个式子表示了这种关系：

H(S)=\max(H(S-L)+L,H(S-1)+1)=O(S)

前一半式子对应操作 2 失败，后一半对应成功，如果不理解，把搜索树画出来就好了。于是复杂度变为 O(\sum{L}\cdot T(n))，T(n) 表示单次操作的复杂度。

过程中的序列操作不难，使用线段树（可以外加 set，但最好不要用【见代码部分说明】），维护 h_0，就完成了。要求的操作：插入删除，全局最大值及位置（包括排名和权值）。这些操作单次都在 O(\log{n}) 内完成，于是一共的复杂度是 O(S\log{S})，其中 S=\sum{L}。

我们可能需要去掉某个 a_i 的最高位，我们对这些串的后缀做排序即可，这一部分类似基数排序，对于相同的一的位置可以转到比较后缀，可以见代码，这里不会是瓶颈。

代码

以下是代码实现。

关于 set 的使用：由于笔者真的很弱，只能做分析做到这一步了，我不清楚在 这篇题解 中使用 set 每次逐个加入、删除的时间是不是对的，因为它与 n 相关，这并不在我自己想的均摊分析之内。但是由于我怀疑这里如果让 n 变大让 L 变小，会使得递归次数变小，感觉会有一个平衡的根号。但是我并没有找到 hack，在 CF 上面交也没有问题。

但是在写这篇文章的时候，我写的使用 set 的解法是目前最优解第三，只跑了 1.04s，这里是提交记录：Submission。有感兴趣的老师可以 Hack 一下或者证明正确性。

我重新写了一份复杂度应当严格正确的线段树解法，特化成前缀删和区间查，还是比较好写的：

#include<bits/stdc++.h>
#define all(X) X.begin(),X.end()
using namespace std;
const int N=3e5+10;
const int INF=0x3f3f3f3f;
struct Node{
    int v,p,c,tag;
};
inline Node operator+(const Node &X,const Node &Y){
    return (Node){max(X.v,Y.v),X.v>=Y.v?X.p:Y.p,X.c+Y.c,0};
}
struct SegTree{
    Node t[N<<2];
    // int t[N<<2],p[N<<2],tag[N<<2];
    #define ls (x<<1)
    #define rs (x<<1|1)
    inline void upd(int x,int y){t[x].v+=y,t[x].tag+=y;}
    inline void pushup(int x){t[x]=t[ls]+t[rs];}  // attention to eq.
    inline void pushdown(int x){if(t[x].tag){upd(ls,t[x].tag),upd(rs,t[x].tag),t[x].tag=0;}}
    void build(int x,int l,int r){
        if(l==r)    return t[x]={-INF,l,0,0},void();
        int mid=(l+r)>>1; build(ls,l,mid),build(rs,mid+1,r);
        pushup(x);
    }
    void update(int x,int l,int r,int ql,int qr,int y,int ad){  // ad 表示对单点次数的修改，主要是懒得改了，有点丑
        if(ql<=l && r<=qr)  return upd(x,y),t[x].c+=ad,void();
        int mid=(l+r)>>1;pushdown(x);
        if(ql<=mid) update(ls,l,mid,ql,qr,y,ad);
        if(qr>mid)  update(rs,mid+1,r,ql,qr,y,ad);
        pushup(x);
    }
    Node query(int x,int l,int r,int ql,int qr){
        if(ql<=l && r<=qr)  return t[x];
        int mid=(l+r)>>1;pushdown(x);
        if(qr<=mid) return query(ls,l,mid,ql,qr);
        if(ql>mid) return query(rs,mid+1,r,ql,qr);
        return query(ls,l,mid,ql,qr)+query(rs,mid+1,r,ql,qr);
    }
}w;
int n,prv[N],ans[N],a[N],ne[N],rk[N],tot=0;   // ne 指向当前串中的下一个一的排名
string s[N];
vector<int> pos[N];
inline void upd(int x,int op){
    w.update(1,1,tot,x,x,op*(INF+a[x]),op);
    if(x<tot)    w.update(1,1,tot,x+1,tot,op,0);   
    // 后面的数排名都加/减 1。
    // 此处的排名指的是前面的数的个数，正是 i - 1
}
inline void printans(int l,int r,int x){
    for(int i=l;i<=r;i++)   ans[i]=x;
}
bool solve(int lim,int del){
    if(del>tot)   return true;

    auto [mx,p,_c,_t]=w.query(1,1,tot,del,tot);
    int c=w.query(1,1,tot,del,p).c;

    if(mx<=0)   return true;
    if(mx>lim)  return false;

    w.update(1,1,tot,p+1,tot,-c,0);

    if(ne[p]!=INF)   upd(ne[p],1);
    int b=mx-c+1;    // b 就是 |a_i|, mx = max |a_i| + i - 1, tmp.size() == i
    if(solve(b-1,p+1)) return printans(b,mx,1),true;
    //
    if(ne[p]!=INF)   upd(ne[p],-1);
    if(mx+1<=lim)   // 事实上，如果这玩意成立那么下面肯定有解。
        return assert(solve(b,p+1)),printans(b+1,mx+1,1),true;

    w.update(1,1,tot,p+1,tot,c,0);

    return false;
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n;int mx=0;
    for(int i=1,len;i<=n;i++){
        cin>>s[i];len=s[i].size();
        mx=max(mx,len),reverse(all(s[i])),prv[i]=INF;   // add: prv init.
        for(int j=len-1,las=-1;j>=0;j--)
            if(s[i][j]=='1')    pos[j].push_back(i),++tot;
    }
    for(int i=0,ts=tot;i<mx;i++){
        sort(all(pos[i]),[&](int x,int y){return prv[x]>prv[y];});
        for(int j:pos[i]){  // fixed: 呃，这里的遍历顺序是从小到大遍历的，上面也得先从小到大排 qwq。
            ne[ts]=prv[j],prv[j]=ts,a[ts]=i+1;
            rk[j]=ts--;
        }
    }
    w.build(1,1,tot);
    for(int i=1;i<=n;i++)
        upd(rk[i],1);
    solve(INF,1);
    int ena=0;
    for(int i=N-1;i>=1;i--)
        if(ena|=ans[i]) putchar(ans[i]+'0');
    if(!ena)    putchar('0');    
    return 0;
}