「 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 |
|