2021.7.13 提高B组模拟赛

$2021.7.13$ 模拟赛$Ⅱ$
目录：

T1.消息传递
T2.JIH的玩偶
T3.摘取作物
T4.公路维护

$T1：$消息传递

分析：

洛谷有一道这题的弱${}^{10}$化版 $link$
这数据范围：$n<=200000$
先是树形$dp$ $f_i$表示处理以$i$为根的子树最少时间
从大到小排序后 $f_i$可以直接求出 $f_i=max(f_i,a_i+i)$ 把这个交到洛谷就过了
再考虑换根$dp$
$g_i$表示除$i$这棵子树后 其他部分以$i$的父亲为根的整棵树的答案
$g_i$已经求出 应该从通过$i$求出每个儿子的$g$

将所有的儿子和自己的$g$值排序后 考虑删掉中间的一个$x$后的答案
这个时候$x$以前的数的$rank$不变 $x$后面的数的$rank$要$-1$

所以预处理一个前缀和后缀的$max$ 表示前$i$个 或后$i$个数中 $f_j+ran{k}_j$的最小值 $j$的$g$值就可以通过$max(pr{e}_{x-1},su{f}_{x+1}-1)$ 得出

CODE：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#pragma GCC optimize(2)
using namespace std;
const int N=2e5+5;
int n,m,x,head[N],tot,f[N],pre[N],suf[N];
int ans=N+1,query[N],g[N];
struct qaq{int x,val;
}a[N];
struct node{int to,next;
}edge[N<<1];
void add(int x,int y)
{edge[++tot]=(node){y,head[x]};head[x]=tot;
}
bool cmp(qaq x,qaq y){return x.val>y.val;}
inline void dp(int x,int fa)
{for(int i=head[x];i;i=edge[i].next){int qwq=edge[i].to;if(qwq==fa) continue;dp(qwq,x);}int cnt=0;for(register int i=head[x];i;i=edge[i].next){int qwq=edge[i].to;if(fa==qwq) continue;a[++cnt]=qaq{qwq,f[qwq]};}sort(a+1,a+cnt+1,cmp);for(int i=1;i<=cnt;i++)f[x]=max(f[x],a[i].val+i);  //推出f
}
inline void work(int x,int fa)
{int cnt=0;if(x!=1) a[++cnt]=qaq{-1,g[x]};  //rank要-1for(int i=head[x];i;i=edge[i].next){int qwq=edge[i].to;if(qwq==fa) continue;a[++cnt]=qaq{qwq,f[qwq]};}sort(a+1,a+cnt+1,cmp);pre[0]=suf[cnt+1]=0;for(int i=1;i<=cnt;i++)pre[i]=max(pre[i-1],a[i].val+i);for(int i=cnt;i>=1;i--)suf[i]=max(suf[i+1],a[i].val+i-1);//处理前缀后缀for(int i=1;i<=cnt;i++){int qwq=a[i].x;if(qwq>0) g[qwq]=max(pre[i-1],suf[i+1]);  //推出g}if(ans>pre[cnt]) ans=pre[cnt],m=0;if(ans==pre[cnt]) query[++m]=x;for(int i=head[x];i;i=edge[i].next){int qwq=edge[i].to;if(qwq==fa) continue;work(qwq,x);}
}
int main(){
//	freopen("news.in","r",stdin);
//	freopen("news.out","w",stdout);scanf("%d",&n);for(register int i=2;i<=n;i++){scanf("%d",&x);add(x,i);add(i,x);}dp(1,0);work(1,0);sort(query+1,query+m+1);printf("%d\n",ans+1);for(int i=1;i<=m;i++)printf("%d ",query[i]);	return 0;
} 

$T2：JIH$的玩偶

分析：

因为只有从$x$到$root$ 那就直接倍增
用类似$RMQ$的倍增维护$father,max,min$以及差
最后就倍增跳 每次取最大值和最小值的差 再更新父节点 就行了

