集训
DAY1 搜索进阶
因此在学习的时候主要以代码实践为主（多做题）
深度优先搜索（dfs）基础
1.子集枚举
复杂度\(O(2^n)\)
2.排列枚举
复杂度\(O(n!)\)
Dfs的剪枝
1.优化搜索顺序
sort
枚举顺序（正/倒）
2.排除等效冗余
inline void dfs(int i,int len,int st){//P1120
if(i==cnt+1)...
if(len==tar)...
for(int j=st/*限制单调*/;j<=n;j++){
if(!vis[j]&&len+a[j]<=tar){
...
if(len==0||len+a[j]==tar)return;//排除等效冗余
j=nxt[j];
}
}
}
int main(){
...
nxt[n]=n;
for(int i=n-1;i>=1;i--){//避免重复
if(a[i]!=a[i+1])nxt[i]=i;
else nxt[i]=nxt[i+1];
}
...
}
3.可行性剪枝（上下界剪枝） 当前分支必定失败
void dfs(int i,int lh,int lr,int sums,int sumv){//P1731 //P1025
...
if(sumv>=n)return;//可行性
if(i*lr*lr*lh+sumv<n)return;
if(i*2+sums>=ans)return;
for(int j=lr-1;j>=i;j--)//上下界
for(int k=lh-1;k>=i;k--)
...
}
4.最优性剪枝 答案不会更优
if(...)return;//P10483 P1731
5.记忆化
迭代加深
搜索规模随搜索层数深入增长很快，且能够确保答案在较浅节点
思想：限制深度
bool dfs(int i){
if(i==dep){
return ...;
}
for...{if(...){return 1;}}
return 0;
}
void solve(){
dep=1;
while(!dfs(1)){
dep++;
}
}//uva529
P1763
hack
双向搜索
具有明确的“初始状态”和“终止状态”
从初态和终态出发各搜一半状态，产生两个深度减半的状态空间，在中间交会、组合成最终答案。\(O(2^\frac{n}{2})\)
//CF888E U311043
void dfs1(int i)...
void dfs2(int i)...
void solve()...
int main(){
dfs1();dfs2();solve();
}
广度优先搜索（BFS）基础
U311287
大模拟
struct传参太多会TLE
3维状态
U311289
多个源点同时入队
BFS变形
1.双端队列BFS（0/1bfs）
deque
0费入队首，1费入队尾
2.优先队列BFS
uva11367
定义状态\((city,cost,left)\)
dijkstra转移状态
优先队列使得\(cost\)最小
二维状态判重
void solve(){
int c=read(),s=read()+1,e=read()+1;
memset(vis,0,sizeof vis);
memset(f,0x3f,sizeof(f));
f[s][0]=0;
priority_queue<node>q;
q.push(node{s,0,0});
while(!q.empty()){
node now=q.top();
q.pop();
if(now.u==e){
cout<<now.cot<<"\n";
return;
}
if(vis[now.u][now.res])continue;
else vis[now.u][now.res]=1;
if(now.res<c&&f[now.u][now.res+1]>now.cot+val[now.u]){
f[now.u][now.res+1]=now.cot+val[now.u];
q.push(node{now.u,f[now.u][now.res+1],now.res+1});
}
for(int j=0;j<(int)a[now.u].size();j++){
int v=a[now.u][j].v,w=a[now.u][j].w;
if(now.res>=w&&f[v][now.res-w]>now.cot){
f[v][now.res-w]=now.cot;
q.push(node{v,f[v][now.res-w],now.res-w});
}
}
}
puts("impossible");
}
3.双向BFS
acwing177
大量细节
开两个队列q1，q2
每单位时间q1拓展三次，q2一次
若两者有相同可到达点即输出当前时间
拓展时打上第几次标记
拓展时打vis标记
多测清空
判段是否在鬼区内
void bfs(){
int tim=0,pre=1,pre2=1;
memset(vis,0,sizeof(vis));
memset(vis2,0,sizeof(vis2));
queue<node>q1;
queue<node>q2;
q1.push(node{bx,by,1});
q2.push(node{gx,gy,1});
while((!q1.empty())&&(!q2.empty())){
tim++;
for(int i=1;i<=3;i++){
while(!q1.empty()&&q1.front().t==pre){
node now=q1.front();
q1.pop();
if(!check(now.x,now.y,tim))continue;
for(int j=0;j<4;j++){
int tx=now.x+dx[j],ty=now.y+dy[j];
if(tx>0&&tx<=n&&ty>0&&ty<=m&&check(tx,ty,tim)&&a[tx][ty]!='X'){
if(vis2[tx][ty]){
cout<<tim<<"\n";
return;
}
if(vis[tx][ty])continue;
else vis[tx][ty]=1;
q1.push(node{tx,ty,pre+1});
}
}
}
pre++;
}
while(!q2.empty()&&q2.front().t==pre2){
node now=q2.front();
q2.pop();
if(!check(now.x,now.y,tim))continue;
for(int j=0;j<4;j++){
int tx=now.x+dx[j],ty=now.y+dy[j];
if(tx>0&&tx<=n&&ty>0&&ty<=m&&check(tx,ty,tim)&&a[tx][ty]!='X'){
if(vis[tx][ty]){
cout<<tim<<"\n";
return;
}
if(vis2[tx][ty])continue;
else vis2[tx][ty]=1;
q2.push(node{tx,ty,pre2+1});
}
}
}
pre2++;
}
puts("-1");
}
DAY2-3 数据结构提高
单调栈
//P5788
stack<int>st;
for(int i=1;i<=n;i++){
while(!st.empty()&&h[i]>h[st.top()])st.pop();
st.push(i);
}
while(!st.empty())st.pop();
分治+单调栈
摆
某计蒜客题
摆
P1823
在单调栈内二分
SP1805
经典
单调队列
deque<int>q;
for(int i=1;i<=n;i++){
while(!q.empty()&&q.front()<i-m)q.pop_front();
...
while(!q.empty()&&a[q.back()]>=a[i])q.pop_back();
q.push_back(i);
}//P1440
P2216
二维
堆
void push(int x){//P3378
heap[++len]=x;
int i=len;
while(i>1&&heap[i/2]>heap[i]){
swap(heap[i/2],heap[i]);
i=i/2;
}
}
void pop(){
heap[1]=heap[len--];
int i=1;
while(i*2<=len){
int son=i*2;
if(son+1<=len&&heap[son]>heap[son+1])son++;
if(heap[son]<heap[i]){
swap(heap[son],heap[i]);
i=son;
}else break;
}
}
int ask(){return heap[1];}
左偏树
\(dist\)定义：一个节点到子树中最近的外节点所经过的边的数量，\(dist[0]=-1\)
维护\(dist\)以维护左偏性质
左偏树的深度没有保证
int find(int i){return f[i]==i?i:f[i]=find(f[i]);}//P3377
int merge(int i,int j){
if(!i||!j)return i|j;//节点为0
if(a[j].val<a[i].val)swap(i,j);//维护堆
a[i].rs=merge(a[i].rs,j);//递归合并右子和另一个堆
if(a[a[i].rs].dist>a[a[i].ls].dist)swap(a[i].ls,a[i].rs);//维护左偏
a[i].dist=a[a[i].rs].dist+1;//维护dist
return i;//返回节点
}
void init(){
a[0].dist=-1;
scanf("%d",&a[i].val);
a[i].id=f[i]=i;
a[i].ls=a[i].rs=a[i].dist=a[i].dead=0;
}
int main(){
//合并 插入
if(a[x].dead||a[y].dead)continue;
int fx=find(x),fy=find(y);
if(fx!=fy)f[fx]=f[fy]=merge(fx,fy);
//删除根
if(a[x].dead)continue;
int fx=find(x);a[fx].dead=1;
f[fx]=f[a[fx].ls]=f[a[fx].rs]=merge(a[fx].ls,a[fx].rs);
}
P4331
摆
基础 STL
注意：
1.区间左闭右开 [,)
2.deque->MLE
pair
默认排序先first后second
vector
t.emplace_back()//新插入方式
t.resize()//重置大小
//定点插入删除元素
v.insert(a.begin()+i,j)//在v的第i个元素位置插入j(从0开始)
v.erase(a.begin(),a.begin()+i)//删除 v 的 第0~第i-1个元素
set (multiset)
去重(不去重)
s.erase(pos)//删除pos迭代器所指向的元素，返回下一个迭代器的位置
s.erase(x)//为删除set中值为x的元素
//注意：multiset执行该操作会删除所有=x的元素，如果只想删除一个则应用s.erase(s.find(x))
s.find(x)//查找 x 元素是否存在，如果存在返回该元素的迭代器，若不存在，返回s.end()，用法 auto pos=s.find(x)
s.count(x)//查找 x 元素的个数，用于 multiset，复杂度很高，为O(ans+logn)
s.lower_bound(x)//返回第一个 >= x 的元素的迭代器
s.upper_bound(x)//返回第一个 > x 的元素的迭代器
nth_element()
平均O(n)的时间复杂度，将数组中第k小的元素放到第k个位置上，同时保证左边元素全部小于它，右边元素全部大于它。
//用法 (a数组下标从1开始，将第i小的元素放到第i个位置)
nth_element(a+1,a+i,a+n+1,cmp);
lower_bound()
返回第一个>=x位置下标
upper_bound()
返回第一个>x位置下标
使用前保证单调性！sort
//用法
int p=lower_bound(a+1,a+n+1,x,cmp);
map
map<T,T>mp;//T必须已定义大小比较
bitset
优化传递闭包，背包 \(O(\frac{n}{w})\)
bitset<size>b;
树状数组
1.单点修改，区间查询
int lowbit(int i){return i&(-i);}//P3374
int sum(int i){
int ret=0;
while(i){
ret+=c[i];
i-=lowbit(i);
}
return ans;
}
void add(int i,int val){
while(i<=n){
c[i]+=val;
i+=lowbit(i);
}
}
2.区间修改，单点查询
维护原序列的差分序列
线段树
注意：四倍空间
void pushup(int p){
...
}
void update(int p,int pl,int pr,...){
if(pl==pr){
...
return;
}
if(...)update(ls,pl,mid,...);
if(...)update(rs,mid+1,pr,...);
pushup(p);
}
int query(int l,int r,int p,int pl,int pr){
if(l<=pl&&pr<=r){
return ...;
}
int ret=0;
if(l<=mid)...
if(r>mid)...
return ret;
}
P4513
经典
LOJ6029
除法转化为减法,暴力更新
void updatediv(int l,int r,int p,int pl,int pr,int k){
if(l<=pl&&pr<=r){
ll n1=floor(1.0*t[p].maxn/k)-t[p].maxn;
ll n2=floor(1.0*t[p].minn/k)-t[p].minn;
if(pl==pr){
t[p].sum=t[p].maxn=t[p].minn=floor(1.0*t[p].minn/k);
}else if(n1==n2){
t[p].tag+=n1;
t[p].maxn+=n1;
t[p].minn+=n1;
t[p].sum+=n1*(pr-pl+1);
}else{
pushdown(p,pl,pr);
updatediv(l,r,ls,pl,mid,k);
updatediv(l,r,rs,mid+1,pr,k);
pushup(p);
}
return;
}
pushdown(p,pl,pr);
if(l<=mid)updatediv(l,r,ls,pl,mid,k);
if(r>mid)updatediv(l,r,rs,mid+1,pr,k);
pushup(p);
}
不开long long见祖宗
P3369
值域线段树&动态开点线段树
void pushup(int p){
val[p]=val[ls]+val[rs];
}
void add(int &p,int pl,int pr,int pos,int k){//数pos的个数增加k
if(!p)p=++cnt;
if(pl==pr){
val[p]+=k;
return;
}
if(pos<=mid)add(ls,pl,mid,pos,k);
else if(pos>mid)add(rs,mid+1,pr,pos,k);
pushup(p);
}
int query(int l,int r,int p,int pl,int pr){//返回[l,r]数的个数
if(!p)return 0;
if(l<=pl&&pr<=r)return val[p];
int ans=0;
if(l<=mid)ans+=query(l,r,ls,pl,mid);
if(r>mid)ans+=query(l,r,rs,mid+1,pr);
return ans;
}
int getrank(int k,int p,int pl,int pr){//查询第k大的数
if(pl==pr)return pl;
if(val[ls]>=k)return getrank(k,ls,pl,mid);
else return getrank(k-val[ls],rs,mid+1,pr);
}
//插入一个数x
add(rt,-lim,lim,x,1);
//删除一个数x(若有多个相同的数，应只删除一个)
add(rt,-lim,lim,x,-1);
//定义排名为比当前数小的数的个数+1,查询x的排名
query(-lim,x-1,rt,-lim,lim)+1
//查询数据结构中排名为x的数
getrank(x,rt,-lim,lim)
//求x的前驱(前驱定义为小于x，且最大的数)
int rk=query(-lim,x-1,rt,-lim,lim);
getrank(rk,rt,-lim,lim)
//求x的后继(后继定义为大于x，且最小的数)
int rk=query(-lim,x,rt,-lim,lim)+1;
getrank(rk,rt,-lim,lim)
P4198
序列\(a\)，可修改，查询满足\({\forall}j{\in}[1,i-1],a[i]>a[j]\)的\(i\)个数
复杂度\(O(nlog^2n)\)
int query(int p,int pl,int pr,double K){//返回p节点内>k的个数
if(pl==pr){
return t[p].maxn>K;
}
if(t[ls].maxn>K)return query(ls,pl,mid,K)+t[p].len-t[ls].len;//递归左子+右子贡献
else return query(rs,mid+1,pr,K);//左子无贡献，递归右子
}
void pushup(int p,int pl,int pr){
t[p].maxn=max(t[ls].maxn,t[rs].maxn);
t[p].len=t[ls].len+query(rs,mid+1,pr,t[ls].maxn);//左子不受影响+右子>左子最大值
}
void update(int pos,int p,int pl,int pr,double K){
if(pl==pr){
t[p].len=1;
t[p].maxn=K;
return;
}
if(pos<=mid)update(pos,ls,pl,mid,K);
else update(pos,rs,mid+1,pr,K);
pushup(p,pl,pr);
}
update(x,1,1,n,tmp);
t[1].len
P4556
值域线段树+树上差分+线段树合并
int merge(int p,int i,int pl,int pr){//合并
if(!p||!i)return p|i;
if(pl==pr){
...
return p;
}
//合并左右子树
ls=ch[i][0]=merge(ls,ch[i][0],pl,mid);
rs=ch[i][1]=merge(rs,ch[i][1],mid+1,pr);
pushup(p);
return p;
}
void getans(int i,int fa){//自下而上合并
for(int j=0;j<a[i].size();j++){
int v=a[i][j];
if(v!=fa){
getans(v,i);
rt[i]=rt[v]=merge(rt[i],rt[v],1,1e5);//更改根节点
}
}
//统计答案
ans[i]=maxn[rt[i]];
if(!sum[rt[i]])ans[i]=0;//特判
}
P4197
线段树合并
在每个点建一颗线段树,加入离散化后的点权
离线询问，按\(x\)排序
将边按边权排序，枚举每个询问，加边,合并线段树
注意数组大小
输出回车
CF786B
线段树优化建图
一棵入树，一棵出树，节点标号偏移\(D\)
\(D\)由数据范围确定
void build(int p,int pl,int pr){
if(pl==pr){
a[pl]=p;//获取节点i对应的树上节点a[i]
return;
}
//出树向父节点连边
e[ls+D].push_back(edge{p+D,0});
e[rs+D].push_back(edge{p+D,0});
//入树向子节点连边
e[p].push_back(edge{ls,0});
e[p].push_back(edge{rs,0});
build(ls,pl,mid);
build(rs,mid+1,pr);
}
void connect(int l,int r,int v,ll w,int p,int pl,int pr,int op){
if(l<=pl&&pr<=r){
//出树向入树连边
if(op)e[p+D].push_back(edge{a[v],w});
else e[a[v]/*注意转换*/+D].push_back(edge{p,w});
return;
}
if(l<=mid)connect(l,r,v,w,ls,pl,mid,op);
if(r>mid)connect(l,r,v,w,rs,mid+1,pr,op);
}
void init(){
build(1,1,n);
for(int i=1;i<=n;i++){
//出树和入树的叶子节点是同一节点
e[a[i]/*注意转换*/].push_back(edge{a[i]/*注意转换*/+D,0});
e[a[i]/*注意转换*/+D].push_back(edge{a[i]/*注意转换*/,0});
}
}
//单点
e[a[v]+D].push_back(edge{a[u],w});
//单点->区间&区间->单点
connect(l,r,v,w,1,1,n,op%2);
//注意图上节点向树上节点编号转换 i->a[i] 在dijkstra时以及答案统计和输出时
trie
P5283 摆
P4551
void insert(int s){
int p=0;
for(int i=(1<<30);i>0;i>>=1){
bool t=s&i;//注意bool
if(!ch[p][t])ch[p][t]=++id;
p=ch[p][t];
}
cnt[p]++;
}
int ask(int s){
int p=0,ret=0;
for(int i=(1<<30);i>0;i>>=1){
bool t=s&i;
if(ch[p][!t]){
ret+=i;
p=ch[p][!t];
}else p=ch[p][t];
}
return ret;
}
//d[i]为树上异或前缀
insert(d[i]);
ans=max(ans,ask(d[i]));