HDU 5495 LCS（数论）

小咪咪 2022-08-09 01:59 140阅读 0赞

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5495  
参考博客：  
http://blog.csdn.net/queuelovestack/article/details/48882935  
(写的也非常详细)

解题思路：这两个序列会构成许多环，并且环之间相互不干扰，结果为长度大于1的环长度减1，长度为1的环直接相加即可。  
来解释一下这个环：  
先看样例：

6  
1 5 3 2 6 4  
3 6 2 4 5 1

a\[x\]代表a中的x  
b\[x\]代表b中的x

这是一个环：a\[1\]->b\[3\]->a\[3\]->b\[2\]->a\[2\]->b\[4\]->a\[4\]->b\[1\]  
另一个是:a\[5\]->b\[6\]->a\[6\]->a\[5\]  
因为每个序列都是1到n，所以肯定能有许多不相干的环，并且分析一下可知，每个环的长度减一相加，再加上所有长度为1的环的长度，便都是对应的答案  
所以我们按a排序一下，可得  
1 2 3 4 5 6  
3 4 2 1 6 5  
这样当我们得知b中的值之后，便可以很快的得到a序列中对应的另一个b值。  
如我们可知 b\[1\]=3 a\[3\]=2 （2为另一个b的值）

AC代码：

#include <map>
    #include <set>
    #include <list>
    #include <stack>
    #include <queue>
    #include <deque>
    #include <cmath>
    #include <ctime>
    #include <cstdio>
    #include <vector>
    #include <bitset>
    #include <sstream>
    #include <cstdlib>
    #include <complex>
    #include <climits>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define Cl0(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9;
    const int inf1=-1*1e9;
    typedef long long LL;
    struct Node
    {
        int a,b;
    } node[100005];
    bool cmp(Node a,Node b)
    {
        return a.a<b.a;
    }
    bool used[100005];
    int main()
    {
        int cas;
        scanf("%d",&cas);
        while(cas--)
        {
            Cl0(used);
            int n;
            RI(n);
            for(int i=0; i<n; i++)
            {
                RI(node[i].a);
            }
            for(int i=0; i<n; i++)
            {
                RI(node[i].b);
            }
            sort(node,node+n,cmp);
            int ans=0;
            for(int i=1; i<=n; i++)
            {
                if(!used[i])
                {
                    int l=1;
                    int p=node[i-1].b;
                    while(p!=i)
                    l++,used[p]=true,p=node[p-1].b;
                    used[i]=true;
                    if(l>1) ans+=l-1;
                    else ans++;
                }
            }
            printf("%d\n",ans);
        }
        return  0;
    }