Arahc's blog

咕↘咕↗咕——→

全真模1部分题解及总结

发布于 2021-08-12 | 分类于 考试总结 、 分治 、 图论 、 数据结构 、 题解 | 22分钟 | 4412字数

考试策略：

比较不行，前面花了太多时间在 T1 上，实际上最后个人感觉 T1 最难。T2 类似于一个猜结果后证明的东西，考虑到数据范围，必然网络流二分图动态规划三选一。因为个人动态规划水平不太好，优先考虑网络流做法没想出来，又因为想到网格图一定是二分图，所以尝试用二分图的角度解释必胜方式，从而证明正确性。T3 因为以前同学讲点分治的时候提到过：

点分治可以用来处理树上路径长度有关的奇特问题，包括刚好等于的，L 到 R 之间的，一个倍数的……

看到“长度-最大值”为倍数的时候直接定档点分治，但是因为 T1 耗时间太多没有时间打。最后 T1T3 暴力写挂没有捞到分，总分只由 T2 AC 的 100 分。

问题所在和反思

T1 最开始想到点分治。显然过于草率被题目的“区间范围”误导了。是缺乏经验的表现。后来及时发现应该使用dsu on tree更好地维护本题。但是没有考虑到不从这个子树的根出发的路径的情况，这一发直接把我送走，考场上改到 11 点放弃了，晚上改到 2 点（刚刚终于 A 了，才开始写总结）

T2 我承认找到正解有一定的运气成分。如果我很自信地认为我的 DP 很好，说不定我会更加往博弈论 DP 的方向想，而不会发现二分图最大匹配的做法。代码实现方面比较混乱，一定程度上造成调试困难。

T3 是裸的点分治。我在做题记录里写到点分治是一个好写难调的做法。改题的时候再一次验证了这个观点，需要实现的细节繁多。属于典型的“在考场上我就算知道这题正解我也不会马上干这个题”的类型。

用通俗的网络流行语总结，就叫做一切恐惧来源于火力不足，网络流和二分图题单上我几乎已经做完了所以很熟悉，但是点分治和 dsu，题单上这类题较少，练习不多，更容易出错，会对这类算法产生一种“No I can't”的心理。直接导致 T3 我知道正解但是还是 0 分的惨案。

题解

T1，看门狗（watchdog）

给定一个大小为 nn 的有根树，11 为根。每个节点有权值 l,rl,r 表示一个边数区间，边有边权，对于每一个子树，求经过这个子树的根节点的所有边数在子树根节点边数区间内的简单路径中的最大边权和。时间限制 4s，n⩽106n\leqslant 10^6，边权为不超过 10910^9 的非负整数。

第一眼看到区间范围，树上求一条路径的属性，容易联想到点分治。但是实际而言，权值范围过大，点分治不能很好地实现。考虑到时间限制为 44s，可以放跑一些 nlog⁡2nn\log^2 n 的做法。因为边权一定是非负整数，所以对于同一条路径，向外延伸边数越多，权值一定不降。

因为 n⩽106n\leqslant 10^6，边数的范围是与 nn 同级。假设 uu 为当前处理的子树。考虑开一个桶，下标为 ii，值为 tit_i，记录在一个点的子树内，走 ii 条边的路径的长度最大值。查询的时候查询 [lu,ru][l_u,r_u] 的最大值，考虑到路径必须要经过子树的根节点，不能朴素地直接处理，但是我们考虑到可以将两条路径合并，这个问题就迎刃而解了。此外还需要将一个点的深度引入到下标中，也就是插入下标为 i+depui+dep_u，查询则为 [lu+depu−1,ru+depu−1][l_u+dep_u-1,r_u+dep_u-1]，简单修改即可，不要忘记桶的大小要因此开 2n2n。

暴力地 dfs 维护这些东西，是 n3n^3 的。如果预处理每一个点的重儿子，将暴力 dfs 转化为 dsu on tree，复杂度降为 n2log⁡nn^2\log n。因为开的桶只需要支持单点修改最大值，区间查询最大值，用树状数组维护为 nlog⁡3nn\log^3 n（树状数组查询最值是 log⁡2\log^2 级别的），用线段树维护为 nlog⁡2nn\log^2 n。总的算法就是 dsu on tree，线段树维护边数桶。

