[数据结构与算法][ROI2018]无进位加法

题目

题目背景
接上文。一块从天而降的巨石砸在 $\mathsf{O}\mathsf{n}\mathsf{e}\mathsf{I}\mathsf{n}\mathsf{D}\mathsf{a}\mathsf{r}\mathsf{k}$ 身上。只剩下左半边脸露在外面。

“我没什么可送你的，只能送你……”

“十拳剑封印！” 从暗处出现的 $\mathsf{D}\mathsf{D}(\mathsf{X}\mathsf{Y}\mathsf{X})$ 忽然一刀结束了 $\mathsf{O}\mathsf{n}\mathsf{e}\mathsf{I}\mathsf{n}\mathsf{D}\mathsf{a}\mathsf{r}\mathsf{k}$ 报团取暖的人生。“原谅我，小卷。我将作为你需要越过的标杆，永远地陪伴着你！”

真相却依旧在电线杆之上。电线杆上是 $\mathsf{D}\mathsf{D}\mathsf{G}$ 的爪印，和四个未曾褪色的金字——

“非吾邮箱！”

题目描述
传送门 to LOJ：给出序列 { a i } \{a_i\} {ai?}，每次操作可以给某个 $a_i$ 加 $1$ 。求最小操作次数使得 $\sum a_i=?a_i$ 。输出以二进制形式给出。

数据范围与约定
记 $L_i$ 为 $a_i$ 在二进制下的位数，则 $\sum L_i?3\times 10^5$ 。

思路

经过多方求证，总算拼凑出了这篇完整的题解。

我一直思考怎样让 $a_i$ 增加，就全完蛋了。二分答案 的优点就在于 只问结果，不看过程。

假设我们已知 $\chi =\sum b_i$，那么 { a i } \{a_i\} {ai?} 变化后得到的序列 { b i } \{b_i\} {bi?} 是对 $\chi$ 的二进制位拆分。而合法的条件就是 $b_i?a_i$ 呗！盍自讨苦吃，让 $a_i$ 一点点增大？

于是我们看出 ${\chi }_1?{\chi }_2$ 时，${\chi }_2$ 更可能合法，因为对应的 $b_i$ 只会更大。所以二分答案法是可行的——从高位开始，逐个确定 $\chi$ 的 $\mathrm{b}\mathrm{i}\mathrm{t}$，检验只需令后面的 $\mathrm{b}\mathrm{i}\mathrm{t}$ 为全 $1$ 。

怎样检验呢？找到 $\chi$ 最高二进制位 $p$ 。再找到 $v=\max a_i$ 。若 $2^{p+1}?v$，则 $v$ 不可能对应合法 $b_i$，失败。若 $2^p>v$，则该位单独作为某个 $b_i$ 时，就可以与任意剩余 $a_i$ 匹配，贪心地想肯定是与 $v$ 匹配；将 $v$ 删掉，将 $2^p$ 从 $\chi$ 中移除，继续进行该匹配。

若 $v\in [2^p,2^{p+1})$，则 $2^p$ 必须分配给 $v$ 对应的 $b_i$，并且这还不够用。将 $v$ 的最高位，即 $2^p$，与 $\chi$ 中的 $2^p$ 一同移除，然后继续进行该匹配。

那么过程中，$a_i^{\prime }$ 会是 $a_i$ 的一个后缀（较低的若干 $\mathrm{b}\mathrm{i}\mathrm{t}$ 位）。为了找 $\max$，我们需要预处理其大小关系。从低位到高位做基数排序，就能确定相同长度的后缀之间的大小关系，于是可以 $\mathcal{O}(\sum L_i)$ 进行预排序。——由于 $n?\sum L_i$，其已被忽略。

上面的做法显然不够快。我们知道，在大小比较时，最高位起到决定性作用。于是我们设 $k_i$ 为 $a_i$ 的最高位，即 $2^{k_i}?a_i<2^{k_i+1}$，考虑能不能搞出些幺蛾子。