CODE：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=2e5+5;
int fa[20][N],minn[20][N],maxn[20][N],k[20][N],n,T;
int main(){
//	freopen("tree.in","r",stdin);
//	freopen("tree.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&maxn[0][i]);minn[0][i]=maxn[0][i];}for(int i=1,x,y;i<n;i++){scanf("%d%d",&x,&y);fa[0][x]=y;}for(int i=1;i<=18;i++)for(int j=1;j<=n;j++){int qwq=fa[i-1][j];fa[i][j]=fa[i-1][qwq];maxn[i][j]=max(maxn[i-1][j],maxn[i-1][qwq]);  //最大值minn[i][j]=min(minn[i-1][j],minn[i-1][qwq]);  //最小值k[i][j]=max(max(k[i][j],maxn[i-1][qwq]-minn[i-1][j]),max(k[i-1][qwq],k[i-1][j]));  //差值}scanf("%d",&T);while(T--){int x,y,res=0x3f3f3f3f,ans=0;scanf("%d%d",&x,&y);for(int i=0;y;i++,y>>=1)if(y&1){ans=max(ans,max(k[i][x],maxn[i][x]-res));  //取最后差值res=min(res,minn[i][x]);x=fa[i][x];  //更新fa}printf("%d\n",ans);}return 0;
} 

$T3：$摘取作物

分析：

网络流费用流
每个点向它的行列连边 源点向每行连 汇点向每列连

$S$到左边$n$个点容量$2$ 费用$0$
右边$m$个点到$T$ 容量$2$ 费用$0$

因为

中间$n$到$m$ 容量为$1$ 费用为$w_{i,j}$
用$spfa$判断流通 然后跑最大费用增广路 直到没有增广路

CODE：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=(35<<1);
int n,m,S,T,w[N][N],f[N][N],ans;
int vis[N],dis[N],pre[N],G[N][N],q[N*10];
int spfa()
{memset(dis,138,sizeof(dis));memset(vis,0,sizeof(vis));int head=0,tail=1;q[1]=S;dis[S]=0;vis[S]=1;while(head<=tail){head++;int qwq=q[head];for(int i=1;i<=T;i++){if(qwq^i&&f[qwq][i]&&dis[qwq]+G[qwq][i]>dis[i]){pre[i]=qwq;dis[i]=dis[qwq]+G[qwq][i];if(!vis[i]){vis[i]=1;q[++tail]=i;}}vis[qwq]=0;}}if(dis[T]<0) return 0;int res=0x3f3f3f3f,qwq=T;while(qwq^S){res=min(res,f[pre[qwq]][qwq]);qwq=pre[qwq];}qwq=T;while(qwq^S){f[pre[qwq]][qwq]-=res;f[qwq][pre[qwq]]+=res;qwq=pre[qwq];}ans+=dis[T];return 1;
}
int main(){
//	freopen("pick.in","r",stdin);
//	freopen("pick.out","w",stdout);scanf("%d%d",&n,&m);S=n+m+1;T=n+m+2;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){scanf("%d",&w[i][j]);f[i][j+n]=1;  //中间n到mG[i][j+n]=w[i][j];  //费用G[j+n][i]=-w[i][j];}for(int i=1;i<=n;i++)f[S][i]=2;  //源点到左边for(int i=n+1;i<=n+m;i++)f[i][T]=2;  //右边到汇点while(spfa());printf("%d",ans);return 0;
} 

$T4：$公路维护

分析：

显然数据结构了 那就线段树

维护两个$lazyTag$ 加值和最大值 加值的优先级更大
其余就是每种情况 的线段树操作了

操作$1$要先看区间是不是能走的 再减 看减完有没有$<=0$的 就把这段区间标为$inf$