如果使用长链剖分 dsu on tree，时间复杂度可能会进一步优化为 nlog⁡nn\log n，这里放的代码是重链剖分：

#include<bits/stdc++.h>
#define LL long long

using namespace std;
const LL max_n=1000005,mod=998244353;
inline LL read(){
	LL x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void write(LL x){
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10^48);
}
// 快速幂，题目要求按一种方案处理所有答案来避免输出过大。
inline LL mi(LL a,LL p){
	LL res=1;
	while(p){
		if(p&1) res*=a,res%=mod;
		a*=a,a%=mod,p>>=1;
	}
	return res;
}

// 以下都是线段树基操

#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
struct segment_tree{
	LL mx[max_n*8],tg[max_n*8],tp[max_n*8];
	int L[max_n*8],R[max_n*8];

	inline void pushup(LL x){
		tg[x]=max(tg[ls(x)],tg[rs(x)]);
	}
	inline void push(LL x,LL p){
        // 下传标记
		if(p==1 && (~tg[x])){
			tp[x]=p,
			mx[x]=max(mx[x],tg[x]);
			tg[x]=-1;
		}
		if(p==2){
			tp[x]=p,
			mx[x]=tg[x]=-1;
		}
	}
	inline void pushdown(LL x){
		if(!tp[x]) return;
		push(ls(x),tp[x]),
		push(rs(x),tp[x]);
		tp[x]=0;
	}
	inline void build(LL x,LL l,LL r){
		L[x]=l,R[x]=r,mx[x]=tg[x]=-1,tp[x]=0;
		if(l==r) return;
		LL mid=(l+r)>>1;
		build(ls(x),l,mid),
		build(rs(x),mid+1,r);
	}
	inline void chg(LL x,LL p,LL val){
//		cerr<<"p : "<<p<<" L,R : "<<L[x]<<","<<R[x]<<"\n";
		if(L[x]==p && R[x]==p){
			tg[x]=max(tg[x],val);
			return;
		}
		pushdown(x);
		LL mid=(L[x]+R[x])>>1;
		if(p<=mid) chg(ls(x),p,val);
		else chg(rs(x),p,val);
		pushup(x);
	}
	inline LL ask(LL x,LL l,LL r){
		if(l<=L[x] && R[x]<=r)
			return mx[x];
		pushdown(x);
		LL mid=(L[x]+R[x])>>1,res=-1;
		if(l<=mid) res=max(res,ask(ls(x),l,r));
		if(r>mid) res=max(res,ask(rs(x),l,r));
		return res;
	}
}seg;
#undef ls
#undef rs
// 封装链式前向星
struct graph{
	int ct,hd[max_n],to[max_n],nx[max_n],ln[max_n];

	graph(){ct=1;}
	inline void clear(){
		ct=1;
		memset(hd,0,sizeof(hd));
	}
	inline void add(LL u,LL v,LL w){
		nx[++ct]=hd[u],hd[u]=ct,to[ct]=v,ln[ct]=w;
	}
}e;

int n,l[max_n],r[max_n];
// hv表示重儿子，sz表示子树大小
// de表示深度，hs表示连向重儿子的边的编号
int hv[max_n],sz[max_n],de[max_n],hs[max_n];
inline void dfs(LL u,LL f){
	de[u]=de[f]+1,sz[u]=1;
	LL mx=0;
	for(register int i=e.hd[u];i;i=e.nx[i]){
		LL v=e.to[i];
		if(v==f) continue;
		dfs(v,u);
		sz[u]+=sz[v];
		if(sz[v]>mx){
			mx=sz[v];
			hv[u]=v,
			hs[u]=i;
		}
	}
}

