hdoj2296(待完成)

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<string>
using namespace std;
#define maxn 120
#define CH 27
int chd[maxn][CH];
int fail[maxn],val[maxn];
int sz;
char id[27];
void init(){
    memset(chd[0],0,sizeof(chd[0]));
    sz=1;
    val[0]=0;
}
void insert(char s[],int type,int v[]){
    int i=0,p=0;
	int len=strlen(s);
    for(i=0;i<=len-1;i++)
	{
        int x=s[i]-'a'+1;
        if(!chd[p][x]){
            memset(chd[sz],0,sizeof(chd[sz]));
            val[sz]=0;
            chd[p][x]=sz++;
        }
        p=chd[p][x];
    }
    val[p]=v[type];
}
void build_fail(){
    queue<int> que;
    for(int i=1;i<=CH-1;i++)
		if(chd[0][i])
		{
			fail[chd[0][i]]=0;
			que.push(chd[0][i]);
		}
    while(!que.empty())
	{
        int p=que.front();
        que.pop();
        for(int i=1;i<=CH-1;i++)
		{
            if(chd[p][i])
			{
                int v=chd[p][i];
                que.push(v);
                fail[v]=chd[fail[p]][i];
                val[v]=val[v]+val[fail[v]];//对word[v]按word[fail[v]]里的内容进行处理
            }
			else
			{
                chd[p][i]=chd[fail[p]][i];
            }
        }
    }
}

int dp[110][60];
string ss[110][60];
int main()
{
	int t;
	int i,j;
	for(i=1;i<=26;i++)
		id[i]='a'+i-1;
	scanf("%d",&t);
	while(t--)
	{
		int n,m;
		init();
		scanf("%d %d",&n,&m);
		getchar();
		char s[110][15];
		for(i=1;i<=m;i++)
		{
			gets(s[i]);
		}
		build_fail();
		int v[110];
		for(i=1;i<=m;i++)
			scanf("%d",&v[i]);
		for(i=1;i<=m;i++)
		{
			insert(s[i],i,v);
		}
		memset(dp,0,sizeof(dp));
		for(i=0;i<=sz-1;i++)
			ss[i][0]="";
		for(j=0;j<=n;j++)
		{
			for(i=0;i<=sz-1;i++)
			{
				for(int k=1;k<=26;k++)
					if(dp[i][j]+val[chd[i][k]]>dp[chd[i][k]][j+1])
					{
						dp[chd[i][k]][j+1]=dp[i][j]+val[chd[i][k]];
						ss[chd[i][k]][j+1]=ss[i][j]+id[k];

					}
					else if(dp[i][j]+val[chd[i][k]]==dp[chd[i][k]][j+1])
					{
						if((ss[i][j]+id[k])<ss[chd[i][k]][j+1])
							ss[chd[i][k]][j+1]=ss[i][j]+id[k];
						
					}
			}
		}
		int weight[110];
		memset(weight,0,sizeof(weight));
		for(j=0;j<=n;j++)
			for(i=0;i<=sz-1;i++)
			{
				if(dp[i][j]>weight[j])
				{
					weight[j]=dp[i][j];
				}
			}
		for(j=n;j>=1;j--)
			if(weight[j]>weight[j-1])
				break;
		int ans=j;
		string result=ss[0][ans];
		for(i=1;i<=sz-1;i++)
			if(ss[i][ans]<result)
				result=ss[i][ans];
		printf("%s\n",result.c_str());
	
	}


system("pause");
return 0;
}

hdoj4162——最小表示法

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char s[300000+10],ans[300000+10];
int max(int a,int b)
{
	return a>b?a:b;
}
int min(int a,int b)
{
	return a<b?a:b;
}
int minstr(char s[])
{
	int i=0,j=1;
	int len=strlen(s);
	while(i<=len-1 && j<=len-1)
	{
		int k=0;
		while(k<=len-1 && s[(i+k)%len]==s[(j+k)%len])
			k++;
		if(k>=len)
			break;
		if(s[(i+k)%len]>s[(j+k)%len])
			i=max(i+k+1,j+1);
		else
			j=max(j+k+1,i+1);
	}
	return min(i,j);
}
int main()
{
	int i;
	while(scanf("%s",s)!=EOF)
	{
		getchar();
		char tmp=s[0];
		int len=strlen(s);
		s[len]=tmp;
		s[len+1]='\0';
		for(i=0;i<=len-1;i++)
		{
			if(s[i+1]>=s[i])
				s[i]='0'+s[i+1]-s[i];
			else
				s[i]='0'+s[i+1]+8-s[i];
		}
		s[len]='\0';
		int pos=minstr(s);
		for(i=pos;i<=pos+len-1;i++)
			ans[i-pos]=s[i%len];
		ans[len]='\0';
		printf("%s\n",ans);

	}

system("pause");
return 0;
}

