题目描述

题解

GDSOI的神仙防AK题，听了三遍仿佛是三道题

01分数规划，变成每选一位有代价，把原串当作代价为0的串丢进AC自动机里，直接在AC自动机上dp

设f[i]表示从fail[i]到i这一段开始到i结束的最大答案

但是上面会少一段，所以设g[i]表示从根到fail[i]这一段到i的最大答案

显然f[i]可以先从f[fail[i]]转移过来，然后加上g[i]就是真正的f[i]

问题变成了怎么求g[i]

我觉得这幅图已经可以把这题讲完了

首先先把g[fa[i]]加进g[i]然后跳fail，可以发现g[fail]刚好对应g[i]向下到fail[fa[i]]所减少的部分，于是一直跳一直加g即可，注意不要把g[fail[i]]加进去

可以发现由于是从fail[i]上面开始的，所以一定能够匹配fail[i]以上的串（即i点不包括从根到i的所有串），因此把从根到i的串减掉后加上去，最后再考虑上从根到i的情况

时间复杂度O(n)

code

#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define max(a,b) (a>b?a:b)
#define ll long long
#define file
using namespace std;

int tr[300002][26],fa[300002],d[300002],dp[300002],n,m,i,j,k,l,len=1,h,t,x;
char st[100001],St[200001];
ll sum[300002],Sum[300002],sum2[300002];
double f[300002],g[300002],L,R,mid;

void New(int t,int x) {if (!tr[t][x]) tr[t][x]=++len;}
void put(char *a,int w)
{
	int i,j,k,l,n=strlen(a);
	
	k=1;
	fo(i,0,n-1)
	{
		New(k,a[i]-‘a‘);
		k=tr[k][a[i]-‘a‘];
	}
	sum[k]+=w;
}

bool pd(double s)
{
	int i,j,k,l,x;
	
	memset(f,254,sizeof(f));
	memset(g,254,sizeof(f));
	
	fo(h,1,t)
	{
		fo(i,0,25)
		if (tr[d[h]][i])
		{
			x=tr[d[h]][i];f[x]=f[fa[x]];g[x]=g[d[h]];
			
			if (x==5)
			n=n;
			
			if (h==1) f[x]=max(f[x],-s+sum[x]); else f[x]=max(f[x],-s);f[x]=max(f[x],-s*dp[x]+sum2[x]);
			k=fa[d[h]];
			while (k && !tr[k][i]) {g[x]=max(g[x],g[k]);k=fa[k];}
			g[x]=max(g[x]-s+(sum[x]-Sum[x]),-s*dp[x]+sum2[x]);f[x]=max(f[x],g[x]);
		}
	}
	
	k=1;
	fo(i,0,n-1)
	{
		k=tr[k][st[i]-‘a‘];
		if (f[k]>0)
		return 1;
	}
	return 0;
}

int main()
{
	freopen("string.in","r",stdin);
	#ifdef file
	freopen("string.out","w",stdout);
	#endif
	
	scanf("%s",st);n=strlen(st);
	put(st,0);
	scanf("%d",&m);
	fo(i,1,m)
	{
		scanf("%s%d",St,&j);
		put(St,j);
	}
	
	h=0;t=1;d[1]=1;
	while (h<t)
	{
		++h;
		fo(i,0,25)
		if (tr[d[h]][i])
		{
			x=fa[d[h]];
			while (x && !tr[x][i]) x=fa[x];
			fa[tr[d[h]][i]]=(!x)?1:tr[x][i];
			Sum[tr[d[h]][i]]=sum[tr[d[h]][i]];
			sum[tr[d[h]][i]]+=sum[fa[tr[d[h]][i]]];
			
			sum2[tr[d[h]][i]]=sum2[d[h]]+sum[tr[d[h]][i]];
			dp[tr[d[h]][i]]=dp[d[h]]+1;
			d[++t]=tr[d[h]][i];
		}
	}
	
//	cout<<pd(2)<<endl;
//	return 0;
	L=0;R=20000000000ll;
	while (R-L>0.000001)
	{
		mid=(L+R)/2;
		if (pd(mid)) L=mid; else R=mid;
	}
	printf("%.4f\n",L);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}

6682. 【2020.06.04省选模拟】串在哪(string)

原文：https://www.cnblogs.com/gmh77/p/13060761.html