企业网站建设需要哪些资料,高端平面设计网站,莱芜,wordpress 页脚声明先放一个大佬的博客#xff1a;「loj - 2850」「ROI 2018 Day 2」无进位加法
用数据结构来优化搜索#x1f914;
神一样的 Kidulthood 考场上就已经意识到了这道题的正解是搜索#x1f605;
考虑搜索过程的本质#x1f914;
首先是找到最小的满足 t i i t_ii tii最大…先放一个大佬的博客「loj - 2850」「ROI 2018 Day 2」无进位加法
用数据结构来优化搜索
神一样的 Kidulthood 考场上就已经意识到了这道题的正解是搜索
考虑搜索过程的本质
首先是找到最小的满足 t i i t_ii tii最大的点 i i i发现对于 p ≠ t i i p\ne t_ii ptii的情况都可以直接回溯掉否则先把 [ 1 , i − 1 ] [1,i-1] [1,i−1]全部删掉然后将其后继插入到序列当中。可以分析出递归的次数其实就是最开始选定的那个串的长度。
那么分两种情况 1.1 1.1 1.1 成功那么其实就不需要回溯了 1.2 1.2 1.2 不成功那么刚开始选定的那个串就会被删掉换句话说是把 [ 1 , i ] [1,i] [1,i]全部删掉
这样复杂度 O ( L log L ) O(L\log L) O(LlogL)。
感性理解 remark \text{remark} remark 这玩意写成代码确实比较抽象。。。
#includebits/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 N6e55;
int n,m,maxL,sz[N],pre[N];
string nums[N];
vectorinteach[N];
pairint,inta[N];
vectorintps[N];
vectorintnxt[N];
int res[N];
setints;
struct node{pairint,intmax;int add;
}t[N2];
void add(int p,int x){t[p].addx,t[p].max.fix;
}
void pushdown(int p){if(t[p].add){add(p1,t[p].add),add(p1|1,t[p].add),t[p].add0;}
}
void pushup(int p){t[p].maxmax(t[p1].max,t[p1|1].max);
}
void build(int p,int l,int r){if(lr){if(a[l].sesz[a[l].fi]-1)t[p].maxmake_pair(pre[l]a[l].se,m-l1),s.insert(l);else t[p].maxmake_pair(pre[l]a[l].se-inf,m-l1);return;}int midlr1;build(p1,l,mid),build(p1|1,mid1,r);pushup(p);
}
void modify(int p,int l,int r,int ql,int qr,int x){if(qlqr)return;if(qllrqr){add(p,x);return;}int midlr1;pushdown(p);if(qlmid)modify(p1,l,mid,ql,qr,x);if(midqr)modify(p1|1,mid1,r,ql,qr,x);pushup(p);
}
void update(int p,int l,int r,int x,int y){if(lr){t[p].max.fiy;return;}int midlr1;pushdown(p);xmid?update(p1,l,mid,x,y):update(p1|1,mid1,r,x,y);pushup(p);
}
int solve(int p){if(t[1].max.fi0)return 1;vectorinttmp;int p2t[1].max.fi,um-t[1].max.se1,cnt0;if(p2p)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 ip2-1;ip2-cnt;i--)res[i]1;int xa[u].fi,ya[u].se,r-1;if(~nxt[x][y]){rps[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(p2p){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);cinn;for(int i1;in;i){cinnums[i],sz[i]nums[i].size(),maxLmax(maxL,sz[i]);ps[i].resize(sz[i]),nxt[i].resize(sz[i]);for(int j0;jsz[i];j)nums[i][j]-0;reverse(nums[i].begin(),nums[i].end());int lst-1;for(int j0;jsz[i];j){if(nums[i][j]1){each[j].pb(i);nxt[i][j]lst;lstj;}}}m0;//基数排序for(int i0;imaxL;i){cnt0;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(seq1,seq1cnt,cmp);for(int j1;jcnt;j){a[m]make_pair(seq[j],i);ps[seq[j]][i]m;}}reverse(a1,a1m);for(int i1;im;i)ps[a[i].fi][a[i].se]i;for(int i1;im;i)pre[i]pre[i-1](a[i].sesz[a[i].fi]-1);build(1,1,m);solve(inf);int tpmaxLn-1;while(tpres[tp]0)tp--;for(int itp;i0;i--)coutres[i];
}
