记录编号	38976	评测结果	AAAAAAAAAA
题目名称	基因重组	最终得分	100
用户昵称	TBK	是否通过	通过
代码语言	C++	运行时间	1.479 s
提交时间	2012-07-03 12:13:37	内存使用	90.68 MiB

#include <iostream> 
#include <cmath> 
#include <cstring> 
#include <string> 
#include <cstdio> 
#include <cstdlib> 
#include <iomanip> 
#include <set> 
#include <algorithm> 
#define MAXN 0x7fffffff 
using namespace std; 
set<long long> tt;
set <int>::iterator m;
long long a[6500000][2],b,c,d,e,h=1,t,s,x,y,z;
char ch;
int main(void) 
{    
    freopen("genea.in","r",stdin); 
    freopen("genea.out","w",stdout); 
	scanf("%d",&b);
	for (c=0;c<b;c++)
	{
		cin>>ch;
		if (ch=='A') x=0;
		if (ch=='C') x=1;
		if (ch=='G') x=2;
		if (ch=='T') x=3;
		d+=(x*(long long)pow(10.0,(double)(b-c-1)));
	}
	for (c=0;c<b;c++)
	{
		cin>>ch;
		if (ch=='A') x=0;
		if (ch=='C') x=1;
		if (ch=='G') x=2;
		if (ch=='T') x=3;
		e+=(x*(long long)pow(10.0,(double)(b-c-1)));
	}
	if (b==1)
	{
		printf("0");
		exit(0);
	}
	a[t][0]=d;
	while (h!=t)
	{
		if (a[t][0]==e) 
		{
			printf("%d",a[t][1]);
			break;
		}
		z=a[t][0];
		x=z/(long long)pow(10.0,(double)(b-1));
		z%=(long long)pow(10.0,(double)(b-1));
		z*=10;
		z+=x;
		if (tt.find(z)==tt.end())
		{
			a[h][0]=z;
			a[h][1]=a[t][1]+1;
			h++;
			tt.insert(z);
		}
		if (h==5000000) h=0;
		z=a[t][0];
		x=z/(long long)pow(10.0,(double)(b-1));
		y=z/(long long)pow(10.0,(double)(b-2));
		y%=10;
		z%=(long long)pow(10.0,(double)(b-2));
		z+=y*(long long)pow(10.0,(double)(b-1));
		z+=x*(long long)pow(10.0,(double)(b-2));
		if (tt.find(z)==tt.end())
		{
			a[h][0]=z;
			a[h][1]=a[t][1]+1;
			h++;
			tt.insert(z);
		}
		if (h==5000000) h=0;
		t++;
		if (t==5000000) t=0;
	}
	fclose(stdin); 
    fclose(stdout); 
    return 0; 
}