jvruo

【蒟蒻算法】隐藏在部分分中的解题思路
在比赛中,我们经常会遇到看到题目一时想不到正解的情况。这时我们要做的并不是放弃题目启动扫雷,而是应该先从部分分的...
扫描右侧二维码阅读全文
28
2018/11

【蒟蒻算法】隐藏在部分分中的解题思路

在比赛中,我们经常会遇到看到题目一时想不到正解的情况。这时我们要做的并不是放弃题目启动扫雷,而是应该先从部分分的思路想起。因为许多题目正解的解题思路,就隐藏在部分分的解决方法中。

从部分分到正解

解决一道题目时,依照不同的部分分写不同复杂度的算法是
很简单的,这只是一个经验问题。今天要讲的是如何根据部分分(特殊情况),找到突破口,进而解决全部问题。

一般来讲,典型的部分分(特殊情况)的转化有:“n, m” ->“n = m”“树” -> “链”“图” -> “ 树”“ 动态” -> “ 静态”
“在线” -> “离线” 等。

接下来就让我们从几道例题来深入体会这种解题技巧吧!

树上连续路径

题目描述

给出一棵 n 个点的树,问树上有多少条路径,满足编号的
范围是连续的。(1 ≤ n ≤ 3 × 105)

解题思路

直接考虑树上情况好像不好处理,所以我们先考虑如果是一条链怎么办:假设这条链上第 i 个点的编号是 a[i],编号为 i 的点位于 b[i] 处,也就是说 a[b[i]] = i。

接下来我们考虑如何判断一段链上的一段区间[l,r]编号是否连续呢?我们有两种很显然的方法:

第一种方法我们可以统计链上[l,r]上的编号的最大值max和最小值min,如果max-min+1==lenth;那么[l,r]这一段的编号一定是连续的;但是貌似在程序中不太好操作,查询最值耗时也比较大,所以我们考虑另一种做法;

第二种做法我们可以设f(l,r) 表示 [l,r] 这段区间的长度减去这段区间中形如(i, i + 1) 这种点对的出现次数,那么当且仅当 f(l,r) = 0 时,[l,r]是一条合法的路径。

这时我们先假设我们求解出来了f数组,接下来我们只要建立一个二维坐标系,横轴表示 l,纵轴表示 r,(l,r) 处表示 f(l,r)。那么只需要统计这个坐标系中 1 ≤ l,r ≤ n 这 n^2 个点中有多少个 0 即可。

剩下的问题就是如何快熟计算f(l,r)了:对于 (ai
, ai+1) 这个点对,其会对满足 1 ≤ l ≤ i, i + 1 ≤ r ≤ n 的点的 f 值产生 1 的贡献,因为这些区间都包含了(ai, ai+1) 这个点对。

而对于 (i, i + 1) 这个点对,其会对所有满足1 ≤ l ≤ min(bi, bi+1), max(bi, bi+1) ≤ r ≤ n 的点的 f 值产生 −1 的贡献,如下图所示:

1.png

这些贡献都是一块矩形区域,扫描线 + 线段树维护即可。
时间复杂度 O(n log n)。具体为什么是一个矩阵呢?比如上图我们x从[1,b[i]]y从[b[i+1],n]都要减一,我们要操作的区间就如下图所示:

2.png

这样这道题链的情况就做完了。但是你肯定不满足与此,于是你开始考虑上述做法如何推广到树上?

首先很显然的一个结论,就是树上任意一颗子树内所有点的DFS序是连续的。所以问题就很简单了。我们先在树上跑出每个点的DFS序,接着我们考虑如何想上面链的情况一样处理每一条边的权值。我们先考虑对于一条边 (u, v),不妨设 v 是 u 的父亲,那么其会一个端点在 u 的子树内,一个端点在 v 的子树外(包括 v)的所有路径产生 1 的贡献。然后又由于是对子树的贡献,容易发现如果用 dfs 序来表示,贡献也是若干个矩形。正如下图,我们设整棵树一共有n个节点,以i为根节点的一个子树中根节点i的DFS序为dfn[i],这颗子树中DFS序最大的点DFS序为low[i],那么如下图:

3.png

接着对于一个点对 (i, i + 1),经过讨论也可以发现贡献也和上面所述的情况类似,是 dfs序上的矩形,所以一样的操作就可以啦。

所以总的来说树上的维护和链上维护方式相同,时间复杂度 O(n log n)

Alice 和 Bob

题目描述

Alice 和 Bob 在玩游戏,开始时有 n 堆石子,第 i 堆石子有 ai 个,Alice 和 Bob 轮流取石子。Alice 每次必须从一堆石子内恰好取 x 个,Bob 每次必须从一堆石子内恰好取 y 个。谁不能取了谁输,Alice 先手,两人都以最优策略取,问谁会赢。
1 ≤ n ≤ 10^5。
1 ≤ ai , x, y ≤ 10^9。

解题思路

首先,乍一看这道题,貌似确实没有想到什么特别好的思路,所以我们首先先考虑一下最特殊的情况——x=y;

x=y

对于第 i 堆石子,可以被取 [ai/x] 次。所有石子可以被取 ∑[ai/x] 次,只需要判断这个数的奇偶性即可。

接着我们发现在x=y的时候,对于任意一堆石子不论是加上2kx个石子,还是减去2kx个石子,答案的奇偶性都不会改变,答案也不会发生改变;

更进一步,我们发现对于一堆石子 ai,其加上 k(x + y) 或减去 k(x + y) 都不影响答案,即如果 ai = ai mod (x + y),答案不变。

经过归纳发现这个结论在 n != m 时也成立。接下来我们考虑一下普通的情况:

x<y

由于 ai 对 x + y 取模后答案不变,所以将 ai 对 x + y 取模,那么 0 ≤ ai < x + y,即:一堆石子至多只能被一个人取。又因为 ai < x 的石子没有贡献,不妨删掉,所以有 x ≤ ai < x + y。

接下来我们又分两种情况进行讨论:

如果存在一个 i,使得 x ≤ ai < y,那么先手必胜。因为先手总可以优先取 ai ≥ y 的堆直到取完,这时他还有石子可以取,而后手已经没有可以取的石子了。

如果不存在这样的堆,那么所有堆都有 ai ≥ y。此时如果存在一堆满足 ai ≥ 2x,那么先手必胜。因为先手可以开场取这堆,从而构造出一堆满足 x ≤ ai < y 的石子。否则每堆石子都只能恰好被取一次,判断石子堆数的奇偶性即可。

x>y

情况和上面类似:

一样的由于 ai 对 x + y 取模后答案不变,所以将 ai 对 x + y 取模,那么 0 ≤ ai < x + y,同样有一堆石子至多只能被一个人取。又因为 ai < y 的石子没有贡献,不妨删掉,所以有 y ≤ ai < x + y。

接下来我们同样又分两种情况进行讨论:

我们发现,如果存在一个 i,使得 y ≤ ai < x,那么后手一定必胜吗?不一定,在这种情况下,只有两种可能后手能取胜,一个是存在另一个j,使得 y ≤ aj < x;或者此时能产生贡献的石子的堆数为偶数;

同样的,在第二种大情况下,如果不存在y ≤ ai < x的堆,那么所有堆都有 ai ≥ x。此时如果存在两堆满足 ai ≥ 2y,那么后手必胜。因为先手足够聪明,一定会开场取一堆这样的堆,只有后手再取一堆这样的堆,从而构造出一堆满足 x ≤ ai < y 的石子。否则每堆石子都只能恰好被取一次,判断石子堆数的奇偶性即可。

到这里这道题就做完啦。

卡片机器

题目描述

初始时你有一张卡片 (a, b) 以及三台机器,这三台机器的功能分别如下:
投入一张 (x, y),生成一张 (x + 1, y + 1)。
投入一张 (x, y),生成一张 (x / 2 ,y / 2)。需保证 x, y 均为偶数。
投入一张 (x, y) 和 (y, z),生成一张 (x, z)。
注意:机器工作完成后会将投入的卡片返还。
现在你希望得到卡片 (c, d),问是否能在 10000 步内达成,
如果能,输出方案,否则输出 −1。
1 ≤ a, b, c, d ≤ 1000。