LL ans[max_n];
// 原先的桶用线段树代替了
inline LL getans(LL u,LL w,LL dp,LL L,LL R){
	LL res=-1;
	seg.chg(1,de[u],w);
	if(R>=de[u]-dp)
		res=seg.ask(1,dp+max(1LL,L+dp-de[u]),R-de[u]+dp*2);
	if(res>-1) res+=w;
	for(register int i=e.hd[u];i;i=e.nx[i]){
		LL v=e.to[i];
		res=max(res,getans(v,w+e.ln[i],dp,L,R));
	}
	return res;
}
// s为0表示需要清空状态避免对兄弟造成影响
// 方式是直接push(1,2);下传标记的时候可以做到全局修改
inline void dsu(LL u,LL w,bool s){
	LL res=-1;
	for(register int i=e.hd[u];i;i=e.nx[i]){
		LL v=e.to[i];
		if(v==hv[u]) continue;
		dsu(v,0,0);// 轻儿子要清空，重儿子不要
	}
	if(hv[u]) dsu(hv[u],w+e.ln[hs[u]],1);
	seg.chg(1,de[u],w),seg.push(1,1);
	
	for(register int i=e.hd[u];i;i=e.nx[i]){
		LL v=e.to[i];
		if(v==hv[u]) continue;
		LL tmp=getans(v,w+e.ln[i],de[u],l[u],r[u]);
		seg.push(1,1);
		if(tmp>-1) tmp-=w*2;
		res=max(res,tmp);
	}
	LL tmp=seg.ask(1,l[u]+de[u],r[u]+de[u]);
	if(tmp>-1) tmp-=w;
	res=max(res,tmp);
	ans[u]=res;
	if(!s) seg.push(1,2);
}

signed main(){
	n=read();
	for(register int i=1;i<=n;++i)
		l[i]=read(),r[i]=read();
	for(register int i=2;i<=n;++i){
		LL fa=read(),w=read();
		e.add(fa,i,w);
	}
	seg.build(1,1,2*n),seg.push(1,2);
	dfs(1,1),
	dsu(1,0,0);
	LL sum=0;
    // 没有在简化题意里提到的
    // 避免输出过大，题目要求按此方案处理答案
	for(register int i=1;i<=n;++i){
//		cerr<<ans[i]<<"\n";
		sum+=ans[i]%mod*mi(23333,n-i)%mod,
		sum+=mod,sum%=mod;
	}
	write(sum),putchar('\n');
	return 0;
}

T2，游戏（b）

一个 n∗mn*m 的方格棋盘，有的格子有障碍物，A 先选一个格子放一个棋子，然后 B 先手，和 A 轮流移动这个棋子。每次移动可以向上/下/左/右移动一个格子。不能移到棋盘外，不能移到障碍物上，不能移到一个走过的格子上。无法行动者算输。求所有可以让 A 必胜的开始格。n,m⩽100n,m\leqslant 100。

唯一一个考场上做出来的题目。

看到这个刚好不大但是不能状压的数据——基本上是网络流二分图动态规划三选一了。考虑到博弈论，理应优先想到决策树上 DP，但是又因为是网格，网格图也是二分图的一种，而且经常有网格图上网络流的魔仙题目。因此很难一眼得到大致算法的感觉。我的第一想法是网络流，但是找不到一个很好的把它转化为最大瘤或者最小彁的方式。所以从二分图的方法考虑问题。

已经是二分图了所以显然不是二分图判定。从最大匹配的角度来看。根据网格图建图套路法则，我们按照国际象棋染色法染色后，相邻的不是障碍的格子连边。如果得到的二分图存在完美匹配，那么无论 A 选什么格子，B 一定可以沿着一条匹配边移动。A 就只能沿一条不匹配边移动，B 又可以延匹配边移动……我们发现因为点和边都不能走重复，所以匹配边走完时，或者走完前，A 就输掉了。因此完美匹配的情况一定无解。

用这种思想，考虑到对于一个二分图，如果存在最大匹配，A 放在最大匹配点，B 就可以走匹配边，又陷入这样的死境。所以 A 要放在一个不是最大匹配点的地方，使得 B 第一步只能走非匹配边，容易得到一定可以走到一个最大匹配点。然后把走匹配边的机会送给了 A。

因此对于那些最大匹配点集不包含的点，就是答案。如果有多个最大匹配，只要有一个最大匹配不包括就可以了。

#include<cstdio>
#include<vector>
#include<string.h>
#include<iostream>
using namespace std;
const int max_n=105;
inline int read(){
	int x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void write(int x){
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10^48);
}
inline bool reads(){
	char c=getchar();
	while(c!='.' && c!='#') c=getchar();
	return c=='.';
}

