BestCoder Round#58 LCS、すなわちhdu 5495(シミュレーション)

LCS
Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 505    Accepted Submission(s): 274
Problem Description
You are given two sequence 
{a1,a2,...,an} and 
{b1,b2,...,bn}. Both sequences are permutation of 
{1,2,...,n}. You are going to find another permutation 
{p1,p2,...,pn} such that the length of LCS (longest common subsequence) of 
{ap1,ap2,...,apn} and 
{bp1,bp2,...,bpn} is maximum.
 
Input
There are multiple test cases. The first line of input contains an integer 
T, indicating the number of test cases. For each test case:
The first line contains an integer 
n(1≤n≤105) - the length of the permutation. The second line contains 
n integers 
a1,a2,...,an. The third line contains 
nintegers 
b1,b2,...,bn.
The sum of 
n in the test cases will not exceed 
2×106.
 
Output
For each test case, output the maximum length of LCS.
 
Sample Input

 
   

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

解析：1.子序列的含义。这里的子序列与我们以前所认知的略有不同，是数学意义上的子序列。

    ，                                   (     )       。   \{1,3,2\}{1,3,2}  \{1, 4, 3, 5, 2, 1\}{1,4,3,5,2,1}      .

           2.リングを求める.BCの問題解には求環があり、それから長さを加算し、より詳細な解釈はなくなりました.ここで詳しく説明します.
              各a[i]について、b[i]には2つのケースがある.
               ①b[i]==a[i]
                   この場合( 何が言いたいと思ってるの?特例として覚えておけばいいのに)   
               ②b[i]!=a[i]
                   この場合,a[i]が長男シーケンスに関与すると,転位になるしかない.たとえば、次のようなデータのセットがあります.
                   1 3 2 4
                   3 2 4 1
                   一人間違えて、こうなりました.
                    1 3 2 4
                       3 2 4 1
                   長男シーケンスは、3 2 4です.
                   これはどのように処理しますか?
                   a1-->b3-->a3-->b2-->a2-->b4-->a4-->b1-->a1
                   すなわち,数字1からA数列とB数列の1対1の対応関係により,最終的には必ず1に戻るループである.このリングでは,Aの長さ=Bの長さ=4,サブシーケンスの長さは3であり,L>1の場合,ans+=L−1がある理由である.
           3.公式に与えられた問題解は、すべてのループLを見つけ、L==1(すなわちa[i]==b[i])、ans+=1である.L>1の場合、ans+=L-1となります.
              しかし、実際には、2つの数列はいずれも1からnまでのn個の数であるため、2つの数列は必然的にリングから構成される.したがって,L>1のリングの数J,ans=n−Jのみが要求される. 
コード:

#include
#include
#include
using namespace std;

const int maxn=1e5;
int a[maxn +10],b[maxn+10];
bool v[maxn+10];

int getin()
{
  int ans=0;char tmp;
  while(!isdigit(tmp=getchar()));
  do ans=(ans<<3)+(ans<<1)+tmp-'0';
  while(isdigit(tmp=getchar()));
  return ans;
}

int main()
{
  freopen("1.in","r",stdin);
  int t,n,ans,i,j,k;
  for(t=getin();t>0;t--)
    {
      ans=n=getin();
      for(i=1;i<=n;i++)a[i]=getin();
      for(i=1;i<=n;i++)b[a[i]]=getin();
      
      memset(v,0,sizeof(v));
      for(i=1;i<=n;i++)if(!v[i] && b[i]!=i)
        for(--ans,k=i;!v[k];k=b[k])v[k]=1;
	  printf("%d
",ans);
	}
  return 0;
}