福建省队集训 20180713

Yist

有一个 n 个点 m 条边的无向图，结点从 1 到 n 标号，点 u 的初始权值为 (w_u)。你可以对任意结点 u 进行操作，将你的得分（初始为 0）加上 (∑ _{(u,v)∈E} w_v)，并将 (w_u) 除以 2。

给定一个长度为 k 的结点序列 (s1, s2, . . . , sk(1 ≤ si ≤ n))，在一轮操作中，你需要依次对 (s_1, s_2, . . . , s_k) 进行操作。你想知道，在进行了无限轮操作后，你得分的极限是多少。

答案的式子不难推，等比数列求和即可。

怎么统计答案呢？注意到答案的式子只和v有关而且随着k变化而变化，我们考虑模拟+根号分治（是叫这个吗？），讨论一个点的相邻的点的度数，(d_vleq sqrt n)则把 (v) 的答案加到 (ans_u)上，否则在询问时单独访问(v)统计。修改的时候暴力修改小点周围的ans，否则不改。这样总复杂度是(nsqrt n)的，感觉这个小点记大点求的套路挺常见的。

注意int和ll，wa了好几发，考试的时候一定要对拍T_T

Ernd

给定一个长度为 n 且仅包含小写英文字母的字符串 S。你有一个字符串 T，初始为空串。

你可以进行 n 次操作，每次操作你可以在 T 的前端或末尾加入一个任意字母。记第 i 次操作后 T 在 S 中的出现次数为 fi，你需要最大化 ans = ∑ i fi。

50~70可能就区间dp+SAM找一找出现次数，然后随机的话超过一定长度就不用找了，出现次数看成1即可。出错的概率是(frac n {26^l})（应该不准确，不过差不多），l设成20多应该就行吧

感觉对SAM还是掌握不够熟练...本来是道简单题

在后面添加字符相当于走转移边，在前面添加相当于走到某个儿子或者保持不动，不过只能保持(len-fa.len)次，直接把dag和parent树合并，dp即可（简单吧

Sanrd

直接主席树