解题思路

这道题看到的第一眼——完了没思路怎么办。不要慌张,我们可以先从最特殊的情况入手——a = b;

首先考虑 a = b 的情况:
容易发现如果 a = b,生成的所有卡片也是两数相等的。又因为显然可以用前两台机器将 (a, b) 变为 (1, 1),(1, 1)又能变成任意(x, x),所以只要c = d,就一定可以。否则一定不行。

接下来考虑 a < b 的情况:
容易发现如果 a < b,生成的所有卡片也是第一个数小于第二个数的。我们可以使用前两台机器把 (a, b) 变为相差最小的两个数,即 (1, x),其中 x 是偶数,因为如果 x 为奇数,则(1,x)--(2,1+x)--(1,(1+x)/2),又 x 大于 1 ,所以(1,(1+x)/2) 差会小于 (1, x) 的差,是更优的。那么 x − 1 是两数之差可能的最小值。也就是说如果d − c < x − 1,那一定无解。

如果有解,则显然需要满足 (x − 1)|(d − c)。假设
d − c = k(x − 1),接下来只需要考虑如何将 (1, x) 变为(1, k(x − 1) + 1)。

其实很简单,先用前两部机器由 (1, x) 得到 (1, k(x − 1) + 1) 的策略如下:
先由 (1, x) 得到 (x, 2x − 1),(2x − 1, 3x − 2), · · · ,((k − 1)(x − 1) + 1, k(x − 1) + 1),再由机器三得到 (1, 2x−1),(1, 3x−2), · · · ,(1, k(x−1) + 1) 即可。

接着a > b 的情况只需要交换 a, b 和 c, d 即可。所以这道题就做完啦。

循环的网格

题目描述

一个 n × m 的网格,你可以给每个格子填一个方向(右或
下),要求从左上角开始沿着给出的方向走,可以将所有格子恰好经过一次且返回起点。问有多少种定向方法。
网格是循环的,也就是说如果某一步走出了网格,你会到网格的另一边。(2 ≤ n, m ≤ 10^5)

解题思路

首先我们注意到,每个格子都的方向都只能是向下或向右,所以我们观察到到如果 (i, j) 处往右走,那么 (i, j + 1) 是从 (i, j) 过来的,也就意味着 (i − 1, j + 1) 处不能往下走,所以 (i − 1, j + 1) 也要往右走。同理往下走也一样。所以可以得到:网格的次对角线上的格子的方向一定相同。即对于每一个格子,他填的方向与他右上方的格子填的方向是一样的。

考虑 gcd(n, m) = 1 的情况,此时从任意一点出发,不断向右上方走,可以走遍所有点,就如下图。即所有点的方向必须一样,这是显然不可以的,所以无解,所以gcd(n, m) ≠ 1。

4.png

接下来考虑 n = m 的情况,此时恰好有 n 条次对角线,现在需要给这 n 条次对角线分配向右还是向下。

设这 n 条次对角线中有 i 个是向右走的,n − i 个向下走的。那么走 n^2 步之后会走到 (ni mod n, n(n − i) mod n) = (0, 0),即无论怎么分配,走 n^2 步之后都会返回起点。

但是只保证走 n^2 步后返回起点还不够,要保证这 n^2 步经过的点都是不相同的。考虑从起点走 kn 步后会到哪里,因为 kn步经过了 k 轮次对角线,所以往右走了 ki 步,往下走了 k(n − i)步,即到了 (ki mod n, k(n − i) mod n) 这个点。我们需要保证当 k < n 时,这个点都不为 (0, 0)。

即问多少个 i 满足 ki mod n = 0, k(n - i) mod n = 0 当1 < k < n 时都不成立。显然当且仅当 gcd(i, n) = 1 时满足。所以枚举往右走的步数 i,只有 gcd(i, n) = 1 时有贡献,贡献为 n!/[i!(n-i)!]。故答案为:
5.png