CODE：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+5;
int n,m,I,ans;
struct SegmentTree{int lazyA,valA,lazyX,valX;bool broken;
}a[N<<2],qwq;
void up(SegmentTree &a,SegmentTree &b,SegmentTree &c)
{if(c.valA<b.valA) a.valA=c.valA,a.valX=c.valX;else a.valA=b.valA,a.valX=b.valX;a.broken=b.broken&c.broken;
}
void down(int x)
{a[x<<1].lazyA=max(a[x<<1].lazyA+a[x].lazyX,a[x].lazyA);a[x<<1|1].lazyA=max(a[x<<1|1].lazyA+a[x].lazyX,a[x].lazyA);a[x<<1].valA=max(a[x<<1].valA+a[x].lazyX,a[x<<1].lazyA);a[x<<1|1].valA=max(a[x<<1|1].valA+a[x].lazyX,a[x<<1|1].lazyA);a[x<<1].lazyX+=a[x].lazyX;a[x<<1|1].lazyX+=a[x].lazyX;a[x].lazyA=-0x3f3f3f3f;a[x].lazyX=0;
}
void build(int x,int l,int r)
{if(l==r){a[x].valA=I;a[x].valX=l;a[x].broken=1;a[x].lazyA=-0x3f3f3f3f;return;}int mid=(l+r)>>1;build(x<<1,l,mid);build(x<<1|1,mid+1,r);up(a[x],a[x<<1],a[x<<1|1]);
}
bool check(int x,int l,int r,int L,int R)  //看这段路能不能走
{if(L==l&&r==R) return a[x].broken;down(x);int mid=(l+r)>>1;bool res=1;if(R<=mid) res=check(x<<1,l,mid,L,R);else if(mid<L) res=check(x<<1|1,mid+1,r,L,R);else res=check(x<<1,l,mid,L,mid)&check(x<<1|1,mid+1,r,mid+1,R);up(a[x],a[x<<1],a[x<<1|1]);return res;
}
void add(int x,int l,int r,int L,int R,int val)  //加值
{if(L==l&&r==R){a[x].valA+=val;a[x].lazyX+=val;a[x].lazyA+=val;return;}down(x);int mid=(l+r)>>1;if(R<=mid) add(x<<1,l,mid,L,R,val);else if(mid<L) add(x<<1|1,mid+1,r,L,R,val);else add(x<<1,l,mid,L,mid,val),add(x<<1|1,mid+1,r,mid+1,R,val);up(a[x],a[x<<1],a[x<<1|1]);
}
void Repare(int x,int l,int r,int L,int R,int val)  //修复这段路
{if(L==l&&r==R){a[x].lazyA=max(a[x].lazyA,val);a[x].valA=max(a[x].valA,a[x].lazyA);return;}down(x);int mid=(l+r)>>1;if(R<=mid) Repare(x<<1,l,mid,L,R,val);else if(mid<L) Repare(x<<1|1,mid+1,r,L,R,val);else Repare(x<<1,l,mid,L,mid,val),Repare(x<<1|1,mid+1,r,mid+1,R,val);up(a[x],a[x<<1],a[x<<1|1]);
}
void UnRet(int x,int l,int r,int p)  //这段路不可修复
{if(l==r){a[x].valA=0x3f3f3f3f;a[x].broken=0;return;}down(x);int mid=(l+r)>>1;if(p<=mid) UnRet(x<<1,l,mid,p);else UnRet(x<<1|1,mid+1,r,p);up(a[x],a[x<<1],a[x<<1|1]);
}
void found(int x,int l,int r,int L,int R)  //看区间内有没有不能走的
{if(L==l&&r==R){if(!qwq.valX) qwq=a[x];else if(a[x].valA<qwq.valA) qwq=a[x];return;}down(x);int mid=(l+r)>>1;if(R<=mid) found(x<<1,l,mid,L,R);else if(mid<L) found(x<<1|1,mid+1,r,L,R);else found(x<<1,l,mid,L,mid),found(x<<1|1,mid+1,r,mid+1,R);up(a[x],a[x<<1],a[x<<1|1]);
}
int main(){
//	freopen("road.in","r",stdin);
//	freopen("road.out","w",stdout);scanf("%d%d%d",&n,&m,&I);build(1,1,n);int E=n;while(m--){int op,l,r,x;scanf("%d%d%d%d",&op,&l,&r,&x);if(op==1){if(check(1,1,n,l,r)){ans++;add(1,1,n,l,r,-x);while(E){qwq.valX=0;found(1,1,n,l,r);if(qwq.valA<=0&&qwq.lazyA<=0)UnRet(1,1,n,qwq.valX);else break;E--;}}continue;}if(op==2){add(1,1,n,l,r,x);continue;}if(op==3){Repare(1,1,n,l,r,x);continue;}}printf("%d",ans);return 0;
}