自动搬运

查看原文

来自洛谷，原作者为

	Cutest_Junior 平平淡淡才是真

搬运于2025-08-24 22:13:16，当前版本为作者最后更新于2021-01-07 21:15:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解 P5676 【[GZOI2017]小z玩游戏】

题意

• 有 $n$ 个游戏，有趣程度为 $w$，玩完后兴奋程度会变为 $e$；
• 每次只会玩有趣程度是兴奋程度整数倍的游戏，一开始兴奋程度为 $1$；
• 不超过 $10$ 组数据，$n,w,e\le10^5$。

做法

相信很多人一开始都和我一样，想对于任意两个游戏，判断是否建边，然后跑一遍 Tarjan。

但是这样的复杂度是 $O(n^2)$ 的，无法通过 $10^5$ 的数据。

我们换一种思考方式。重新构造脑子。

若当前兴奋值为 $a$，某个游戏有趣程度为 $w$，兴奋程度为 $e$，$w$ 是 $a$ 的倍数。

可以视为兴奋值先从 $a$ 变成了它的倍数 $w$，再变成 $e$。

那我们就可以对每个数向它的倍数建边，再对于每个游戏从 $w$ 向 $e$ 建边。

跑一遍 Tarjan，对于每个游戏判断 $w$ 和 $e$ 是否在同一强连通分量。

建边复杂度 $O(n\log n)$，可以通过。

代码

#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
#include <cstring>

using namespace std;

const int N = 1e5 + 5;

vector<int> edge[N];

void add(int u, int v) {
	edge[u].push_back(v);
}

int dfn[N], dfstot;
int low[N];
int scc[N], scctot;

stack<int> sta;

void tarjan(int x) {
	dfn[x] = low[x] = ++dfstot;
	sta.push(x);
	for (int i = 0; i < edge[x].size(); ++i) {
		int to = edge[x][i];
		if (dfn[to] == 0) {
			tarjan(to);
			low[x] = min(low[x], low[to]);
		}
		else if (scc[to] == 0) {
			low[x] = min(low[x], dfn[to]);
		}
	}
	if (low[x] == dfn[x]) {
		++scctot;
		while (1) {
			int t = sta.top();
			sta.pop();
			scc[t] = scctot;
			if (t == x) {
				break;
			}
		}
	}
}

int arr1[N], arr2[N];

void run() {
	memset(dfn, 0, sizeof dfn);
	memset(low, 0, sizeof low);
	memset(scc, 0, sizeof scc);
	dfstot = scctot = 0;
	for (int i = 0; i < N; ++i) {
		edge[i].clear();
	}
	for (int i = 1; i + i < N; ++i) {
		for (int j = 2; j * i < N; ++j) {
			add(i, j * i);
		}
	}
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &arr1[i]);
	}
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &arr2[i]);
		add(arr1[i], arr2[i]);
	}
	for (int i = 1; i < N; ++i) {
		if (dfn[i] == 0) {
			tarjan(i);
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; ++i) {
		if (scc[arr1[i]] == scc[arr2[i]]) {
			++ans;
		}
	}
	printf("%d\n", ans);
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		run();
	}
}