i.cpp

ACM World Final 2008题目程序代码

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int n,m;
long long w[30][1<<10][110];
char s[30];

struct node
{
	int c[26],m;
};

struct qnode
{
	int no,p;
	qnode& operator()(int no_,int p_)
	{
		return no=no_,p=p_,*this;
	}
};

struct trie
{
	node nd[2000];
	int ns;
	void init()
	{
		memset(nd,0,sizeof(nd));
		for(int i=0;i<26;++i)nd[0].c[i]=1;
		ns=1;
	}
	void ins(char* s,int m=1)
	{
		int no=1;
		for(;*s;++s)
		{
			int &nno=nd[no].c[*s-'a'];
			if(!nno)nno=++ns;
			no=nno;
		}
		nd[no].m|=m;
	}
	qnode q[110];
	int qsize;
	void adde(int no,int p)
	{
		nd[no].m|=nd[p].m;
		for(int i=0;i<26;++i)
			if(nd[no].c[i])q[++qsize](nd[no].c[i],nd[p].c[i]);
			else nd[no].c[i]=nd[p].c[i];
	}
	void adde()
	{
		q[qsize=1](1,0);
		for(int i=1;i<=qsize;++i)adde(q[i].no,q[i].p);
	}
	void print(int no=1,int c=0)
	{
		if(!no)return;
		if(nd[no].m)cout.write(s,c)<<endl;
		for(int i=0;i<26;++i)
		{
			s[c]='a'+i;
			print(nd[no].c[i],c+1);
		}
	}
} tr,pt;

void calcw(int c,int ma,int no)
{
	int mc=tr.nd[no].m;
	if(mc&~ma)return;
	int mac=ma-mc;
	long long &ans=w[c][ma][no];
	for(int i=mc;i>=0;--i)
	{
		i&=mc;
		for(int j=0;j<26;++j)
			ans+=w[c+1][mac|i][tr.nd[no].c[j]];
	}
}

void print(int c,int ma,int no)
{
	if(!w[c][ma][no])return;
	if(c==n)
	{
		s[c]=0,pt.ins(s);
		return;
	}
	int mc=tr.nd[no].m;
	if(mc&~ma)return;
	int mac=ma-mc;
	for(int i=mc;i>=0;--i)
	{
		i&=mc;
		for(int j=0;j<26;++j)
		{
			s[c]='a'+j;
			print(c+1,mac|i,tr.nd[no].c[j]);
		}
	}
}

int main()
{
	for(int te=1;scanf("%d %d\n",&n,&m),n;++te)
	{
		tr.init();
		for(int i=0;i<m;++i)
		{
			gets(s);
			tr.ins(s,1<<i);
		}
		tr.adde();
		memset(w,0,sizeof(w));
		for(int i=1;i<=tr.ns;++i)
			w[n][tr.nd[i].m][i]=1;
		for(int i=n-1;i>=0;--i)
			for(int j=0;j<1<<m;++j)
				for(int k=1;k<=tr.ns;++k)
					calcw(i,j,k);
		long long ans=w[0][(1<<m)-1][1];
		cout<<"Case "<<te<<": "<<ans<<" suspects"<<endl;
		if(ans<=42)
		{
			pt.init();
			print(0,(1<<m)-1,1);
			pt.print();
		}
	}
	return 0;
}