8.17 CSP 模拟 23
That's Why You Go Away - Michael Learns To Rock
Baby won't you tell me why
there is sadness in your eyes
I don't wanna say goodbye to you
Love is one big illusion
I should try to forget
But there is something left in my head
You're the one who set it up
Now you're the one to make it stop
I'm the one who's feeling lost right now
Now you want me to forget every little thing you said
But there is something left in my head
I won't forget the way you're kissing
The feelings so strong were lasting for so long
But I'm not the man your heart is missing
That's why you go away I know
You were never satisfied, no matter how I tried
Now you wanna say goodbye to me
Love is one big illusion, I should try to forget
But there is something left in my head
I won't forget the way you're kissing
The feelings so strong were lasting for so long
But I'm not the man your heart is missing
That's why you go away I know
Sitting here all alone in the middle of nowhere
Don't know which way to go
There ain't so much to say now between us
There ain't so much for you
There ain't so much for me anymore
I won't forget the way you're kissing
The feelings so strong were lasting for so long
But I'm not the man your heart is missing
That's why you go away I know
That's why you go away I know
\(\text{happyguy round}\)
T1 电压
要求删除一条边使得原图成为二分图，且删去的边必须在这个二分图的同一部中。充要条件是删去的边必须在所有奇环中，必须不在任何偶环中。
除了只有一个奇环的情况可以删去这条返祖边外，可能的边一定是 DFS 树的树边。
对每条返祖边考虑，进行树上差分的操作。
现在证明为什么不要考虑多条返祖边构成的环，先证明两条返祖边构成的环不会被考虑，同样方法可以归纳到多条边。
-
一个更大的奇环一定是由一个奇环的返祖边和一个偶环的返祖边组成。如果不统计这个大奇环并不会影响合法答案（总数和各自计数都没有统计），而被偶环包含的树边一定会被这个偶环判定为不合法。
-
一个更大的偶环一定是由两个奇环的返祖边或两个偶环的返祖边组成。对于前者，被偶环包括在内的树边一定不在两个奇环的交，因此不会影响答案；对于后者，两个小偶环就可以判定不合法。
点击查看代码
int n,m;
struct edge{
int to,nxt;
}e[maxm<<1];
int head[maxn],cnt;
inline void add_edge(int u,int v){
e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
e[++cnt].to=u,e[cnt].nxt=head[v],head[v]=cnt;
}
bool vis[maxn];
int pre[maxn],dep[maxn];
int tot[maxn][2];
void dfs(int u,int d,int pre){
vis[u]=true;
dep[u]=d;
for(int i=head[u],v;i;i=e[i].nxt){
v=e[i].to;
if((i^1)==pre) continue;
if(!vis[v]){
dfs(v,d+1,i);
tot[u][0]+=tot[v][0],tot[u][1]+=tot[v][1];
}
else{
if(dep[u]<dep[v]) continue;
if((dep[u]-dep[v])&1) ++tot[u][0],--tot[v][0];
else{
++tot[0][1];
++tot[u][1],--tot[v][1];
}
}
}
}
int ans;
int main(){
n=read(),m=read();
cnt=1;
for(int i=1;i<=m;++i){
int u=read(),v=read();
add_edge(u,v);
}
for(int i=1;i<=n;++i){
if(!vis[i]) dfs(i,0,0);
}
for(int i=1;i<=n;++i){
if(!dep[i]) continue;
if(tot[i][1]==tot[0][1]&&!tot[i][0]) ++ans;
}
if(tot[0][1]==1) ++ans;
printf("%d\n",ans);
return 0;
}
T2 农民
判断过程是如果向左儿子要求小于当前的值，向右儿子要求大于当前的值，那么可以对所有向左儿子的节点权值求 \(\min\)，对所有向右儿子的节点权值求 \(\max\)，只需要判断这两个信息即可。
这样容易树链剖分线段树维护，翻转操作就是给子树内除本身外的节点交换左右儿子身份，那么维护左儿子右儿子的 \(\min\) 和 \(\max\)，翻转直接交换即可。
点击查看代码
int n,m;
int a[maxn],ch[maxn][2],fa[maxn],RT;
int dep[maxn],siz[maxn],son[maxn];
int top[maxn],dfn[maxn],dfncnt,id[maxn];
void dfs1(int u,int d){
dep[u]=d,siz[u]=1;
if(ch[u][0]) dfs1(ch[u][0],d+1);
if(ch[u][1]) dfs1(ch[u][1],d+1);
siz[u]+=siz[ch[u][0]]+siz[ch[u][1]];
if(siz[ch[u][0]]>=siz[ch[u][1]]) son[u]=ch[u][0];
else son[u]=ch[u][1];
}
void dfs2(int u,int t){
dfn[u]=++dfncnt,top[u]=t,id[dfncnt]=u;
if(!son[u]) return;
dfs2(son[u],t);
if(ch[u][0]&&ch[u][0]!=son[u]) dfs2(ch[u][0],ch[u][0]);
if(ch[u][1]&&ch[u][1]!=son[u]) dfs2(ch[u][1],ch[u][1]);
}
struct SegmentTree{
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
bool tag[maxn<<2],chk[maxn<<2];
int lmx[maxn<<2],lmn[maxn<<2],rmx[maxn<<2],rmn[maxn<<2];
inline void push_up(int rt){
lmx[rt]=max(lmx[rt<<1],lmx[rt<<1|1]);
lmn[rt]=min(lmn[rt<<1],lmn[rt<<1|1]);
rmx[rt]=max(rmx[rt<<1],rmx[rt<<1|1]);
rmn[rt]=min(rmn[rt<<1],rmn[rt<<1|1]);
}
inline void push_down(int rt){
if(tag[rt]){
swap(lmx[rt<<1],rmx[rt<<1]),swap(lmn[rt<<1],rmn[rt<<1]);
swap(lmx[rt<<1|1],rmx[rt<<1|1]),swap(lmn[rt<<1|1],rmn[rt<<1|1]);
tag[rt<<1]^=1,tag[rt<<1|1]^=1;
chk[rt<<1]^=1,chk[rt<<1|1]^=1;
tag[rt]=0;
}
}
void build(int rt,int l,int r){
tag[rt]=0;
if(l==r){
lmx[rt]=rmx[rt]=-inf,lmn[rt]=rmn[rt]=inf;
if(id[l]==RT) return;
if(ch[fa[id[l]]][0]==id[l]) chk[rt]=0,lmx[rt]=lmn[rt]=a[fa[id[l]]];
else chk[rt]=1,rmx[rt]=rmn[rt]=a[fa[id[l]]];
return;
}
build(lson),build(rson);
push_up(rt);
}
void update(int rt,int l,int r,int p){
if(l==r){
if(id[l]==RT) return;
if(!chk[rt]) lmx[rt]=lmn[rt]=a[fa[id[l]]];
else rmx[rt]=rmn[rt]=a[fa[id[l]]];
return;
}
push_down(rt);
if(p<=mid) update(lson,p);
else update(rson,p);
push_up(rt);
}
void update_tag(int rt,int l,int r,int pl,int pr){
if(pl<=l&&r<=pr){
swap(lmx[rt],rmx[rt]),swap(lmn[rt],rmn[rt]);
tag[rt]^=1;
chk[rt]^=1;
return;
}
push_down(rt);
if(pl<=mid) update_tag(lson,pl,pr);
if(pr>mid) update_tag(rson,pl,pr);
push_up(rt);
}
int query_max(int rt,int l,int r,int pl,int pr){
if(pl<=l&&r<=pr) return rmx[rt];
push_down(rt);
int res=-inf;
if(pl<=mid) res=max(res,query_max(lson,pl,pr));
if(pr>mid) res=max(res,query_max(rson,pl,pr));
return res;
}
int query_min(int rt,int l,int r,int pl,int pr){
if(pl<=l&&r<=pr) return lmn[rt];
push_down(rt);
int res=inf;
if(pl<=mid) res=min(res,query_min(lson,pl,pr));
if(pr>mid) res=min(res,query_min(rson,pl,pr));
return res;
}
#undef mid
#undef lson
#undef rson
}S;
inline void query(int x){
int now=x;
int mx=-inf,mn=inf;
while(now){
mx=max(mx,S.query_max(1,1,n,dfn[top[now]],dfn[now]));
mn=min(mn,S.query_min(1,1,n,dfn[top[now]],dfn[now]));
now=fa[top[now]];
}
if(a[x]>mx&&a[x]<mn) printf("YES\n");
else printf("NO\n");
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;++i){
a[i]=read(),ch[i][0]=read(),ch[i][1]=read();
if(ch[i][0]) fa[ch[i][0]]=i;
if(ch[i][1]) fa[ch[i][1]]=i;
}
for(int i=1;i<=n;++i){
if(!fa[i]) RT=i;
}
dfs1(RT,0);
dfs2(RT,RT);
S.build(1,1,n);
for(int i=1,opt,x;i<=m;++i){
opt=read(),x=read();
if(opt==1){
a[x]=read();
if(ch[x][0]) S.update(1,1,n,dfn[ch[x][0]]);
if(ch[x][1]) S.update(1,1,n,dfn[ch[x][1]]);
}
else if(opt==2){
if(siz[x]>1) S.update_tag(1,1,n,dfn[x]+1,dfn[x]+siz[x]-1);
}
else query(x);
}
return 0;
}
T3 奇迹树
原题：AtCoder-ARC117D Miracle Tree
非常厉害啊！
把编号按 \(E_i\) 升序排序，满足 \(E_{p_i}-E_{p_{i-1}}\ge \mathrm{dist}(p_{i-1},p_i)\) 即可。证明考虑对于 \(i<j<k\)，有 \(E_k-E_i=E_k-E_j+E_j-E_i=\mathrm{dist}(p_i,p_j)+\mathrm{dist}(p_j,p_k)\ge \mathrm{dist}(p_i,p_k)\)。
实际上可以取到 \(E_{p_i}-E_{p_{i-1}}=\mathrm{dist}(p_{i-1},p_i)\)，这样最大值 \(E_{p_n}=1+\sum_{i=1}^{n-1}\mathrm{dist}(p_i,p_{i+1})\)，注意到如果加上 \(\mathrm{dist}(p_1,p_n)\)，最优策略就是按照 DFS 序，这样总和是 \(1+2(n-1)\)，那么减去的 \(\mathrm{dist}(p_1,p_n)\) 是直径就做到最小。
点击查看代码
int n;
int D1,D2;
vector<int> E[maxn];
int fa[maxn],dep[maxn];
bool mark[maxn];
void dfs1(int u,int f,int d){
fa[u]=f,dep[u]=d;
for(int v:E[u]){
if(v==f) continue;
dfs1(v,u,d+1);
}
}
int id[maxn];
void dfs2(int u){
id[++id[0]]=u;
sort(E[u].begin(),E[u].end(),[&](int A,int B){
return mark[A]<mark[B];
});
for(int v:E[u]){
if(v==fa[u]) continue;
dfs2(v);
}
}
int siz[maxn],son[maxn],top[maxn];
void dfs3(int u){
siz[u]=1;
int maxson=-1;
for(int v:E[u]){
if(v==fa[u]) continue;
dfs3(v);
siz[u]+=siz[v];
if(siz[v]>maxson) son[u]=v,maxson=siz[v];
}
}
void dfs4(int u,int t){
top[u]=t;
if(!son[u]) return;
dfs4(son[u],t);
for(int v:E[u]){
if(v==fa[u]||v==son[u]) continue;
dfs4(v,v);
}
}
inline int get_LCA(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]]) swap(u,v);
v=fa[top[v]];
}
if(dep[u]>dep[v]) swap(u,v);
return u;
}
inline int get_dis(int u,int v){
int lca=get_LCA(u,v);
return dep[u]+dep[v]-2*dep[lca];
}
int ans[maxn];
int main(){
n=read();
for(int i=1,u,v;i<n;++i){
u=read(),v=read();
E[u].push_back(v),E[v].push_back(u);
}
dfs1(1,0,0);
for(int i=1;i<=n;++i){
if(dep[i]>dep[D1]) D1=i;
}
dfs1(D1,0,0);
for(int i=1;i<=n;++i){
if(dep[i]>dep[D2]) D2=i;
}
for(int u=D2;u;u=fa[u]) mark[u]=true;
dfs2(D1);
dfs3(D1);
dfs4(D1,D1);
ans[id[1]]=1;
for(int i=2;i<=n;++i) ans[id[i]]=ans[id[i-1]]+get_dis(id[i-1],id[i]);
for(int i=1;i<=n;++i) printf("%d ",ans[i]);
printf("\n");
return 0;
}
T4 暴雨
要求前后都有更大的位置，这样不方便 DP，一个套路是枚举最大值位置，DP 前缀和后缀。
设 \(f_{i,j,l,0/1},g_{i,j,l,0/1}\) 为考虑前缀/后缀 \(i\)，当前最大值 \(j\)，删除 \(l\) 个数，目前积水体积和为偶数/奇数的方案数。
由于最多删 \(k\) 个数，那么本质不同的 \(j\) 只有 \(k+1\) 个，可以 set 和 map 预处理并映射。
转移是平凡的，就是讨论是否更改最大值以及是否删除当前的位置。
合并就是枚举最高点 \(i\)，在第二维要求不大于 \(h_i\)，后缀和优化，在第三维就是和为 \(k\)。注意如果有多个相同最大值，要求每个方案在删去后最大值第一次出现位置计算，也就是要求前缀第二维小于 \(h_i\)，后缀第二维不大于 \(h_i\)。
时间复杂度 \(O(nk^2)\)。
点击查看代码
int n,k;
int h[maxn];
set<int> S;
unordered_map<int,int> mp[maxn];
int valf[maxn][maxk],valg[maxn][maxk];
int f[maxn][maxk][maxk][2],g[maxn][maxk][maxk][2];
int ans;
int main(){
n=read(),k=read();
for(int i=1;i<=n;++i) h[i]=read();
for(int i=0;i<=n;++i){
S.insert(h[i]);
int j=0;
auto it=S.end();
--it;
while(1){
valf[i][++j]=(*it),mp[i][(*it)]=j;
valf[i][0]=j;
if(j==k+1||it==S.begin()) break;
--it;
}
}
f[0][1][0][0]=1;
for(int i=0;i<n;++i){
for(int j=1;j<=valf[i][0];++j){
for(int l=0;l<=min(i,k);++l){
int x=valf[i][j];
if(h[i+1]<=x){
//最大值不改变
//不删
int id=mp[i+1][x];
f[i+1][id][l][(x-h[i+1])&1]=(f[i+1][id][l][(x-h[i+1])&1]+f[i][j][l][0])%mod;
f[i+1][id][l][(x-h[i+1])&1^1]=(f[i+1][id][l][(x-h[i+1])&1^1]+f[i][j][l][1])%mod;
//删
f[i+1][id][l+1][x&1]=(f[i+1][id][l+1][x&1]+f[i][j][l][0])%mod;
f[i+1][id][l+1][x&1^1]=(f[i+1][id][l+1][x&1^1]+f[i][j][l][1])%mod;
}
else{
//最大值改变
//不删
int id1=mp[i+1][x],id2=mp[i+1][h[i+1]];
f[i+1][id2][l][0]=(f[i+1][id2][l][0]+f[i][j][l][0])%mod;
f[i+1][id2][l][1]=(f[i+1][id2][l][1]+f[i][j][l][1])%mod;
//删
f[i+1][id1][l+1][x&1]=(f[i+1][id1][l+1][x&1]+f[i][j][l][0])%mod;
f[i+1][id1][l+1][x&1^1]=(f[i+1][id1][l+1][x&1^1]+f[i][j][l][1])%mod;
}
}
}
}
S.clear();
for(int i=0;i<=n;++i) mp[i].clear();
for(int i=n+1;i>=1;--i){
S.insert(h[i]);
int j=0;
auto it=S.end();
--it;
while(1){
valg[i][++j]=(*it),mp[i][(*it)]=j;
valg[i][0]=j;
if(j==k+1||it==S.begin()) break;
--it;
}
}
g[n+1][1][0][0]=1;
for(int i=n+1;i>1;--i){
for(int j=1;j<=valg[i][0];++j){
for(int l=0;l<=min(n-i+1,k);++l){
int x=valg[i][j];
if(h[i-1]<=x){
//最大值不改变
int id=mp[i-1][x];
if(id){
//不删
g[i-1][id][l][(x-h[i-1])&1]=(g[i-1][id][l][(x-h[i-1])&1]+g[i][j][l][0])%mod;
g[i-1][id][l][(x-h[i-1])&1^1]=(g[i-1][id][l][(x-h[i-1])&1^1]+g[i][j][l][1])%mod;
//删
g[i-1][id][l+1][x&1]=(g[i-1][id][l+1][x&1]+g[i][j][l][0])%mod;
g[i-1][id][l+1][x&1^1]=(g[i-1][id][l+1][x&1^1]+g[i][j][l][1])%mod;
}
}
else{
//最大值改变
//不删
int id1=mp[i-1][x],id2=mp[i-1][h[i-1]];
if(id2){
g[i-1][id2][l][0]=(g[i-1][id2][l][0]+g[i][j][l][0])%mod;
g[i-1][id2][l][1]=(g[i-1][id2][l][1]+g[i][j][l][1])%mod;
}
//删
if(id1){
g[i-1][id1][l+1][x&1]=(g[i-1][id1][l+1][x&1]+g[i][j][l][0])%mod;
g[i-1][id1][l+1][x&1^1]=(g[i-1][id1][l+1][x&1^1]+g[i][j][l][1])%mod;
}
}
}
}
}
for(int i=0;i<=n+1;++i){
for(int j=k+1;j>=1;--j){
for(int l=0;l<=k;++l){
f[i][j][l][0]=(f[i][j][l][0]+f[i][j+1][l][0])%mod;
f[i][j][l][1]=(f[i][j][l][1]+f[i][j+1][l][1])%mod;
g[i][j][l][0]=(g[i][j][l][0]+g[i][j+1][l][0])%mod;
g[i][j][l][1]=(g[i][j][l][1]+g[i][j+1][l][1])%mod;
}
}
}
for(int i=1;i<=n;++i){
int p1=upper_bound(valf[i-1]+1,valf[i-1]+1+valf[i-1][0],h[i],greater<int>())-valf[i-1];
int p2=lower_bound(valg[i+1]+1,valg[i+1]+1+valg[i+1][0],h[i],greater<int>())-valg[i+1];
if(p1>valf[i-1][0]||p2>valg[i+1][0]) continue;
int now=0;
for(int j=0;j<=k;++j){
ans=(ans+1ll*f[i-1][p1][j][0]*g[i+1][p2][k-j][0]%mod)%mod;
ans=(ans+1ll*f[i-1][p1][j][1]*g[i+1][p2][k-j][1]%mod)%mod;
now=(now+1ll*f[i-1][p1][j][0]*g[i+1][p2][k-j][0]%mod)%mod;
now=(now+1ll*f[i-1][p1][j][1]*g[i+1][p2][k-j][1]%mod)%mod;
}
}
printf("%d\n",ans);
return 0;
}
反思
T1 确实太不会这种无向图环之类的的问题了。
T2 最后才想出来，所幸写得比较快。
T3 这个构造比较巧妙。
T4 考场上想到前后缀这种之前见过的套路了吗？