hdu 5495 LCS 水题

LCS

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??.

Output

对于每组数据, 输出LCS的长度.

Sample Input

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

HINT

题意

题解:

建边,a[i]->b[i]这样建边,对于其中构成的长度为l的环,我们能构造出长度为l-1的lcs

所以答案就是n-环的个数

代码:

#include<iostream>
#include<stdio.h>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;

int a[100500];
int b[100500];
int c[100500];
int vis[100500];
int main()
{
    int n;
    int t;scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            vis[i]=0;
        }
        for(int i=1;i<=n;i++)
            scanf("%d",&b[i]);
        for(int i=1;i<=n;i++)
            c[a[i]]=b[i];
        int ans = n;
        for(int i=1;i<=n;i++)
        {
            int x=i;
            if(vis[x])continue;
            if(c[x]!=x)
            {
                ans--;
                while(!vis[x])
                {
                    vis[x]=1;
                    x=c[x];
                }
            }
        }
        printf("%d\n",ans);
    }
}
时间: 10-03

hdu 5495 LCS 水题的相关文章

HDU 2092 整数解 --- 水题

x+y = n, x*y = m; y = n - x; x * ( n - x) = m nx - x^2 = m; x^2 - nx + m = 0; △ = sqrt(n^2 - 4m) 要有整数解即△需要为可开方数即可. /* HDU 2092 整数解 --- 水题 */ #include <cstdio> #include <cmath> int main() { double n, m; while (scanf("%lf%lf", &n,

hdu 5210 delete 水题

Delete Time Limit: 1 Sec  Memory Limit: 256 MB 题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=5210 Description wld有n个数(a1,a2,...,an),他希望进行k次删除一个数的操作,使得最后剩下的n−k个数中有最多的不同的数,保证1≤n≤100,0≤k<n,1≤ai≤n(对于任意1≤i≤n) Input 多组数据(最多100组)对于每组数据:第一行:一个数n表示数的个数接下来一行:

HDU 5703 Desert 水题 找规律

已知有n个单位的水,问有几种方式把这些水喝完,每天至少喝1个单位的水,而且每天喝的水的单位为整数.看上去挺复杂要跑循环,但其实上,列举几种情况之后就会发现是找规律的题了= =都是2的n-1次方,而且这题输出二进制数就行了......那就更简单了,直接输出1,然后后面跟n-1个0就行了╮(╯_╰)╭ 下面AC代码 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm>

hdu 4802 GPA 水题

GPA Time Limit: 20 Sec  Memory Limit: 256 MB 题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=4802 Description In college, a student may take several courses. for each course i, he earns a certain credit (ci), and a mark ranging from A to F, which is c

hdu 1015 Safecracker 水题一枚

题目链接:HDU - 1015 === Op tech briefing, 2002/11/02 06:42 CST === "The item is locked in a Klein safe behind a painting in the second-floor library. Klein safes are extremely rare; most of them, along with Klein and his factory, were destroyed in World

HDU 5211 Mutiple 水题

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5211 题解: 1.筛法: 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #include<vector> 6 using namespace std; 7 8 const int maxn=10000+10; 9 const i

hdu 5326 Work 水题

Work Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 225    Accepted Submission(s): 166 Problem Description It’s an interesting experience to move from ICPC to work, end my college life and star

hdu 4493 Tutor 水题

Tutor Time Limit: 20 Sec  Memory Limit: 256 MB 题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=4493 Description Lilin was a student of Tonghua Normal University. She is studying at University of Chicago now. Besides studying, she worked as a tutor tea

HDU 5003 Osu! 水题 2014 ACM/ICPC Asia Regional Anshan Online

水.. #include <iostream> #include <cstdio> #include <string.h> #include <queue> #include <vector> #include <algorithm> #include <set> using namespace std; #define N 100 double a[N]; bool cmp(double x, double y){ re