sfiction/selection/TopCoder

从 Trac 迁移的文章

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

原文章内容如下：

{{{
- SRM680-12, [图论], 注意到连通块数量每次至少减半，用1-2^k构造即可。O(m)。
- SRM697-12, [位运算], 易见a[i]之外的数可以根据LCP分为m组c[]，将每种情况的代价x^2展开后求和得到关于c[]的二次和式，化简后即可快速计算。O(nm)。
- SRM699-12, [数论], 注意到每个b[i]都能代表一组数，只需要b[i]和a[j]间有一个过渡值即可连边i->j。O(n^2)。
- SRM700-12, [组合], 分解成用 n 个点构成 k 棵有根树，再用 k 个有根树的顶点连成一堆环。后者的答案就是 k!，从第1个顶点开始，每个顶点都可以选择形成自环或者连到 1..i-1 其中一个前面。前半部分，首先 C(n,k) 选取 k 个顶点，然后用类似 prufer 定理的方法删掉这些顶点之外的点，得到一个长为 n-k 的序列，这个序列的最后一项是 k 个顶点之一，其他项都可以任取 1..n，因此是 C(n,k)*k*n^(n-k-1)。O(n)。
- SRM701-12, [字符串, DP], k大序列可以考虑按位枚举，统计特定前缀对应的解数量。本题的变换有很优美的性质，即解可以两两对称。因此生成方式只是考虑将i放在头或尾，倒过来考虑即可DP。O(sigma*n^3)。
- SRM702-12, [枚举], 合法串数量不多，产生出所有串后排序即可。
- SRM703-12, [搜索], 枚举y坐标最大的warship所连cannon后，剩余warship和cannon都分布在连线两侧，分解为两个子问题。状态数应该是n^2*本质不同凸包数。
}}}

- SRM680-12, [图论], 注意到连通块数量每次至少减半，用1-2^k构造即可。O(m)。
- SRM697-12, [位运算], 易见a[i]之外的数可以根据LCP分为m组c[]，将每种情况的代价x^2展开后求和得到关于c[]的二次和式，化简后即可快速计算。O(nm)。
- SRM699-12, [数论], 注意到每个b[i]都能代表一组数，只需要b[i]和a[j]间有一个过渡值即可连边i->j。O(n^2)。
- SRM700-12, [组合], 分解成用 n 个点构成 k 棵有根树，再用 k 个有根树的顶点连成一堆环。后者的答案就是 k!，从第1个顶点开始，每个顶点都可以选择形成自环或者连到 1..i-1 其中一个前面。前半部分，首先 C(n,k) 选取 k 个顶点，然后用类似 prufer 定理的方法删掉这些顶点之外的点，得到一个长为 n-k 的序列，这个序列的最后一项是 k 个顶点之一，其他项都可以任取 1..n，因此是 C(n,k)*k*n^(n-k-1)。O(n)。
- SRM701-12, [字符串, DP], k大序列可以考虑按位枚举，统计特定前缀对应的解数量。本题的变换有很优美的性质，即解可以两两对称。因此生成方式只是考虑将i放在头或尾，倒过来考虑即可DP。O(sigma*n^3)。
- SRM702-12, [枚举], 合法串数量不多，产生出所有串后排序即可。
- SRM703-12, [搜索], 枚举y坐标最大的warship所连cannon后，剩余warship和cannon都分布在连线两侧，分解为两个子问题。状态数应该是n^2*本质不同凸包数。