2019-team2/Sp091

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

 题解:
 A. bitset,从大到小统计每个k的答案,维护大于等于k所有数以及其倍数形成的bitset. 复杂度O(nlogn+n^2^/64).
 B. AC自动机+DP,状态是第i位/已经被包含字符串的集合/Trie结点,最后检查每个状态是否存在对应后缀使得能跨过中间形成子串.
 C. 不懂
 D. 不懂
 E. 不懂
 F. 当不连通时,应该使得m+1个点形成菊花图.如果连通,先用n-1条边形成菊花图,然后每条多余的边都能使得一个点对从2变成1.
 G. 树DP,状态是结点/是否选取该结点/最大匹配数模m,转移看起来是m^2^的,但是可以用启发式和并通过.
 H. 每次找到最小值然后求出去掉最小值后的B集合.
 I. 每个数至多存在一个d满足性质,二分找到最小d^d^>=n的d,然后算出小于这个数的长度为d的排列.Java BigInteger可以过.
 J. 不懂
 K. 从小到大排序,满足相邻不超过K的后缀都能赢.

题解:

A. bitset,从大到小统计每个k的答案,维护大于等于k所有数以及其倍数形成的bitset. 复杂度O(nlogn+n²/64).

B. AC自动机+DP,状态是第i位/已经被包含字符串的集合/Trie结点,最后检查每个状态是否存在对应后缀使得能跨过中间形成子串.

C. 不懂

D. 不懂

E. 不懂

F. 当不连通时,应该使得m+1个点形成菊花图.如果连通,先用n-1条边形成菊花图,然后每条多余的边都能使得一个点对从2变成1.

G. 树DP,状态是结点/是否选取该结点/最大匹配数模m,转移看起来是m²的,但是可以用启发式和并通过.

H. 每次找到最小值然后求出去掉最小值后的B集合.

I. 每个数至多存在一个d满足性质,二分找到最小d^d>=n的d,然后算出小于这个数的长度为d的排列.Java BigInteger可以过.

J. 不懂

K. 从小到大排序,满足相邻不超过K的后缀都能赢.