P5319 [BJOI2019]奥术神杖

BZOJ最后一题

这博客更新速度有点慢啊...汗TAT

有一个长度为 $n$ 的母串，其中某些位置已固定，另一些位置可以任意填。

同时给定 $m$ 个小串，第 $i$ 个为 $S_i$ ，所有位置都已固定，它的价值为 $V_i$ 。

每次每个小串在母串中出现一次，便会给答案的多重集贡献一个 $V_i$ 。

最终的答案为多重集的几何平均数，定义空集的几何平均数为 $1$ 。

请你求出一个合法母串（往可以填的位置填合法字符）使得答案最大。

$1\le n,s\le 1501$ ， $1\le V_i\le \max V=10^9$ ，其中 $s=\sum_{i=1}^{m}|S_i|$ 。

首先我们好像是要求个最大的

ans=max(\sqrt[c]{\prod_{i=1}^{c}{w_i}})

这个玩意怎么处理呢?开log就行了

ln~~ans=max(\frac{1}{c}*{\sum_{i=1}^c{\ln w_i}})

我们发现要最大化均值....

就是一个经典的0/1分数规划了,那么,注意 $w_i$ 已经去了对数

\frac{1}{c}*\sum_{i=1}^c{w_i}>mid

\sum_{i=1}^c{w_i-mid}>0

这样就比较简单了,可以在小串上建AC自动机上DP

$dp[i][u]$ 表示遍历完成了字符串前i个字符,匹配在AC自动机u节点的情况最大值

转移时考虑是否i字符确定,不确定就都更新一下

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#define ll long long
using namespace std;

int n,m;
double w[1510];
char a[1510],s[1510][1510];
int ch[1510][10],ccnt=0,num[1510],fail[1510];
double sum[1510];

inline void ins(int x,int len) {
	int i,cur=0,tmp;
	for(i=1; i<=len; ++i) {
		tmp=s[x][i]-'0';
		if(!ch[cur][tmp])ch[cur][tmp]=++ccnt;
		cur=ch[cur][tmp];
	}
	num[cur]++;//数量和s
	sum[cur]+=w[x];//sum是权值和
//	printf("%d - - %lf\n",num[cur],sum[cur]);
}
queue<int> q;
inline void build() {
	int i,u,v;
	for(i=0; i<10; ++i) {
		if(!ch[0][i])continue;
		q.push(ch[0][i]);
		fail[ch[0][i]]=0;
	}
	while(!q.empty()) {
		u=q.front();
		q.pop();
		num[u]+=num[fail[u]];
		sum[u]+=sum[fail[u]];//统计fail树和
		for(i=0; i<10; ++i) {
			v=ch[u][i];
			if(v) fail[v]=ch[fail[u]][i],q.push(v);
			else ch[u][i]=ch[fail[u]][i];//建立fail边
		}
	}
	//for(int i=0; i<=3; ++i)printf("%d-%lf\n",num[i],sum[i]);
}
double dp[1510][1510];
int from[1510][1510][2],endpos;

inline bool check(double mid) {
	register int i,j,k,son;
	for(i=0; i<=n; ++i)
		for(j=0; j<=ccnt; ++j)dp[i][j]=-2e20;
	//init
	for(i=0; i<=ccnt; ++i) {
		sum[i]-=mid*(double)num[i];//暴力处理一下
	}
	dp[0][0]=0;
	for(i=1; i<=n; ++i) {
		for(j=0; j<=ccnt; ++j) {
			if(dp[i-1][j]==-2e20)continue;
			if(a[i]!='.') {//直接转移
				son=ch[j][a[i]-'0'];
				if(dp[i][son]<dp[i-1][j]+sum[son]) {
					dp[i][son]=dp[i-1][j]+sum[son];
					from[i][son][0]=j;
					from[i][son][1]=a[i]-'0';
				}
			} else {
				for(k=0; k<10; ++k) {
					son=ch[j][k];
					if(dp[i][son]<dp[i-1][j]+sum[son]) {
						dp[i][son]=dp[i-1][j]+sum[son];//就都更新一遍呗
						from[i][son][0]=j;
						from[i][son][1]=k;//暴力记住上个节点和这个字符是什么
					}
				}
			}
		}
	}
	int pos=0;
	for(i=1; i<=ccnt; ++i)if(dp[n][i]>dp[n][pos]) pos=i;//选择个最优的状态
	for(i=0; i<=ccnt; ++i)sum[i]+=mid*(double)num[i]; //还原影响
	endpos=pos;
	//printf("%d?%lf\n",pos,dp[n][pos]);
	return dp[n][pos]>0;//返回能否大于0
}
char re[1510];
int main() {
	scanf("%d%d",&n,&m);
	register int i;
	scanf("%s",a+1);
	for(i=1; i<=m; ++i) {
		scanf("%s",s[i]+1);
		scanf("%lf",&w[i]);
		w[i]=log((double)w[i]);//强行精度误差
//		printf("%lf?\n",w[i]);
		ins(i,strlen(s[i]+1));
	}
//	printf("%d?\n",ccnt);
	build();
	double l=0,r=log(1e9+7),mid,ans=0;
	while(r-l>1e-6) {
		mid=(l+r)*0.5;
	//	printf("%lf %lf %lf\n",l,r,mid);
		if(check(mid))ans=mid,l=mid;//printf("%lfqwq\n",ans);
		else r=mid;
	}
	check(ans);
	for(i=n; i>=1; --i) {
		re[i]=from[i][endpos][1]+'0';//输出方案部分
		endpos=from[i][endpos][0];//跳fa
	}
	for(int i=1; i<=n; ++i)putchar(re[i]);
	putchar('\n');
	return 0;
}

夏晓光(loveJY)的博客

P1224 [NOI2013]向量内积