const int dx[4]={-1,1,0,0};
const int dy[4]={0,0,1,-1};

int n,m,id[max_n][max_n],cnt,tot;
bool a[max_n][max_n];

std::pair<int,int> mp[max_n*max_n];

struct graph{
	int ct,hd[max_n*max_n*2],to[max_n*max_n*2],nx[max_n*max_n*2];

	graph(){ct=1;}
	inline void clear(){
		ct=1;
		memset(hd,0,sizeof(hd));
	}
	inline void add(int u,int v){
		nx[++ct]=hd[u],hd[u]=ct,to[ct]=v;
	}
}e;

int con[max_n*max_n],get[max_n*max_n];
bool vis[max_n*max_n];

inline bool dfs(int u,int p){ // 匈牙利跑最大匹配
	for(register int i=e.hd[u];i;i=e.nx[i]){
		int v=e.to[i];
		if(con[v]==p) continue;
		con[v]=p;
		if(!get[v] || dfs(get[v],p)){
			get[v]=u;
			return 1;
		}
	}
	return 0;
}

inline void tag(int u){ // 标记那些存在最大匹配没有的点
	++tot;
	for(register int i=e.hd[u];i;i=e.nx[i]){
		int v=e.to[i];
		if(!get[v]) continue;
		if(!vis[get[v]]){
			vis[get[v]]=1;
			tag(get[v]);
		}
	}
}

signed main(){
	n=read(),m=read();
	for(register int i=1;i<=n;++i)
		for(register int j=1;j<=m;++j){
			a[i][j]=reads();
			if(a[i][j]){
				id[i][j]=++cnt;
				mp[cnt]=std::make_pair(i,j);
			}
		}
	for(register int i=1;i<=n;++i)
		for(register int j=1;j<=m;++j)
			if(a[i][j] && ((i+j)&1)) // 国际象棋染色法，i+j为奇数的是黑格子
				for(register int k=0;k<4;++k){
					int tx=i+dx[k],ty=j+dy[k];
					if(tx<1 || ty<1 || tx>n || ty>m) continue;
					if(a[tx][ty])
						e.add(id[i][j],id[tx][ty]),
						e.add(id[tx][ty],id[i][j]);
				}
	for(register int i=1;i<=n;++i)
		for(register int j=1;j<=m;++j)
			if(a[i][j] && ((i+j)&1))
				dfs(id[i][j],id[i][j]);

	for(register int i=1;i<=cnt;++i)
		if(get[i])
			get[get[i]]=i;
	for(register int i=1;i<=cnt;++i) // 找出所有存在最大匹配没有这个的点
    // tot 统计答案，vis 避免重复跑
		if(!get[i]){
			vis[i]=1;
			tag(i);
		}
	for(register int i=1;i<=cnt;++i)
		cerr<<get[i]<<"\n";
	write(tot),putchar('\n');
	for(register int i=1;i<=cnt;++i)
		if(vis[i])
			write(mp[i].first),putchar(' '),
			write(mp[i].second),putchar('\n');
	return 0;
}

T3 树（c）

为什么 T2 是 b，T3 是 c，T1 不是 a 啊

给定一个树，每个点有一个非负整数点权，记一条路径的权值为路径上点权和减去点权最大值，求路径权值恰好为 pp 的非负整数倍的路径个数。特别地，一个单独的点也算作一条路径。n⩽105n\leqslant 10^5，点权和 pp 不超过 10610^6。

显然可以用比较裸的点分治进行。因为点权和可能比较大，但是只考虑边权是不是 pp 的倍数，再加上没有除法，可以直接取模判 00。整体比较模板。

注意到一个单独的点也算作一条路径，但是一个单独的点组成的路径的权值为 00，一定符合条件。因此只需要在跑完点分治得到的答案上加 nn 即可，不需要特殊操作。

代码：

#include<cstdio>
#include<algorithm>
#include<string.h>
#define int long long
const int max_n=100005,max_m=10000005;int mod;
inline int read(){
	int x=0;char c=getchar();
	while(c<'0' || c>'9') c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x;
}
inline void write(int x){
	if(x>9) write(x/10);
	putchar(x%10^48);
}
inline int max(int a,int b){return a>b?a:b;}

