P5676 [GZOI2017]小z玩游戏

CuSO4_and_5H2O · 2022-07-09 17:54:01 · 题解

思路

第一眼看到这个题目的时候感觉很简单，求强连通分量，然后看看有几个点的 w_i 和 e_i 在一个强联通分量里，那就是答案。但是突然发现如果输入一个点就要和其他的点租比较的话时间会爆炸，然后我就想到不如把所有 e_i 的倍数枚举一遍，这样就可以了（对于没用的也没必要管因为最后是统计所有 w_i 和 e_i 是否在一个强联通分量里，所以不会影响答案的），这样时间复杂度就很小了。看到这里，我自信了丢掉草纸准备自己做出来，之后做完了发现一点都不对，接下来我会列举几个我做的时候遇到的坑。

1. 是枚举 e_i 的倍数而不是 w_i 的，这个还是比较好发现的，也不容易出错（是我菜了所以才会错这个点的）。
1. 枚举所有 e_i 的倍数的时候倍数乘以 e_i 的数值限制一定是你定的 N-1（这里的 N 是定的数组大小，如果你没定 N 就是你的比你数组的大小少一），这么说可能不太清楚，上代码。

for(int i=1; i<=n; i++) {
    cin>>b[i],vec[a[i]].push_back(b[i]);
    for(int j=2; !Map[b[i]] && j*b[i]<N; j++) //就是这里的<N了，如果是<=的话会错，因为他如果等于N的话到上边的tarjan代码的时候会访问vis[N]等数组，但是这些数组的范围是0到N-1的不包括N所以会出错
        vec[b[i]].push_back(j*b[i]);
    Map[b[i]]=114514;
}

1. 我做的时候有一段时间对了六个点，空间超限了四个点，这是因为 vector 数组重复建了太多的边了导致空间爆掉，你肯能会问为什么会重复建边呢，下边个样例。

M(这里 M 指的是个很大的数)
#daa..adw##@!.ads%#.ads(这里泛指很多数字这行数字不重要)
1 1 1 1 1 1 1 ……1(有 M 个1)

这样的话要建 M \times 100005 条边假如 M 很大的话空间当然会爆，但是这些边都是重复的，其实只要建一次就好了，所以我们可以建立一个数组来查看这个点的是否建边，这样就不会爆空间啦！

代码

这里就是代码了，题目并不难，看了思路之后自己打出来，代码也很好理解。

#include<bits/stdc++.h>
#define int long long
const int N=1e5+10;
using namespace std;

int n,a[N],b[N];
vector<int> vec[N];
int Map[N];
int jis,wuy[N],low[N],dfn[N],cnt,vis[N];
int ans;
stack<int> sta;

void tarjan(int x)
{
    sta.push(x);vis[x]=1;
    low[x]=dfn[x]=++cnt;
    for(int i=0;i<vec[x].size();i++)
    {
        int nex=vec[x][i];
        if(!dfn[nex]){
            tarjan(nex);
            low[x]=min(low[x],low[nex]); 
        } else if(vis[nex]) low[x]=min(low[x],dfn[nex]); 
    }
    if(low[x]==dfn[x])
    {
        jis++;
        while(1)
        {
            vis[sta.top()]=0;
            wuy[sta.top()]=jis;
            vis[sta.top()]=0;
            if(sta.top()==x) break ;
            sta.pop();
        }
        sta.pop();
    }
}

signed main(){
    int t;
    cin>>t;
    for(int qwq=1;qwq<=t;qwq++)
    {
    memset(dfn, 0, sizeof dfn);
    memset(low, 0, sizeof low);
    memset(wuy, 0, sizeof wuy);
    memset(vis, 0, sizeof vis);
    memset(Map, 0, sizeof Map);
    cnt=jis=ans=0;
    for (int i = 0; i < N; ++i) 
        vec[i].clear();
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        cin>>b[i],vec[a[i]].push_back(b[i]);
        for(int j=2;!Map[b[i]] && j*b[i]<N;j++)//把每个e_i枚举一遍 
            vec[b[i]].push_back(j*b[i]);
        Map[b[i]]=114514;//标记 
    }
    for(int i=1;i<=n;i++) if(!dfn[a[i]]) tarjan(a[i]);
    for(int i=1;i<=n;i++) if(wuy[a[i]]==wuy[b[i]]) ans++;
    cout<<ans<<endl;    
    }
}