CodeForces 1200F

缺乏、安全感 2023-08-17 16:37 70阅读 0赞

题意略。

思路：

如果是问一下然后搜一下，那必然是不现实的。因此我们要预处理出所有的答案。

我们令mod = lcm(m1,m2,...,mn)。可知，在任意一点，我们挑选两个不同的数c1、c2，其中c2 = k \* mod + c1，这两种出发状态一定会走出相同的路径。

由此，我们把每个点拆成mod个状态点，那一共是n \* mod个点，由每个状态点只引申出来一条只想别的点的边，我们其实就是要在这个有向图中找环，

找环后统计环上不同点的个数。

开始的时候，我以为环的个数不会超过实际点的个数，后来wa了一次，发现同一个实际点其实是可以在不同的环中的。

代码如下：

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 2520005;
    const int maxm = 2520005;
    const int maxp = 1005;
    
    int connect[maxn],belong[maxn],scc[maxn],cnt;
    int stk[maxn],tail;
    bool visit[maxn];
    
    int n,mstore[maxp],kstore[maxp],mod = 1;
    vector<int> graph[maxp];
    set<int> st,sst;
    
    void add_e(int u,int v){
        connect[u] = v;
    }
    int gcd(int a,int b){
        return b == 0 ? a : gcd(b,a % b);
    }
    int lcm(int a,int b){
        int d = gcd(a,b);
        return a / d * b;
    }
    void dfs(int p){
        if(visit[p]) return;
        st.clear();
        sst.clear();
        tail = 0;
        while(!visit[p]){
            visit[p] = true;
            stk[tail++] = p;
            st.insert(p);
            p = connect[p];
        }
        if(st.count(p)){
            int idx = cnt++;
            while(stk[tail - 1] != p){
                int cur = stk[--tail];
                belong[cur] = idx;
                cur = cur / mod + 1;
                sst.insert(cur);
            }
            --tail;
            sst.insert(p / mod + 1);
            belong[p] = idx;
            scc[idx] = sst.size();
        }
        for(int i = 0;i < tail;++i){
            belong[stk[i]] = belong[p];
        } 
        
    }
    
    int main(){
        scanf("%d",&n);
        for(int i = 1;i <= n;++i) scanf("%d",&kstore[i]);
        for(int i = 1;i <= n;++i){
            scanf("%d",&mstore[i]);
            int m = mstore[i],temp;
            mod = lcm(mod,m);
            for(int j = 0;j < m;++j){
                scanf("%d",&temp);
                graph[i].push_back(temp);
            }
        }
        for(int i = 1;i <= n;++i){
            int m = mstore[i];
            for(int j = 0;j < mod;++j){
                int to = graph[i][j % m];
                int keep = to;
                to = j + kstore[to];
                to = (to % mod + mod) % mod;
                to = (keep - 1) * mod + to;
                int from = (i - 1) * mod + j;
                add_e(from,to);
            }
        }
        int tot = n * mod;
        for(int i = 0;i < tot;++i) dfs(i);
        int x,y,q;
        scanf("%d",&q);
        for(int i = 0;i < q;++i){
            scanf("%d%d",&x,&y);
            y = (y + kstore[x]) % mod;
            y = (y + mod) % mod;
            int cur = (x - 1) * mod + y;
            int fa = belong[cur];
            int ans = scc[fa];
            printf("%d\n",ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/tiberius/p/11403519.html