答案的下界是 $a_i=2^{k_i}$ 。不言而喻的前提是 $a_i$ 减小（或增大）不会得到更劣（或更优）的解。记 $h$ 为 $\chi$ 的最高 $\mathrm{b}\mathrm{i}\mathrm{t}$，设 { a i } \{a_i\} {ai?} 单调递减，我们震惊地发现 $h=\max (i?1+k_i)$ 。因为用掉前 $(i?1)$ 个 $1$ 的 $\mathrm{b}\mathrm{i}\mathrm{t}$ 后，第 $i$ 个的位置不能矮于 $k_i$ 。归纳法可知其可实现。

答案的上界是 $a_i=2^{k_i+1}$ 。类型完全相同！此时 $h=\max (i+k_i)$，也就是上面的那个 $h$ 再 $+1$ 。

回到原问题。记 $h_0=\max (i?1+k_i)$，我们只需要检验 $h=h_0$ 是否可行，不可行则选取 $h=h_0+1$ 。也就是说，我们可以直接造出最优解，所谓二分答案的过程则被废弃了。

考虑 $h_0$ 究竟是谁的限制：找到最小的 $t$ 使得 $t?1+k_t=h_0$ 。由于处理 $a_t$ 之前至少有 $(t?1)$ 个 $\mathrm{b}\mathrm{i}\mathrm{t}$ 会被直接用掉，所以必须是 $[k_t,h_0]$ 这些 $\mathrm{b}\mathrm{i}\mathrm{t}$ 为全 $1$ 。但同时我们又发现，$t$ 是最小足以保证这些 $\mathrm{b}\mathrm{i}\mathrm{t}$ 恰好让那些 $a_i(i<t)$ 完成了匹配！

于是 $a_t$ 与 $k_t$ 上的 $\mathrm{b}\mathrm{i}\mathrm{t}$ 匹配，得到 $a_t$ 移除 $2^{k_t}$ 的结果。将 $a_i(i<t)$ 移除，剩下的数字只能递归了。为了加速判断，我们同样先求出一个估计值 $h_0^{\prime }$，则实际值 h ′ ∈ { h 0 ′ , h 0 ′ + 1 } h'\in\{h_0',h_0'{+}1\} h′∈{h0′?,h0′?+1} 。合法的条件显然是 $k^t>h^{\prime }$，互不干扰嘛。可以发现只有 $k_t=h_0^{\prime }+1$ 时，合法性不确定，需要再顺着 $t^{\prime }$ 递归检验。

我们还能窥见，$h=h_0+1$ 时，必须是 $(k_t+1,h]$ 这些 $\mathrm{b}\mathrm{i}\mathrm{t}$ 为全 $1$ 。因为其他情况其实都递归到上面的 ${\chi }^{\prime },h^{\prime }$ 答案；该情况却能让 $a_t$ 直接获得匹配，因而消失。所以求出 $h$ 之后，我们就能造出最优解了。

时间复杂度是什么呢？若 $h=h_0$ 成功，则递归过程没有回溯，每次至少将 $a_t$ 的一个 $\mathrm{b}\mathrm{i}\mathrm{t}$ 移除。若 $h=h_0$ 失败，由于 $k_t?1=h_0^{\prime }?k_{t^{\prime }}$，最多递归 $\mathcal{O}(k_t)$ 次，然后会将 $a_t$ 移除。

于是记势能 $\Phi =\sum k_i$，则两种情况的操作次数 $?$ 势能减小量 $\Delta \Phi$ 。所以总次数和就是 $\mathcal{O}({\Phi }_0)=\mathcal{O}(\sum L_i)$ 。

过程中 疯狂地 使用线段树或堆或平衡树等维护 $\max$，总复杂度 $\mathcal{O}[\sum L_i\log (\sum L_i)]$ 。

代码

看上去还蛮简单的。

#include <cstdio> // megalomaniac JZM yydJUNK!!!
#include <iostream> // Almighty XJX yyds!!!
#include <algorithm> // XYX yydLONELY!!!
#include <cstring> // XEZ yydSON & SY yydMT!!!
#include <cctype> // oracle: ZXY yydBUS!!!
#include <vector>
typedef long long llong;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
# define rep0(i,a,b) for(int i=(a); i!=(b); ++i)
inline int readint(){
	int a = 0, c = getchar(), f = 1;
	for(; !isdigit(c); c=getchar()) if(c == '-') f = -f;
	for(; isdigit(c); c=getchar()) a = a*10+(c^48);
	return a*f;
}

