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

Cutest_Junior · 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();
    }
}