「ROI 2018 Day 2」无进位加法

Posted on Edited on In

「ROI 2018 Day 2」无进位加法

题目大意：

给出二进制数 \(a_1,\ldots a_n\) ，对于 \(b_1\ldots b_n\)

满足 \(a_i\leq b_i\) ， \(\bigoplus b_i=\sum b_i\) ，其中 \(\bigoplus\) 为异或和

求 \(\sum b_i\) 最小值

设长度量级为 \(N=\sum len(a_i)\)

\(O(N^2-N^3)\) ， 从高到低确定答案的每一个位

枚举当前位为0，下面的位为1，贪心确定是否存在方案

检查一个答案是否合法：

动态维护一个倒序的 \(a_i\) 集合，从高到低考虑每一个位置

1.如果当前位为0：

如果 \(a_i\) 中存在大于等于这一位的数，非法

2.如果当前位为1：

2-1.如果 \(a_i\) 中存在2个当前位为1的数，非法

2-2.如果 \(a_i\) 中存在恰好一个，则将这个1用于这个 \(a_i\) ，并将 \(a_i\) 去掉最高位后放回集合

2-3.不存在，用这个 \(1\) 删除最大的一个 \(a_i\)

实际看来，这个贪心本身效率并不高

\[\ \]

优化1：快速确定答案最高位的可能范围

令 \(B=\max\{ len(a_i)+i-1\}\)

则 \(len(Ans)\in[B,B+1]\)

上下界均可以由上面的贪心模拟得到

\[ \ \]

优化2：快速维护 \(a_i\) 倒序

显然在不断更改的过程中，当前的 \(a_i\) 一定是原先的某一个 \(a_i\) 的一段后缀

考虑将所有这样的后缀排序，为了方便，用每一个最高的1来表示一个合法的后缀

显然可以先按照后缀长度分类，同长度的后缀，按照后缀中下一个1出现的位置排序

也就是一个类似基数排序个过程，额外维护每一个后缀中下一个出现的 \(1\) 所对应的后缀即可

预处理复杂度为 \(O(N\log N)\)

同时，也可以用线段树快速维护插入/删除的排名，得到 \(B\) 的值，单次操作复杂度 \(O(\log N)\)

\[ \ \]

优化3

称满足 \(len(a_i)+i-1=B\) 的 \(i\) 为 \(\text{critical number}\)

令 \(p\) 为最小的 \(\text{critical number}\) ，也就是在贪心过程中第一个出现情况2-1./2-2.的位置

决策答案为 \(B\) 还是为 \(B+1\) ，也就是决策

是用 \(len(a_p)\) 这个位置删除 \(a_p\) 的最高位，还是用 \(len(a_p)+1\) 的位置删除 \(a_p\)

( \([1,p-1]\) 的部分一定会被删掉)

\(\text{intended solution}\) 采用暴力递归来完成确定每一位的这个操作

1
2
3
4
5
6
7
8
9
10
11
12
13
Function Solve(Limit) Limit为当前可以使用的最高位的1
	求得 B,p
	删除 a[1,p-1]
	删除 a[p]最高位
	if B<=Limit and Solve(p-1) then
		ans[len(a[p]),B]=1
		return True
	删除a[p]
	if B+1<=Limit and Solve(p) then 
		ans[len(a[p])+1,B+1]=1
		return True
	else return False
end

至于复杂度，官方题解给出为 \(O(N)\) 次递归和删除/加入操作，最终复杂度为 \(O(N\log N)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,const T &b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,const T &b){ ((a<b)&&(a=b)); }
char IO;
int rd(){
	int s=0;
	while(!isdigit(IO=getchar()));
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return s;
}

typedef vector <int> V;
const int N=3e5+10,INF=1e9+10;

int n,m,I[N],L;
char s[N];
int fir[N],nxt[N],rk[N],len[N],id[N];
V A[N];

struct Affirmation_Of_My_Existence{
	int s[N<<2],t[N<<2];
	void Down(int p){
		rep(v,p<<1,p<<1|1) t[v]+=t[p],s[v]+=t[p];
		t[p]=0;
	}
	void Upd(int p,int l,int r,int ql,int qr,int x) {
		if(ql>qr) return;
		if(ql<=l && r<=qr) {
			s[p]+=x,t[p]+=x;
			return;
		}
		Down(p);
		int mid=(l+r)>>1;
		if(ql<=mid) Upd(p<<1,l,mid,ql,qr,x);
		if(qr>mid) Upd(p<<1|1,mid+1,r,ql,qr,x);
		s[p]=max(s[p<<1],s[p<<1|1]);
	}
	void Build(int p,int l,int r){ 
		s[p]=len[id[l]]-INF;
		if(l==r) return;
		int mid=(l+r)>>1;
		Build(p<<1,l,mid),Build(p<<1|1,mid+1,r);
	}
	void Add(int x,int k){
		x=rk[x];
		Upd(1,1,m,x,x,INF*k),Upd(1,1,m,x+1,m,k);
	}
	// Find the first critical position "p", and return all the bits in [1,p]
	void Get(int p,int l,int r,int x,V &R){
		if(s[p]<0) return;
		if(l==r) return R.pb(id[l]);
		Down(p);
		int mid=(l+r)>>1;
		Get(p<<1,l,mid,x,R);
		if(s[p<<1]!=x) Get(p<<1|1,mid+1,r,x,R);
	}
} T;

int Solve(int L){
	// L denotes the maxmium bit we can use
	int B=T.s[1];
	if(B<0) return 1;
	if(B>L) return 0;
	V R; T.Get(1,1,m,B,R);
	int p=*R.rbegin(),l=len[p];
	for(int i:R) T.Add(i,-1);
	
	// Try ans B , so we use bit [nxt,B] to delete the number [1,p-1] 
    // and the number a[p] will be set to a[p]-2^l
	if(nxt[p]) T.Add(nxt[p],1);
	if(Solve(l-1)) {
		rep(i,l,B) s[i]=1;
		return B+1;
	}

	// Try ans B+1 , so we use bit [nxt+1,B+1] to delete the [1,p]
	if(nxt[p]) T.Add(nxt[p],-1);
	if(B<L && Solve(l)) {
		rep(i,l+1,B+1) s[i]=1;
		return B+2;
	}
	for(int i:R) T.Add(i,1);
	return 0;
}

int main(){
	rep(i,1,n=rd()) {
		scanf("%s",s); int l=strlen(s);
		cmax(L,l);
		drep(j,l-1,0) if(s[j]=='1') {
			nxt[++m]=fir[i];
			A[len[m]=l-j-1].pb(m);
			fir[i]=m;
		}
	}
	rk[0]=1e9;
	int k=m;
	rep(i,0,L-1) {
		k-=A[i].size();
		sort(A[i].begin(),A[i].end(),[&](int x,int y){ return rk[nxt[x]]<rk[nxt[y]]; });
		for(int j:A[i]) id[rk[j]=++k]=j;
		k-=A[i].size();
	}
	T.Build(1,1,m);
	rep(i,1,n) T.Add(fir[i],1);
	memset(s,0,sizeof s);
	drep(i,Solve(INF)-1,0) putchar(s[i]^48);
}