记录编号	53293	评测结果	AAAAAAA
题目名称	[HAOI 2005]破译密文	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2013-02-25 11:25:57	内存使用	0.41 MiB

#include <fstream>
using namespace std;
ifstream fi("encrypt.in");
ofstream fo("encrypt.out");
string s1,s2,st1,st2,sst1,sst2;
int n,chang[1000],num[1000]={0},fu[10001],ceng[10001],sum;
bool sh[10001];
void csh()
{
	int i,j;
	char p;
	bool f=false,ff=false;
	fi>>s1>>s2;
	fi>>n;
	for (i=1;i<=n;i++)
	{
		f=false;ff=f;
		fi>>p;fi>>chang[p-96];
		for (j=0;j<s1.length();j++)
			if (s1[j]==p) {f=true;break;}
		for (j=0;j<s2.length();j++)
			if (s2[j]==p) {ff=true;break;}
		if (f==false&&ff==false) chang[p-96]=0;
	}
	num[1]=1;
	for (i=2;i<=n;i++) num[i]=num[i-1]+chang[i-1];
	sum=num[n]+chang[n]-1;
	for (i=1;i<=sum+2;i++) {fu[i]=i;ceng[i]=0;sh[i]=true;}
}
void zl()
{
	int t,i,j;
	for (i=0;i<s1.length();i++)
		if (s1[i]!='1'&&s1[i]!='0')
		{
			t=0;
			for (j=i;j<=i+chang[s1[i]-96]-1;j++)
			{
				st1+=s1[i];t++;sst1+=char(t+48);
			}
		}else {st1+=s1[i];sst1+=s1[i];}
	for (i=0;i<s2.length();i++)
		if (s2[i]!='1'&&s2[i]!='0')
		{
			t=0;
			for (j=i;j<=i+chang[s2[i]-96]-1;j++)
			{
				st2+=s2[i];t++;sst2+=char(t+48);
			}
		}else {st2+=s2[i];sst2+=s2[i];}
}
void init()
{
	csh();
	zl();
}
int zx(int x)
{
	if (fu[x]!=x) fu[x]=zx(fu[x]);
	return fu[x];
}
void hebing(int x,int y)
{
	if (x!=y)
	{
		if (ceng[x]>ceng[y]) {fu[y]=x;sh[y]=false;}else
		{
			fu[x]=y;sh[x]=false;
			if (ceng[x]==ceng[y]) {ceng[y]++;ceng[x]=0;}
		}
	}
}
int number(char x,char y)
{
	if (x=='0') return sum+1;
	if (x=='1') return sum+2;
	return num[int(x)-96]+int(y)-49;
}
int main()
{
	int i,a,b,s=0,ans=2,x,y;
	init();
	for (i=0;i<st1.length();i++)
	{
		if (st1[i]=='1'&&st2[i]=='0'||st1[i]=='0'&&st2[i]=='1') {fo<<0<<endl;return 0;}
		if ('a'<=st1[i]&&st1[i]<='z'||'a'<=st2[i]&&st2[i]<='z')
		{
			a=number(st1[i],sst1[i]);
			b=number(st2[i],sst2[i]);
			x=zx(a);
			y=zx(b);
			hebing(x,y);
		}
		if (zx(sum+1)==zx(sum+2)) {fo<<0<<endl;return 0;}
	}
	for (i=1;i<=sum+2;i++)
		if (sh[i]) s++;s-=2;
	if (s==0) ans=1;
	for (i=1;i<s;i++) ans*=2;
	fo<<ans<<endl;
	return 0;
}