「2018 EC-Final」J - Philosophical … Balance(SAM+纳什均衡)

「 2018-2019 ACM-ICPC, Asia East Continent Finals 」J - Philosophical … Balance

题意

给一个字符串,先手给串的每一个位置赋一个值$p_i$并保证$p_i \ge 0, \sum_{i=1}^n p_i = 1$,后手选择一个子串$j$。有式子$\sum_{k=1}^n p_k \mathrm{lcp}(s_k,s_j)$,先手想使其尽可能大,后手想使其尽可能小。先手要如何操作才能使这个值最大,求这个最大值。

题解

看了这篇题解,网友是真的牛逼(战术后仰)

将原串反向,建立后缀自动机。
对于反串的后缀树,此时后手如果选择某个子树$u$中选择串$s_j$,在$p$固定的情况下要使lcp最小,显然最优解为选择子树的根。

在后缀自动机的suffix link树中,如果当前state为np节点,则直接取当前节点的len作为答案。否则需要合并若干子树的答案,答案为一个纳什均衡的模型,即每个子节点的贡献相等。那么该点的贡献为$len[u]+x$,其中$len[u]$一定会取到,$x$为纳什均衡下可以取到的最大值,推一下子树的$x$得到$x = \frac{1}{\sum \frac{1}{f_i}}$,那么在suffix link树上dfs即可求出答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 10;

struct SuffixAutomation
{
int last, cnt;
int ch[maxn << 1][26], fa[maxn << 1], len[maxn << 1], pos[maxn << 1];
int sz[maxn << 1], a[maxn << 1], c[maxn << 1];
vector<int> g[maxn << 1];

void init()
{
for(int i = 1; i <= cnt; i ++) g[i].clear();
last = cnt = 1;
memset(ch[1], 0, sizeof ch[1]);
fa[1] = len[1] = sz[1] = 0;
}

int inline newnode(int idx)
{
++cnt;
memset(ch[cnt], 0, sizeof ch[cnt]);
fa[cnt] = len[cnt] = sz[cnt] = 0;
pos[cnt] = idx;
return cnt;
}

void ins(int c)
{
int p = last , np = newnode(pos[last] + 1);
last = np, len[np] = len[p] + 1;
for(; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
if(!p) fa[np] = 1;
else
{
int q = ch[p][c];
if(len[p] + 1 == len[q]) fa[np] = q;
else
{
int nq = newnode(pos[p] + 1);
len[nq] = len[p] + 1;
memcpy(ch[nq], ch[q], sizeof ch[q]);
fa[nq] = fa[q], fa[q] = fa[np] = nq;
for(; ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
}
}
sz[np] = 1;
}

void suffixTree() { for(int i = 2; i <= cnt; i ++) g[fa[i]].push_back(i); }

double dfs(int u, int l)
{
if(sz[u]) return l;
double res = 0;
for(auto v : g[u]) res += 1.0 / dfs(v, len[v] - len[u]);
return 1.0 / res + l;
}
}sam;

char s[maxn];

int main()
{
int _;
scanf("%d", &_);
while(_ --)
{
scanf("%s", s);
sam.init();
int n = strlen(s);
for(int i = n - 1; i >= 0; i --) sam.ins(s[i] - 'a');
sam.suffixTree();
printf("%.10f\n", sam.dfs(1, 0));
}
return 0;
}