把每个兴奋值看成一个状态值，若某个兴奋值 x 能选择一个结束兴奋值为 y 的游戏，就连边 x->y；某个游戏能玩两次，当且仅当它的 e_i 能回到某个整除 w_i 的同 SCC 状态。
OJ: luogu
题目 ID: P5676
难度:提高+/省选-
标签:图论强连通分量tarjan
日期: 2026-06-20 02:22
题意
有 N 个游戏。
- 第
i个游戏的“看上去有趣程度”是w_i - 玩完它以后，兴奋程度会变成
e_i
小 z 只会玩那些满足下面条件的游戏：
- 当前兴奋程度
x能整除这个游戏的w_i
初始兴奋程度是 1。
问有多少个游戏“有可能被玩两次”。
这里的“可能”表示：
- 存在某种选择顺序
- 让这个游戏在整条序列中出现至少两次
样例图
用样例二来画状态转移图更直观。
样例二的 5 个游戏是：
w = [2, 3, 5, 35, 21]e = [7, 11, 7, 3, 2]
这张图展示“玩完一个游戏后，下一步还能选哪些游戏”：
digraph G {
1 -> 5;
3 -> 5;
4 -> 2;
4 -> 5;
5 -> 4;
}
其中 2,4,5 之间能绕成环，所以它们可能被再次玩到。
而 1、3 虽然能走出去，但回不来，所以不能玩第二次。
思路
先看一个最直接的小数据图论版：
cpp
// brute.cpp：直接在“游戏之间”的图上建边，再求强连通分量。
// 如果一个游戏所在的强连通分量大小大于 1，或者自己有自环，
// 那么它就可能在某条游玩顺序里被玩两次。
#include <bits/stdc++.h>
using namespace std;
int t;
int n;
vector<int> w, e_val;
vector< vector<int> > g, rg;
vector<int> order, scc_id, scc_size;
vector<char> vis, self_loop;
void dfs1(int u) {
vis[u] = 1;
for (size_t i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (!vis[v]) {
dfs1(v);
}
}
order.push_back(u);
}
void dfs2(int u, int color) {
scc_id[u] = color;
scc_size[color]++;
for (size_t i = 0; i < rg[u].size(); i++) {
int v = rg[u][i];
if (scc_id[v] == 0) {
dfs2(v, color);
}
}
}
int solve_case() {
cin >> n;
w.assign(n + 1, 0);
e_val.assign(n + 1, 0);
for (int i = 1; i <= n; i++) {
cin >> w[i];
}
for (int i = 1; i <= n; i++) {
cin >> e_val[i];
}
g.assign(n + 1, vector<int>());
rg.assign(n + 1, vector<int>());
self_loop.assign(n + 1, 0);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (w[j] % e_val[i] == 0) {
g[i].push_back(j);
rg[j].push_back(i);
if (i == j) {
self_loop[i] = 1;
}
}
}
}
vis.assign(n + 1, 0);
order.clear();
order.reserve(n);
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
dfs1(i);
}
}
scc_id.assign(n + 1, 0);
scc_size.assign(n + 1, 0);
int scc_cnt = 0;
for (int i = (int)order.size() - 1; i >= 0; i--) {
int u = order[i];
if (scc_id[u] == 0) {
scc_cnt++;
dfs2(u, scc_cnt);
}
}
int answer = 0;
for (int i = 1; i <= n; i++) {
if (scc_size[scc_id[i]] > 1 || self_loop[i]) {
answer++;
}
}
return answer;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> t;
while (t--) {
cout << solve_case() << '\n';
}
return 0;
}brute.cpp 的想法是：
- 把每个游戏看成一个点
- 如果玩完游戏
i后，兴奋值e_i能整除w_j，就连边i -> j - 某个游戏能玩两次，当且仅当它所在的图里存在回路能回到自己
所以在这个“游戏图”里，答案就是：
- 处在非平凡强连通分量里的点
- 或者自己有自环的点
这个建模是对的，但如果直接建游戏图，边数最坏可能是
关键优化是：
后续能选什么游戏，只和“当前兴奋程度”有关，和你刚才玩的是哪个游戏无关。
于是把点改成“兴奋值”会更自然：
- 图上的一个点表示某个可能出现的兴奋值
- 如果当前兴奋值是
x，存在某个游戏满足x | w_i，且玩完后兴奋值变成e_i - 那么就在值图里连边
x -> e_i
现在考虑某个具体游戏 i 什么时候能玩两次。
第一次玩完它以后，兴奋值会变成 e_i。
如果以后还能再次玩到它，说明中间经过若干步后，当前兴奋值一定变成了某个 x，并且：
x能整除w_i
这样才能再次选择游戏 i。
所以游戏 i 能玩两次，当且仅当：
- 从值
e_i出发，能够走到某个整除w_i的值x
而一旦有这样的 x，由于“再次玩游戏 i”本身就对应一条边 x -> e_i，所以：
x和e_i一定在同一个强连通分量里
于是判定条件就变成了：
- 枚举
w_i的所有约数里，哪些本身是某个出现过的兴奋值 - 只要其中有一个约数值和
e_i属于同一个 SCC，游戏i就能玩两次
这样我们只需要在“不同兴奋值个数”这层图上跑一次 SCC，复杂度就降下来了。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
struct Frame {
int u; // 当前点
int iter_edge; // 当前枚举到哪条边
};
int t;
int n;
vector<int> w, e_val;
// 缩点后的“兴奋程度值图”。
vector<int> head, to, nxt;
int edge_cnt;
vector<int> dfn, low, parent_node, scc_id;
vector<int> tarjan_stack;
vector<char> in_stack;
int dfs_clock, scc_cnt;
unordered_map<int, int> value_id;
unordered_map<int, vector<int> > divisor_cache;
void add_edge(int u, int v) {
to.push_back(v);
nxt.push_back(head[u]);
edge_cnt++;
head[u] = edge_cnt;
}
// 找出 w 的所有“同时也是某个 e 值”的约数，对应的图节点编号。
vector<int> &get_divisor_nodes(int x) {
unordered_map<int, vector<int> >::iterator it = divisor_cache.find(x);
if (it != divisor_cache.end()) {
return it->second;
}
vector<int> res;
for (int d = 1; 1LL * d * d <= x; d++) {
if (x % d != 0) {
continue;
}
unordered_map<int, int>::iterator it1 = value_id.find(d);
if (it1 != value_id.end()) {
res.push_back(it1->second);
}
int d2 = x / d;
if (d2 != d) {
unordered_map<int, int>::iterator it2 = value_id.find(d2);
if (it2 != value_id.end()) {
res.push_back(it2->second);
}
}
}
divisor_cache[x] = res;
return divisor_cache[x];
}
// 非递归 Tarjan 求强连通分量，避免值图退化成长链时爆栈。
void tarjan_scc(int start) {
vector<Frame> call_stack;
call_stack.push_back({start, head[start]});
parent_node[start] = 0;
dfn[start] = low[start] = ++dfs_clock;
tarjan_stack.push_back(start);
in_stack[start] = 1;
while (!call_stack.empty()) {
Frame &cur = call_stack.back();
int u = cur.u;
if (cur.iter_edge != 0) {
int e = cur.iter_edge;
cur.iter_edge = nxt[e];
int v = to[e];
if (!dfn[v]) {
parent_node[v] = u;
dfn[v] = low[v] = ++dfs_clock;
tarjan_stack.push_back(v);
in_stack[v] = 1;
call_stack.push_back({v, head[v]});
continue;
}
if (in_stack[v]) {
low[u] = min(low[u], dfn[v]);
}
continue;
}
call_stack.pop_back();
if (parent_node[u] != 0) {
int p = parent_node[u];
low[p] = min(low[p], low[u]);
}
if (low[u] == dfn[u]) {
scc_cnt++;
while (true) {
int x = tarjan_stack.back();
tarjan_stack.pop_back();
in_stack[x] = 0;
scc_id[x] = scc_cnt;
if (x == u) {
break;
}
}
}
}
}
int solve_case() {
cin >> n;
w.assign(n + 1, 0);
e_val.assign(n + 1, 0);
for (int i = 1; i <= n; i++) {
cin >> w[i];
}
for (int i = 1; i <= n; i++) {
cin >> e_val[i];
}
vector<int> values;
values.reserve(n);
for (int i = 1; i <= n; i++) {
values.push_back(e_val[i]);
}
sort(values.begin(), values.end());
values.erase(unique(values.begin(), values.end()), values.end());
int value_cnt = values.size();
value_id.clear();
value_id.reserve(value_cnt * 2 + 5);
for (int i = 0; i < value_cnt; i++) {
value_id[values[i]] = i + 1;
}
divisor_cache.clear();
divisor_cache.reserve(n * 2 + 5);
head.assign(value_cnt + 1, 0);
to.assign(1, 0);
nxt.assign(1, 0);
edge_cnt = 0;
// 建值图：x -> e_i，表示当前兴奋值是 x 时，可以选择第 i 个游戏。
for (int i = 1; i <= n; i++) {
int target = value_id[e_val[i]];
vector<int> &div_nodes = get_divisor_nodes(w[i]);
for (size_t j = 0; j < div_nodes.size(); j++) {
add_edge(div_nodes[j], target);
}
}
dfn.assign(value_cnt + 1, 0);
low.assign(value_cnt + 1, 0);
parent_node.assign(value_cnt + 1, 0);
scc_id.assign(value_cnt + 1, 0);
in_stack.assign(value_cnt + 1, 0);
tarjan_stack.clear();
tarjan_stack.reserve(value_cnt);
dfs_clock = 0;
scc_cnt = 0;
for (int i = 1; i <= value_cnt; i++) {
if (!dfn[i]) {
tarjan_scc(i);
}
}
int answer = 0;
// 游戏 i 能玩两次：
// e_i 可以走到某个 x，并且 x 能再次选择 i。
// 后者等价于 x | w_i，所以只要找到一个与 e_i 同 SCC 的约数值 x 即可。
for (int i = 1; i <= n; i++) {
int my_scc = scc_id[value_id[e_val[i]]];
vector<int> &div_nodes = get_divisor_nodes(w[i]);
bool ok = false;
for (size_t j = 0; j < div_nodes.size(); j++) {
if (scc_id[div_nodes[j]] == my_scc) {
ok = true;
break;
}
}
if (ok) {
answer++;
}
}
return answer;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> t;
while (t--) {
cout << solve_case() << '\n';
}
return 0;
}复杂度
设不同兴奋值个数为 K。
值图上的节点数是 K，建边时只会枚举每个 w_i 的约数，所以：
- 时间复杂度主要是
- 在本题范围内可以视为线性到近线性
空间复杂度：
总结
这题最重要的转化不是 Tarjan 本身，而是：
- 后续可选游戏只取决于当前兴奋值，不取决于上一个游戏是谁
一旦把“游戏图”压成“兴奋值图”，问题就变成了一个很标准的 SCC 判定：
- 建值图
- 跑强连通分量
- 对每个游戏检查：
w_i的某个约数值，是否和e_i在同一个 SCC
这样就把原本看起来像博弈/搜索的问题，改写成了纯图论题。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
