Time Limit: 1 Sec

Memory Limit: 256 MB

题目连接

http://acm.hdu.edu.cn/showproblem.php?pid=5495

Description

你有两个序列\{a_1,a_2,...,a_n\}{a​1​​,a​2​​,...,a​n​​}和\{b_1,b_2,...,b_n\}{b​1​​,b​2​​,...,b​n​​}. 他们都是11到nn的一个排列. 你需要找到另一个排列\{p_1,p_2,...,p_n\}{p​1​​,p​2​​,...,p​n​​}, 使得序列\{a_{p_1},a_{p_2},...,a_{p_n}\}{a​p​1​​​​,a​p​2​​​​,...,a​p​n​​​​}和\{b_{p_1},b_{p_2},...,b_{p_n}\}{b​p​1​​​​,b​p​2​​​​,...,b​p​n​​​​}的最长公共子序列的长度最大.

Input

输入有多组数据, 第一行有一个整数TT表示测试数据的组数. 对于每组数据:

第一行包含一个整数n (1 \le n \le 10^5)n(1≤n≤10​5​​), 表示排列的长度. 第2行包含nn个整数a_1,a_2,...,a_na​1​​,a​2​​,...,a​n​​. 第3行包含nn个整数 b_1,b_2,...,b_nb​1​​,b​2​​,...,b​n​​.

数据中所有nn的和不超过2 \times 10^62×10​6​​.

2

3

1 2 3

3 2 1

6

1 5 3 2 6 4

3 6 2 4 5 1

Sample Output

2

4

#include<iostream>

#include<stdio.h>

#include<queue>

#include<map>

#include<algorithm>

using namespace std;

int a[];

int b[];

int c[];

int vis[];

int main()

{

    int n;

    int t;scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        for(int i=;i<=n;i++)

        {

            scanf("%d",&a[i]);

            vis[i]=;

        }

        for(int i=;i<=n;i++)

            scanf("%d",&b[i]);

        for(int i=;i<=n;i++)

            c[a[i]]=b[i];

        int ans = n;

        for(int i=;i<=n;i++)

        {

            int x=i;

            if(vis[x])continue;

            if(c[x]!=x)

            {

                ans--;

                while(!vis[x])

                {

                    vis[x]=;

                    x=c[x];

                }

            }

        }

        printf("%d\n",ans);

    }

}