Dyd's Blog

He who has a strong enough why can bear almost any how.

luoguP4616 [COCI2017-2018#5] Pictionary

Posted on Edited on In
Symbols count in article: 2.6k Reading time ≈ 2 mins.

不要老往数学上想

Pictionary

第一反应是 $O(n^2)$ 40分的做法（很显然），直接 $O(n\sqrt{n})$ 把每个数分解，建图连边，再从大到小扫描每个因数，由此处理出所有 $gcd(a, b)$ ，这里是 $O(n^2)$ ，然后暴力枚举 $i : 1 \rightarrow m$ ，并查集维护即可，这里是 $O(n\log n)$

但满数据 $n \le 10^5$ 肯定不允许 $n^2$ ，空间时间都挂了

仔细看，上面的瓶颈主要在求 $gcd(a, b)$ 只要我们要求出所有 $gcd$ ，就一定会有一个 $n^2$ 的时空复杂度，这显然应该放弃，那么考虑题目可否不求或者不求出全部的 $gcd$

发现题目的问题有一下性质：

  1. 这 $n$ 个数是 $1 \sim n$ 连续的（我以为很有用，然并卵）
  2. 只是询问图的联通性，不询问具体的两个数的 $gcd$
  3. 答案求的是一个最值
  4. 图建好后，询问不会再改变图了

除开第一个误导我好久的性质，我们来看看其它性质如何使用：

首先最好用的是性质3，它明显提示我们建一个有权值的图，将询问转化为求权值，具体的，可以建一棵有边权的树，权值对应的时间，两个点之间的路径上的最大边权就是答案

现在主要问题在建图了，再看现性质2，明显我们不必也不能求 $gcd$ 来建图，正难则反，考虑可否枚举倍数，发现在只关注图的联通性的情况下，每天连出的边等效于从第 $m - i + 1$ 号城向它的所有倍数号城连边，边权就是天数，正确性显然，而这样建图，时间复杂度为 $O(\frac{n}{1} + \frac{n}{2} + … + \frac{n}{n}) = O(n)$ ，但我们要的是树，毕竟如果有多条路径就不好处理了，于是用类似最小生成树的思想，取最小的边权（其实就是天数最小）加入树中，用并查集维护联通性，一共是 $O(n \log n)$

现在树建好了，性质2、3也都用了，来考虑询问，上面说过，两个点之间的路径上的最大边权就是答案，但每次暴力求权值肯定不行，结合 $n \le 10^5$ 和所求问题，不难想到树链剖分，如果是树剖，当然，本题得以解决

但是考虑性质4，树剖是支持修改和区间操作的，用在本题这静态的图上不免大材小用（主要是调不出来），于是思考，可否用一个预处理后在 $O(\log n)$ 内回答询问

当然是可以的，考虑树上倍增，用ST表+lca即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, D = 25, INF = 0x3f3f3f3f;
int n, m;
struct Edge
{
	int ne, ver, w;
} e[N << 1];
int h[N], idx;
int fa[N];
int f[N][D], st[N][D], dep[N];
void add(int x, int y, int z)
{
	e[idx] = (Edge){h[x], y, z}, h[x] = idx++;
}
int get_f(int x)
{
	return x == fa[x] ? x : fa[x] = get_f(fa[x]);
}
void build()
{
	for (int i = m, u, v; i >= 1; --i)
		for (int j = i + i; j <= n; j += i)
		{
			u = get_f(i), v = get_f(j);
			if (u != v)
			{
				fa[u] = v;
				add(i, j, m - i + 1);  //i枚举的是m-i+1的值,所以这里要变回来
				add(j, i, m - i + 1);
			}
		}
}
void bfs()
{
	queue<int> q;
	dep[1] = 1;
	st[1][0] = 0;
	q.push(1);
	int x, y;
	while (!q.empty())
	{
		x = q.front(), q.pop();
		for (int i = h[x]; i != -1; i = e[i].ne)
		{
			y = e[i].ver;
			if (y == f[x][0])
				continue;
			dep[y] = dep[x] + 1;
			f[y][0] = x;
			st[y][0] = e[i].w;
			for (int i = 1; i < D; ++i)
			{
				f[y][i] = f[f[y][i - 1]][i - 1];
				st[y][i] = max(st[y][i - 1], st[f[y][i - 1]][i - 1]);
			}
			q.push(y);
		}
	}
}
int get_ans(int x, int y) //类似lca
{
	int res = 0;
	if (dep[y] < dep[x])
		swap(x, y);
	for (int i = D - 1; i >= 0; --i)
		if (dep[f[y][i]] >= dep[x])
		{
			res = max(res, st[y][i]);
			y = f[y][i];
		}
	if (x == y)
		return res;
	for (int i = D - 1; i >= 0; --i)
		if (f[x][i] != f[y][i])
		{
			res = max(res, max(st[y][i], st[x][i]));
			y = f[y][i], x = f[x][i];
		}
	return max(res, max(st[x][0], st[y][0]));
}
int main()
{
	int Q, u, v;
	scanf("%d%d%d", &n, &m, &Q);
	for (int i = 1; i <= n; ++i)
		h[i] = -1, fa[i] = i;
	idx = 0;
	for (int i = 1; i <= n; ++i)
		for (int j = 0; j < D; ++j)
			st[i][j] = INF;
	build();
	bfs();
	while (Q--)
	{
		scanf("%d%d", &u, &v);
		printf("%d\n", get_ans(u, v));
	}
	return 0;
}