Gene mutation

Gene mutation is the sudden and inheritable mutation of genomic DNA molecules. From the molecular level, gene mutation refers to the change of the composition or sequence of base pairs in the structure of a gene. Although the gene is very stable, it can reproduce itself accurately when the cell divides. Under certain conditions, the gene can also suddenly change from its original existence to another new form of existence.   

A genome sequence might provide answers to major questions about the biology and evolutionary history of an organism.  A 2010 study found  a gene sequence in the skin of cuttlefish  similar to those in the eye’s retina. If the gene matches, it can be used to treat certain diseases of the eye.  

A gene sequence in the skin of cuttlefish  is specified by a sequence of distinct integers (Y1,Y2, …Yc). it  may be mutated. Even if these integers are transposed  ( increased or decreased by a common amount ) ,  or re-ordered ,  it is still a gene sequence of cuttlefish.  For example,  if  "4 6 7"  is a gene sequence of cuttlefish, then "3 5 6" (-1), "6 8 9" ( +2),  "6 4 7" (re-ordered), and "5 3 6" (transposed and re-ordered) are also ruminant a gene sequence of cuttlefish.   
Your task is to determine that there are several matching points at most  in a gene sequence of the eye’s retina (X1,X2, …, Xn)

输入

The first line of the input contains one integer T, which is the number of  test cases (1<=T<=5).  Each test case specifies:

* Line 1:       n                   ( 1 ≤ n ≤ 20,000 )

* Line 2:       X1  X2… Xn        ( 1 ≤ Xi ≤ 100    i=1…. n)

* Line 3:       c                   ( 1 ≤ c≤ 10 )

* Line 4:        Y1  Y2… Yc        ( 1 ≤ Yi ≤ 100    i=1…. c)

输出

For each test case generate a single line:  a single integer that there are several matching points. The matching gene sequence can be partially overlapped

样例输入 Copy

1
6
1 8 5 7 9 10
3
4 6 7

样例输出 Copy

2

解题思路：

这道题意思是这样的。给出一个无序的数组a，在给出一个无序的数组b。b中的元素通过位置调换和所有元素同时+或-一个数，能否和a中的一个子序列相等。答案输出b能匹配多少个a中的子序列。

找出所有子序列一个个比就行了。也算是签到题。把b和a的子序列排序，如果相邻元素的间隔都一样大，就说明可以匹配。

AC代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=20005;
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		cin>>n;
		int a[N],bb[N];
		int m;
		
		for(int i=0;i<n;i++) cin>>a[i];
		cin>>m;
		for(int i=0;i<m;i++) cin>>bb[i];
		sort(bb,bb+m);
		int b[N];
		for(int i=0;i<m-1;i++)
		{
			b[i]=bb[i+1]-bb[i];
		}		
//		cout<<"b=";
//		for(int i=0;i<m-1;i++) cout<<b[i]; 
//		cout<<endl;
		
		int ans=0;
		for(int i=0;i<n-m+1;i++)
		{
			int tt[N];
			int ttt=0;
			int t[N];
			for(int j=i;j<m+i;j++)
			{
				tt[ttt++]=a[j];
			}
			sort(tt,tt+ttt);		
			for(int i=0;i<ttt-1;i++)
			{
				t[i]=tt[i+1]-tt[i];
			}
//			cout<<"t=";
//			for(int i=0;i<ttt-1;i++) cout<<t[i]; 
//			cout<<endl;
			int sum=0;
			for(int j=0;j<ttt-1;j++)
				if(t[j]==b[j])sum++;
				else break;
			if(sum==m-1) ans++;
		}
		cout<<ans<<endl;
	}	
}