【NOI2019五校联考2019.3.5】Second

Description

给出一个长度为n的字符串S，你需要对k1~kn赋值，满足∑ki=1，使得max(kj*lcp(s[i…n],s[j…n])最小，求出这个最小值

|S|<=10^6

Solution

比赛时一直在想怎么解方程真是菜坏了

先把后缀树弄出来，显然有祖先后代关系的两点不会同时有值

设F[x]表示x为根，内部已经分好权值和为1的最小值。

考虑从儿子怎么转移，设儿子的F值分别为f1,f2,f3…fk

那么我们就是要分配x1,x2,x3…xk，满足∑xi=1，且max(fixi)最小

显然所有的fixi都相等时这个东西取最小值

然后就直接在后缀树上Dp就好了

复杂度O(n)

Code

#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define pb(a) push_back(a)
using namespace std;

typedef double db;

const int N=1e6+5;
const db eps=1e-8;

int n,tot,lst,pos[N];
vector<int> son[N];
bool vis[N];
char s[N];

struct SAM{int pr,len,son[26];}sam[N];

int extend(int x,int p) {
	int np=++tot;sam[np].len=sam[p].len+1;
	while (p&&!sam[p].son[x]) sam[p].son[x]=np,p=sam[p].pr;
	if (!p) sam[np].pr=1;else {
		int q=sam[p].son[x];
		if (sam[q].len==sam[p].len+1) sam[np].pr=q;
		else { 
			int nq=++tot;
			sam[nq]=sam[q];
			sam[nq].len=sam[p].len+1;
			sam[q].pr=sam[np].pr=nq;
			while (p&&sam[p].son[x]==q) sam[p].son[x]=nq,p=sam[p].pr;
		}
	}
	return np;
}

db f[N];

void dfs(int x,int y) {
	if (vis[x]) {
		f[x]=sam[x].len-sam[y].len;
		return;
	}
	for(int i=0;i<son[x].size();i++) {
		int z=son[x][i];
		dfs(z,x);
		f[x]+=1.0/f[z];
	}
	f[x]=1.0/f[x]+sam[x].len-sam[y].len;
}

int main() {
	freopen("second.in","r",stdin);
	freopen("second.out","w",stdout);
	scanf("%s",s+1);n=strlen(s+1);
	bool ok=1;
	fo(i,1,n-1) if (s[i]!=s[i+1]) {ok=0;break;}
	lst=tot=1;
	fd(i,n,1) vis[pos[i]=lst=extend(s[i]-'a',lst)]=1;
	fo(i,2,tot) son[sam[i].pr].pb(i);dfs(1,0);
	printf("%.6lf\n",f[1]);
	return 0;
}