"ROI 2018 Day 2" no carry addition
Main idea of the title:
Give binary numbers \ (a_1 \ ldots a_n \), for \ (b_1\ldots b_n \)
Meet \ (a_i\leq b_i \), \ (\ bigoplus b_i=\sum b_i \), where $\ bigoplus $is XOR and
Find the minimum value of \ (\ sum b_i \)
Set the length order as \ (N=\sum len(a_i) \)
\(O(N^2-N^3) \), determine each bit of the answer from high to low
The current bit of enumeration is 0 and the following bit is 1. Greedily determine whether there is a scheme
Check whether an answer is legal:
Dynamically maintain an inverted \ (a_i \) set, considering each position from high to low
1. If the current bit is 0:
If there is a number greater than or equal to this bit in \ (a_i \), it is illegal
2. If the current bit is 1:
2-1. If there are 2 numbers with current bit of 1 in \ (a_i \), it is illegal
2-2. If there is exactly one in \ (a_i \), use this 1 for this \ (a_i \), and remove the highest bit of \ (a_i \) and put it back into the set
2-3. Does not exist, use this \ (1 \) to delete the largest \ (a_i \)
In fact, this greed itself is not efficient
Optimization 1: quickly determine the possible range of the highest answer
Make \ (b = \ Max \ {len (a_i) + i-1 \} \)
Then \ (len(Ans)\in[B,B+1] \)
The upper and lower bounds can be obtained by the greedy simulation above
Optimization 2: fast maintenance \ (a_i \) reverse order
Obviously, in the process of continuous change, the current \ (a_i \) must be a suffix of the original \ (a_i \)
Consider sorting all such suffixes. For convenience, use each highest 1 to represent a legal suffix
Obviously, suffixes of the same length can be sorted according to the position of the next 1 in the suffix
That is, a process similar to cardinality sorting. You can maintain the suffix corresponding to the next \ (1 \) in each suffix
Preprocessing complexity is \ (O(N\log N) \)
At the same time, you can also use the segment tree to quickly maintain the insertion / deletion ranking, get the value of \ (B \), and the complexity of a single operation \ (O(\log N) \)
Optimization 3
Call the \ (I \) satisfying \ (len(a_i)+i-1=B \) as \ (\ text{critical number} \)
Make \ (p\) the smallest \ (\text{critical number}\), that is, the first case 2-1 occurs in the process of greed/ 2-2. Location of
Whether the decision answer is \ (B \) or \ (B+1 \), that is, the decision
Delete the highest bit of \ (a_p \) with the position of \ (len(a_p) \), or delete \ (a_p \) with the position of \ (len(a_p)+1 \)
(\ ([1,p-1] \) must be deleted)
\(\ text{intended solution} \) violent recursion is used to complete the operation of determining each bit
Function Solve(Limit) Limit Is the highest 1 currently available Seek B,p delete a[1,p-1] delete a[p]Highest position if B<=Limit and Solve(p-1) then ans[len(a[p]),B]=1 return True delete a[p] if B+1<=Limit and Solve(p) then ans[len(a[p])+1,B+1]=1 return True else return False end
As for complexity.. I don't know
#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); }