接下来考虑 n ̸= m 的情况,根据之前讨论,如果有解那么gcd(n, m) = g ̸= 1。画图后发现此时的网格共有 g 条次对角线,和 n = m 时使用相同的办法,可以发现当且仅gcd(i, n) = 1, gcd(g -i, m) = 1 时对答案有贡献,贡献为g!/[i!*(g-i)!]。所以答案为:
6.png
所以这道题就解决了!(听说NOI2018的冠军zzq6分钟就AC了这道题QwQ)

乌鸦抓松鼠

题目描述

给出一个 n 个点的树,开始时树上有两只乌鸦和一只松鼠,位于不同位置。现在要进行若干论操作,每轮操作将分为三步:
1、你选择一个乌鸦飞到天上。
2、松鼠在树上随机移动,但不能经过另一只乌鸦。
3、在天上的乌鸦降落回树上(落的位置在第一步确定)。
如果某次降落后,乌鸦恰好在松鼠所在位置,那么松鼠被抓住。问如何操作乌鸦,使得在最坏情况下抓住松鼠的步数最少。(2 ≤ n ≤ 10^5)

解题思路

在树上可能比较难思考,我们首先考虑一条链的情况:一种策略是两只乌鸦借助边界一步一步卡松鼠的活动范围:
7.png
还有一种策略是某只乌鸦先到某一点,使得松鼠的活动范围减小,之后两只乌鸦再借助边界卡松鼠:
8.png

树上也是如此:
一种情况是以某只乌鸦为根,之后两只乌鸦轮流将松鼠往子树中卡,此时答案就是根的松鼠方向的儿子的子树的最大深度。

另一种情况是某只乌鸦先跳到某个点上,并以该点为根,接下来同上一种情况。对于第二种情况,需要枚举第一步前往的所有点,所以复杂度 O(n^2)。当然这个复杂度是过不了的,我们考虑一下优化。

注意到第二种情况的答案就是:
9.png
也即:
10.png
显然这个数为直径除以二上取整。时间复杂度 O(n)。

添加符号

题目描述

给出 n 个数,在这 n 个数的 n-1 个间隔中加入加号或乘号,问对于所有的 2^(n-1) 种情况,所有表达式的值的和为多少。答案模 10^9 + 7。
同时你还要支持 q 次修改操作:每次给你两个数 p b,表示把 p 处的值修改为 b,输出修改后的答案。1 ≤ n, q ≤ 10^5。

解题思路

首先不考虑修改操作:
用一个二元组 (ai, bi) 来表示一个表达式的值,含义为这个表达式最后一个加号前的结果为 ai,最后一个加号之后的数的乘积为 bi。那么如果在这个表达式后面加入一个数 c,将会产生两个新表达式 (ai + bi, c) 和 (ai, bi × c)。设当前一共有 n 个二元组,那么加入一个 c 之后,将变成2n 个二元组。

这么写有上面好处呢?我们设我们当前有n个表达式,我们看下图:

11.png

我们发现,设之前所有二元组的和为 (A,B),那么加入一个 c 之后,将变成 (2A + B, c(n + B))。所以只要扫一遍并维护 A, B, n 即可。时间复杂度 O(n)。

考虑转移 (A,B, n) → (2A + B, c(n + B), 2n)。写成矩阵形式:

12.png

所以答案即为若干个矩阵的连乘,修改 c 即修改某个位置的矩阵。线段树维护即可,时间复杂度 O(n log n)。

最后再介绍一下线段树如何维护矩阵吧,我们每个叶子节点都是一个关于c的矩阵,第i个c要改变,就修改第i个叶子节点的矩阵,每个父亲节点代表的是其两个儿子节点的矩阵乘积,所以根节点就是我们的答案了,如下图:

13.png
到这里这道题就结束啦。

结语

这篇BLOG我们介绍了一种很重要的思想——从特殊到一般,这是在众多学科中都适用的规律,最后希望你能掌握这项技能,也希望你能喜欢这篇BLOG!

Last modification:January 29th, 2019 at 10:06 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment