[省选联考 2021 A/B 卷] 图函数 题解

2021/12/13 23:21:19

本文主要是介绍[省选联考 2021 A/B 卷] 图函数 题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

没错,NOIP 都结束了,我才补省选题。我是一只大鸽子!!1

Description

传送门

Solution

算法一

直接暴力即可。

每次计算 f ( i , G ) f(i,G) f(i,G) 的时候,暴力枚举 j ∈ [ 1 , i ] j \in [1,i] j∈[1,i] 并通过 O ( m ) O(m) O(m) 的 dfs \text{dfs} dfs 进行判定,所以每个 f ( i , G ) f(i,G) f(i,G) 的计算都是 O ( n m ) O(nm) O(nm) 的。

注意到一共要计算 O ( n m ) O(nm) O(nm) 个 f ( i , G ) f(i,G) f(i,G),所以总复杂度是 O ( n 2 m 2 ) O(n^2 m^2) O(n2m2) 的,可以拿到 16 16 16 分。这也是本蒟蒻的考场分数

算法二

考虑如何优化 h h h 的计算。

可以发现, ( x , y ) (x,y) (x,y) 会对答案产生贡献,当且仅当 x ≥ y x \ge y x≥y,且存在一条从 x x x 出发到 y y y,再从 y y y 回到 x x x 的路径使得其经过的所有点的编号均不小于 y y y。

于是,我们可以枚举 y y y,在反图和正图上分别进行一次 dfs \text{dfs} dfs,那么答案应加上在反图和正图上均被经过的点的数量。

单次 dfs \text{dfs} dfs 是 O ( m ) O(m) O(m) 的,一共有 O ( n m ) O(nm) O(nm) 次 dfs \text{dfs} dfs,所以时间复杂度为 O ( n m 2 ) O(nm^2) O(nm2)。

实现的时候,我们可以在求 h ( i , G ) h(i,G) h(i,G) 之前将所有不合法的边删掉,并剪枝+大力卡常,即可拿到 44 44 44 分。特别的,若使用 bitset 优化 dfs \text{dfs} dfs,则时间复杂度为 O ( n 3 w m ) O(\frac {n^3} {w} m) O(wn3​m),卡常后也可以获得同样的分值。

算法三

Key Observation

若 ( x , y ) (x,y) (x,y) 会对 f ( i , G ) f(i,G) f(i,G) 产生贡献,则其同样也会对 f ( i − 1 , G ) f(i-1,G) f(i−1,G) 产生贡献。


这启发我们给边带上边权,即这条边的编号。那么,若令 f x , y f_{x,y} fx,y​ 表示从 x x x 到 y y y 的路径上的最小边权的最大值,则 ( x , y ) (x,y) (x,y) 会对第 f x , y − 1 , f x , y − 2 , ⋯   , 0 f_{x,y}-1,f_{x,y}-2,\cdots,0 fx,y​−1,fx,y​−2,⋯,0 个答案均产生 1 1 1 的贡献——这显然可以使用差分维护。

不难发现可以使用 Floyd 求出 f f f。于是时间复杂度为 O ( n 3 + m ) O(n^3+m) O(n3+m),期望得分 [ 44 , 100 ] [44,100] [44,100] 分。

卡常小技巧

一般人可能会这么写 Floyd:

for (int k=n;k>=1;k--){
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++)
		  GA[i][j]=max(GA[i][j],min(GA[i][k],GA[k][j]));
	}
}

但其实,若 i ≥ k , j ≥ k i \ge k,j \ge k i≥k,j≥k,那么这次松弛是没有任何意义的。

于是可以得到新的代码:

for (int k=n;k>=1;k--){
	for (int i=1;i<k;i++){
		for (int j=1;j<=n;j++)
		  GA[i][j]=max(GA[i][j],min(GA[i][k],GA[k][j]));
	}
	for (int i=k;i<=n;i++){
		for (int j=1;j<k;j++)
		  GA[i][j]=max(GA[i][j],min(GA[i][k],GA[k][j]));
	}
}

它的复杂度是

∑ k = 1 n ( n 2 − ( n − k + 1 ) 2 ) = n 3 − ∑ k = 1 n k 2 = n 3 − n ( n + 1 ) ( 2 n + 1 ) 6 \sum_{k=1}^n (n^2-(n-k+1)^2)=n^3-\sum_{k=1}^n k^2=n^3-\frac {n(n+1)(2n+1)} {6} k=1∑n​(n2−(n−k+1)2)=n3−k=1∑n​k2=n3−6n(n+1)(2n+1)​

这约等于 2 3 n 3 \frac {2} {3} n^3 32​n3,因此可以省掉三分之一的时间,于是就能通过本题了。

PS: 如果有人使用算法三不加这个优化直接过去了,并且没有使用指令集等恶心的东西,请私信我。我将会将您的建议补充在卡常小技巧中。

Summary

这是一道以性质观察为重点,以 Floyd 应用为技巧、套路的放在省选 D1T3 的不错的图论题。虽然我知道这题的标算不是 n^3 的

首先,我们需要洞察到 ( x , y ) (x,y) (x,y) 对答案产生贡献的充要条件。
接着,我们需要观察到 ( x , y ) (x,y) (x,y) 对答案是否产生贡献的单调性

对于上面两个观察,可以得出——对于一类删边或删点求解的问题,我们往往是半在线式地逆序加边维护,或离线式地逐一考虑,而后者各个个体的贡献往往是一个前缀或后缀或区间。

最后,我们需要在上述两个十分重要的观察的前提下,发现我们所要干的最终事情——求出 x x x 到 y y y 的路径边权最小值最大值。这东西显然可以通过 Floyd 维护——相信所有刷题量上千的人都会。

这题的区分度主要在于前两个性质的观察。



这篇关于[省选联考 2021 A/B 卷] 图函数 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程