题目

描述

题目大意

给你一堆小串，每个小串都有一定的分数。

让你构造一个字符串，若子串中出现了之前的小串，就可以得到对应的分数（可以重复）

问最大分数。

思考历程

一看这题就知道是什么字符串方面的算法。

然后就很自然地想到AC自动机，多串匹配嘛！

接下来就想到建字符串的过程中，一个指针在AC自动机上跳来跳去……

先建出AC自动机，然后算出到达每个节点的贡献。

对于每个节点，枚举字母，若没有出边，就想着用failfailfail往上跳，然后将出边连向那个地方。

从此AC自动机变成了一张有向图，每个点都有262626条出边。题目就转成了在这张有向图上，走mmm步所的最大点权和。

感觉转化到这一步之后就想不出什么了，考虑过最长路一类的做法，都是没有成功。

于是我也不追求满分了，直接跑DP水分。

正解

事实上……

题目中有这么一句话：字符串的长度和不超过200200200。

知道这一切之后我疯了。

既然这样，那不就是一个裸的矩阵乘法吗？

时间就是2003lg⁡m200^3\lg m2003lgm，在6000ms中肯定是可以过的。

代码

using namespace std;

#include <cstdio>

#include <cstring>

#include <algorithm>

int n;

long long m;

int a[210];

char str[210];

struct Node{

	int c[26],fail;

	int v;

} d[210];

int cnt,root;

inline void insert(char *s,int val){

	int t=root;

	for (;*s;++s){

		if (!d[t].c[*s-'a'])

			d[t].c[*s-'a']=++cnt;

		t=d[t].c[*s-'a'];

	}

	d[t].v+=val;

}

inline void build(){//求fail，顺便做了对空儿子的处理。显然这两步是可以放在一起的

	static int q[210];

	int head=0,tail=1;

	d[root].fail=root;

	q[1]=root;

	do{

		int t=q[++head];

		for (int i=0;i<26;++i){

			if (d[t].c[i])

				q[++tail]=d[t].c[i];

			if (t==root){

				if (d[t].c[i])

					d[d[t].c[i]].fail=root;

				else

					d[t].c[i]=root;

				continue;

			}

			int nxt=d[t].fail;

			while (nxt!=root && !d[nxt].c[i])

				nxt=d[nxt].fail;

			if (d[nxt].c[i]){

				if (d[t].c[i]){

					d[d[t].c[i]].fail=d[nxt].c[i];

					d[d[t].c[i]].v+=d[d[nxt].c[i]].v;

				}

				else

					d[t].c[i]=d[nxt].c[i];

			}

			else{

				if (d[t].c[i])

					d[d[t].c[i]].fail=root;

				else

					d[t].c[i]=root;

			}

		}

	}

	while (head!=tail);

}

struct Matrix{

	long long mat[210][210];

	inline void operator*=(Matrix &b){

		static Matrix res;

		memset(res.mat,200,sizeof res);

		for (int i=1;i<=cnt;++i)

			for (int j=1;j<=cnt;++j)

				for (int k=1;k<=cnt;++k)

					res.mat[i][j]=max(res.mat[i][j],mat[i][k]+b.mat[k][j]);

		memcpy(mat,res.mat,sizeof mat);

	}

} f;

inline void get_pow(Matrix &x,long long m){

	static Matrix res;

	memset(res.mat,200,sizeof res);

	for (int i=1;i<=cnt;++i)

		res.mat[i][i]=0;

	for (;m;m>>=1,x*=x)

		if (m&1)

			res*=x;

	memcpy(x.mat,res.mat,sizeof x);

}

int main(){

	cnt=root=1;

	scanf("%d%lld",&n,&m);

	for (int i=1;i<=n;++i)

		scanf("%d",&a[i]);

	for (int i=1;i<=n;++i){

		scanf("%s",str);

		insert(str,a[i]);

	}

	build();

	memset(f.mat,200,sizeof f);

	for (int i=1;i<=cnt;++i)

		for (int j=0;j<26;++j)

			f.mat[i][d[i].c[j]]=d[d[i].c[j]].v;

	get_pow(f,m);

	long long ans=0;

	for (int i=1;i<=cnt;++i)

		ans=max(ans,f.mat[1][i]);

	printf("%lld\n",ans);

	return 0;

}

总结

不想说什么……

如果不是没有看到，我这题早就AC的……

巴特西

[JZOJ4649] 【NOIP2016提高A组模拟7.17】项链

题目

描述

题目大意

思考历程

正解

代码

总结

最新文章

热门文章