hdoj2825

无限TLE。。实在改不动了。。就这样吧。
trie图+状压DP。总共10个单词不到,每个单词是否包含用0、1表示,这样状态总共不超2^10-1.dp[i][j][t]表示在trie图上走i步,处于j结点,且状态为t(压缩后的二进制串的十进制表示)时的字符串数目。状态转移见代码,有点像lrj白书上说的刷表法。

hdoj2243

TLE代码一段,写的肉流满面,居然TLE。。
这里借鉴了poj3233的思路,二分计算A+A^2+A^3+…………+A^k。据说计算A+A^2+A^3+…………+A^k.(其中A是一个矩阵,k很大)有第二种简单且更快的方法,矩阵扩大成4倍。。明天再说。。

zoj2778——trie图+矩阵快速幂

好题,trie图建好后,写出它的邻接矩阵形式,m[i][j]表示从结点i经过一步到达j的方法数(边数).注意,不能经过危险结点(何为危险结点?请参考wc的论文《trie树的改进与活用》),所以到达从点i到达危险结点的方法数设为0.这样最后结果才表示走n步(相当于写了n个字母)后没有包含单词结点的字符串数量。
注意:这里补全了结点的所有’A'——’Z'的孩子,但实际只可能转向’A'、’C'、’G'、T’,所以其他虚拟孩子不用考虑。

trie图模板

关于虚拟结点:这个知识点纠结了一个星期多,现在总算基本ok了。
对于root的不存在的孩子结点,补边,把它指向root。对于其他结点u的不存在的孩子结点c,补上边,指向fail[u]的c孩子,因为两者等效,如果fail[u]没有c孩子会怎样,没有问题,由于求解fail和补边时是bfs,所以补ch[u]..时,ch[fail][u]即使不存在,也一定补好边了。
为什么代码中对于root的孩子没有补边的代码?
因为root结点的编号是0,而ch[0][i]被初始化为0,也就是说已经指向root结点了(已经不好了)。
补边完成后:
1.trie的最下面一层叶子结点时虚拟的,不存在的,因为真实存在的结点都会补齐虚拟孩子结点。
2.对于非叶结点,每个结点的孩子都是补全的。
关于ac自动机和trie图的比较:
理解了之后感觉两者关系非常清楚:ac自动机其实是不确定性有限状态自动机,因为当结点失配要用fail回溯时可能要回溯多次。而trie图是确定性有限状态自动机,他相当于把ac自动机的可能的多次回溯变成一次,一次到达下一个状态。
为什么chd[p][i]=chd[fail[p]][i];这句一次就使得失配后(指的是p点匹配,而i点不匹配,即p没有i孩子,即ch[p][i]不存在),ch[p][i]指向了该去的结点?
答:因为计算ch[p][i]时,ch[fail[p]][i]已经计算完成,也就是ch[fail[p]][i]一定已经指向了(即被赋值为该去的结点后者其本身就存在)存在的结点。
举例来说:假设p没有c孩子,fail[p]没有c孩子,fail[fail[p]]没有c孩子,fail[fail[fail[p]]]有c孩子,那么计算ch[fail[fail[p]]]时,它被赋值为ch[fail[fail[fail[p]]]],计算ch[fail[p]]时,它被赋值为ch[fail[fail[p]]],计算ch[p]时,它被赋值为ch[fail[p]]。(上述计算过程显然是依照这个顺序进行的,因为是bfs的)可见,最终ch[p]被实际赋值为ch[fail[fail[fail[p]]]],这个ch[fail[fail[fail[p]]]]..是真实存在的结点。问题解决了。上述过程的本质就是把ac自动机的多次回溯变成了一次(有效的利用了bfs过程,这种赋值很像DP思想(确切的说是递推))
语言表达不太好,看代码把^_^
对了,还有一点:只有真实存在的点才需要fail指针,以为无论在trie图中转移到哪个点,其实每个时刻都是在一个真实存在的结点上。一个虚拟结点是不可能匹配成功的(因为根本走不到那,转移到那其实是走到了一个真实存在的结点)
匹配主串的时候,每到一个点v都要检查v、fail[v]、fail[fail[v]]……直到root,是否是单词点,道理和ac自动机相同。(一个字符串可能不是单词,但它的后缀,它的后缀的后缀……可能是单词)