const int MAXN = 300005;
std::vector<bool> num[MAXN];
int tmp[2][MAXN], id[MAXN], k[MAXN];
int nxt[MAXN], lst[MAXN];
int radix_sort(int len){
	rep(i,1,len) id[i] = i, lst[i] = -1;
	for(int j=0,tot=0; true; ++j){
		if(len == 0) return tot;
		int* const _end = id+len+1;
		int *ptr[2] = {tmp[0],tmp[1]};
		for(int *i=id+1; i!=_end; ++i)
			if(int(num[*i].size()) != j)
				*(ptr[num[*i][j]] ++) = *i;
		rep(p,len=0,1) for(int *i=tmp[p]; i!=ptr[p]; ++i){
			id[++ len] = *i; if(!p) continue;
			nxt[tot+1] = lst[*i], k[lst[*i] = ++ tot] = j;
		}
	}
}

namespace zkw{
	int val[MAXN*3], id[MAXN*3];
	int siz[MAXN*3], ass, n;
	inline void pushUp(const int &o){
		siz[o] = siz[o<<1]+siz[o<<1|1];
		if(val[o<<1]+siz[o<<1|1] > val[o<<1|1])
			val[o] = val[o<<1]+siz[o<<1|1], id[o] = id[o<<1];
		else val[o] = val[o<<1|1], id[o] = id[o<<1|1];
	}
	void build(const int &_n){
		for(ass=1,n=_n; ass<n+2; ass<<=1);
		rep(i,1,n) id[ass+i] = i;
		memset(val+1,-1,(ass+n+1)<<2);
	}
	void insert(const int &x, const int &v){
		++ siz[x+ass], val[x+ass] = v;
		for(int i=x+ass; i>>=1; ) pushUp(i);
	}
	void erase(const int &x){
		-- siz[x+ass], val[x+ass] = -1;
		for(int i=x+ass; i>>=1; ) pushUp(i);
	}
	int query(int &rh){
		int l = ass, r = ass+n+1, rsiz = 0;
		rh = -1; int rid = 0, lh = -1, lid = 0;
		for(; (l^r)!=1; l>>=1,r>>=1){
			if(val[l^1] >= (lh += siz[l^1]))
				lh = val[l^1], lid = id[l^1];
			if(!(r&1)) continue; // do nothing
			if(val[r^1]+rsiz > rh) // strictly
				rh = val[r^1]+rsiz, rid = id[r^1];
			rsiz += siz[r^1]; // on the right
		}
		if(rh >= (lh += rsiz)) return rid;
		rh = lh; return lid; // better
	}
	bool empty(){
		int l = ass, r = ass+n+1;
		for(; (l^r)!=1; l>>=1,r>>=1){
			if(!(l&1) && siz[l^1]) return false;
			if((r&1) && siz[r^1]) return false;
		}
		return true; // nothing
	}
}

bool ans[MAXN<<1];
bool check(const int &want){
	if(zkw::empty()) return true; // great job
	int h0, t = zkw::query(h0);
	if(h0 != want) return h0 < want;
	const int now_n = zkw::n;
	zkw::n = t-1; // remove bigger ones
	if(~nxt[t]) zkw::insert(nxt[t],k[nxt[t]]);
	if(check(k[t]-1)){ // succeed
		memset(ans+k[t],true,h0-k[t]+1);
		return true; // get answer meanwhile
	}
	if(~nxt[t]) zkw::erase(nxt[t]);
	zkw::n = now_n; return false;
}
void solve(){
	while(!zkw::empty()){
		int h0, t = zkw::query(h0);
		if(check(h0)) continue; // done
		memset(ans+k[t]+1,true,h0-k[t]+1);
		zkw::n = t-1; // permanent modification	
	}
}

char str[MAXN];
int main(){
	int n = readint();
	for(int i=1,len; i<=n; ++i){
		scanf("%s",str), len = int(strlen(str));
		num[i].resize(len); rep0(j,0,len)
			num[i][j] = str[len-1-j]^48;
	}
	zkw::build(radix_sort(n));
	rep(i,1,n) zkw::insert(lst[i],k[lst[i]]);
	solve(); int len = (MAXN<<1)-1;
	while(!ans[len]) -- len; // leading zero
	drep(i,len,0) putchar(ans[i] ? '1' : '0');
	putchar('\n'); return 0;
}