【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;
}