LCS

题意：给出两个序列a_n和b_n，想在给出一个序列p_n，问经过a[p₁],,,,a[p_n]和b[p₁],,,b[p_n]变换后序列a和序列b的最长公共子序列的长度是多少。

思路：对a[i]->b[i]建边，最终总能形成一个环，对于这个长度为L的环，我们总能找到一个长度为L-1的LCS。所以，我们只要用序列的长度减去长度大于1的环的个数就是最终的结果。

例如：

　　　

代码：

#include 
      
       using namespace std;const int maxn = 1e5+10;typedef long long ll;int a[maxn],b[maxn],c[maxn];int vis[maxn];inline void init(){    memset(vis,0,sizeof(vis));    return;}int main(){    int T;    scanf("%d",&T);    while(T--)    {        init();        int n;        scanf("%d",&n);        for(int i = 1; i<=n; i++)            scanf("%d",&a[i]);        for(int i = 1; i<=n; i++)        {            scanf("%d",&b[i]);            c[a[i]] = b[i];        }        int ans = n;        for(int i = 1; i<=n; i++)        {            int t = i;            if(c[t] != t && !vis[t])            {                ans--;                while(!vis[t])                {                    vis[t] = 1;                    t = c[t];                }            }        }        printf("%d\n",ans);    }    return 0;}/*样例输入：231 2 33 2 161 5 3 2 6 43 6 2 4 5 1样例输出：24*/