struct graph{
	int ct,hd[max_n*2],to[max_n*2],nx[max_n*2];

	graph(){ct=1;}
	inline void clear(){
		ct=1;
		memset(hd,0,sizeof(hd));
	}
	inline void add(int u,int v){
		nx[++ct]=hd[u],hd[u]=ct,to[ct]=v;
	}
}e;

int n,a[max_n],root;

bool vis[max_n];

inline int getsize(int u,int fa){ // 返回一个点的子树大小
// （本来想直接记录size每次更新但是比较难处理就算了）
	int res=1;
	for(register int i=e.hd[u];i;i=e.nx[i]){
		int v=e.to[i];
		if(v==fa || vis[v]) continue;
		res+=getsize(v,u);
	}
	return res;
}

inline int getroot(int u,int fa,int &rt,int sz){ // 找根
	int res=1,s;bool ok=1;
	for(register int i=e.hd[u];i;i=e.nx[i]){
		int v=e.to[i];
		if(v==fa || vis[v]) continue;
		s=getroot(v,u,rt,sz);
		res+=s;
		if(s*2>sz) ok=0;
	}
	if((sz-res)*2>sz) ok=0;
	if(ok) rt=u;
	return res;
}

int ans,tot,t[max_m];
// ans记录答案，tot记录点数，t[]是桶

struct dot{ // 点分治基操记录信息，封装了。
	int sm,mx; // sm->sum mx->max
	dot(){sm=mx=0;}
	
	inline void init(int s,int m){
		sm=s,mx=m;
	}
}c[max_n],k[max_n];

inline bool cmp(dot a,dot b){ // 按max排序
	return a.mx<b.mx;
}

inline void pre(int u,int fa,int x,int sm){ // 提前处理好每个点信息
	x=max(x,a[u]),
	sm+=a[u],sm%=mod;
	k[u].init(sm,x);
	for(register int i=e.hd[u];i;i=e.nx[i]){
		int v=e.to[i];
		if(v==fa || vis[v]) continue;
		pre(v,u,x,sm);
	}
}

inline void push(int u,int fa){ // 将要用到的信息递归读取储存
	c[++tot]=k[u];
	for(register int i=e.hd[u];i;i=e.nx[i]){
		int v=e.to[i];
		if(v==fa || vis[v]) continue;
		push(v,u);
	}
}

inline int calc(int u,int val){
	tot=0;push(u,0);
	std::sort(c+1,c+1+tot,cmp); // 排序后统计答案
	
	int res=0;
	for(register int i=1;i<=tot;++i){
		res+=t[((c[i].mx+val-c[i].sm)%mod+mod)%mod],
		++t[(c[i].sm+mod)%mod];
	}
	for(register int i=1;i<=tot;++i)
		--t[(c[i].sm+mod)%mod];
	return res;
}

inline void dfz(int u){ // 点分治部分
	int sz=getsize(u,0);
	getroot(u,0,u,sz);
	pre(u,0,0,0);

	ans+=calc(u,a[u]);
	vis[u]=1;
	for(register int i=e.hd[u];i;i=e.nx[i]){
		int v=e.to[i];
		if(vis[v]) continue;
		ans-=calc(v,a[u]);
	}

	for(register int i=e.hd[u];i;i=e.nx[i]){
		int v=e.to[i];
		if(vis[v]) continue;
		dfz(v);
	}
}

signed main(){
	n=read(),mod=read();
	for(register int i=2;i<=n;++i){
		int x=read(),y=read();
		e.add(x,y),e.add(y,x);
	}
	for(register int i=1;i<=n;++i)
		a[i]=read();
	dfz(1);
	write(ans+n),putchar('\n'); // 别忘记加 n
	return 0;
}
# 考试总结 # 分治 # 图论 # 数据结构 # 题解
CF1553部分题解及总结 上一篇
CF1557和CF1530部分题解 下一篇
浏览数 次 | 访客数 人
Powered by Gridea ©2019 | Theme By HsxyHao
Articles written by Arahc
0%
召唤看板娘