【学习笔记】「ROI 2018 Day 2」无进位加法

先放一个大佬的博客：「loj - 2850」「ROI 2018 Day 2」无进位加法

用数据结构来优化搜索🤔

神一样的 Kidulthood 考场上就已经意识到了这道题的正解是搜索😅

考虑搜索过程的本质🤔

首先是找到最小的满足$t_i+i$最大的点$i$，发现对于$p\ne t_i+i$的情况都可以直接回溯掉，否则先把$[1,i-1]$全部删掉，然后将其后继插入到序列当中。可以分析出递归的次数其实就是最开始选定的那个串的长度。

那么分两种情况：

$1.1$ 成功，那么其实就不需要回溯了
$1.2$ 不成功，那么刚开始选定的那个串就会被删掉（换句话说是把$[1,i]$全部删掉）

这样复杂度$O(L\log L)$。

感性理解

$\text{remark}$ 这玩意写成代码确实比较抽象。。。

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pb push_back
#define db double
#define inf 0x3f3f3f3f
using namespace std;
const int N=6e5+5;
int n,m,maxL,sz[N],pre[N];
string nums[N];
vector<int>each[N];
pair<int,int>a[N];
vector<int>ps[N];
vector<int>nxt[N];
int res[N];
set<int>s;
struct node{pair<int,int>max;int add;
}t[N<<2];
void add(int p,int x){t[p].add+=x,t[p].max.fi+=x;
}
void pushdown(int p){if(t[p].add){add(p<<1,t[p].add),add(p<<1|1,t[p].add),t[p].add=0;}
}
void pushup(int p){t[p].max=max(t[p<<1].max,t[p<<1|1].max);
}
void build(int p,int l,int r){if(l==r){if(a[l].se==sz[a[l].fi]-1)t[p].max=make_pair(pre[l]+a[l].se,m-l+1),s.insert(l);else t[p].max=make_pair(pre[l]+a[l].se-inf,m-l+1);return;}int mid=l+r>>1;build(p<<1,l,mid),build(p<<1|1,mid+1,r);pushup(p);
}
void modify(int p,int l,int r,int ql,int qr,int x){if(ql>qr)return;if(ql<=l&&r<=qr){add(p,x);return;}int mid=l+r>>1;pushdown(p);if(ql<=mid)modify(p<<1,l,mid,ql,qr,x);if(mid<qr)modify(p<<1|1,mid+1,r,ql,qr,x);pushup(p);
}
void update(int p,int l,int r,int x,int y){if(l==r){t[p].max.fi+=y;return;}int mid=l+r>>1;pushdown(p);x<=mid?update(p<<1,l,mid,x,y):update(p<<1|1,mid+1,r,x,y);pushup(p);
}
int solve(int p){if(t[1].max.fi<=0)return 1;vector<int>tmp;int p2=t[1].max.fi,u=m-t[1].max.se+1,cnt=0;if(p2>p)return 0;while(*s.begin()!=u){cnt++;int cur=*s.begin();modify(1,1,m,cur,m,-1);update(1,1,m,cur,-inf);tmp.pb(cur);s.erase(cur);}modify(1,1,m,u,m,-1);update(1,1,m,u,-inf);s.erase(u);for(int i=p2-1;i>=p2-cnt;i--)res[i]=1;int x=a[u].fi,y=a[u].se,r=-1;if(~nxt[x][y]){r=ps[x][nxt[x][y]];modify(1,1,m,r,m,1);update(1,1,m,r,inf);s.insert(r);}if(solve(p2-1-cnt))return res[p2-cnt-1]=1;if(~r){modify(1,1,m,r,m,-1);update(1,1,m,r,-inf);s.erase(r);}if(p2==p){for(auto cur:tmp){modify(1,1,m,cur,m,1);update(1,1,m,cur,inf);s.insert(cur);}modify(1,1,m,u,m,1);update(1,1,m,u,inf);s.insert(u);return 0;}res[p2]=1;return solve(p2-cnt);
}
int low[N],seq[N],cnt;
bool cmp(int x,int y){return low[x]<low[y];
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>nums[i],sz[i]=nums[i].size(),maxL=max(maxL,sz[i]);ps[i].resize(sz[i]),nxt[i].resize(sz[i]);for(int j=0;j<sz[i];j++)nums[i][j]-='0';reverse(nums[i].begin(),nums[i].end());int lst=-1;for(int j=0;j<sz[i];j++){if(nums[i][j]==1){each[j].pb(i);nxt[i][j]=lst;lst=j;}}}m=0;//基数排序for(int i=0;i<maxL;i++){cnt=0;for(auto e:each[i]){low[e]=(nxt[e][i]==-1)?0:ps[e][nxt[e][i]];if(nums[e][i]==1)low[e]+=inf;seq[++cnt]=e;}sort(seq+1,seq+1+cnt,cmp);for(int j=1;j<=cnt;j++){a[++m]=make_pair(seq[j],i);ps[seq[j]][i]=m;}}reverse(a+1,a+1+m);for(int i=1;i<=m;i++)ps[a[i].fi][a[i].se]=i;for(int i=1;i<=m;i++)pre[i]=pre[i-1]+(a[i].se==sz[a[i].fi]-1);build(1,1,m);solve(inf);int tp=maxL+n-1;while(tp&&res[tp]==0)tp--;for(int i=tp;i>=0;i--)cout<<res[i];
}