sfiction/Topcoder

从 Trac 迁移的文章

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

原文章内容如下：

== list ==

 1. 2016.10.13 SRM 700: 300, 500
 2. 2016.10.15 SRM 699: 250, 500
 3. 2016.10.18 SRM 697: 300, 500
 4. 2016.10.25 SRM 680: 250, 450
 5. 2016.10.26 SRM 701: 300, 600

== solution ==

{{{
#!html
<ul>
<li>SRM680-11, [贪心], 统计每个段中最多最少能取的偶数数量，求和检查n/2是否可行。O(qlogq)。</li>
<li>SRM680-12, [图论], 注意到连通块数量每次至少减半，用1-2^k构造即可。O(m)。</li>
<li>SRM697-11, [代数], 对n个不等式求和之后推导。O(n)。</li>
<li>SRM697-12, [位运算], 易见a[i]之外的数可以根据LCP分为m组c[]，将每种情况的代价x^2展开后求和得到关于c[]的二次和式，化简后即可快速计算。O(nm)。</li>
<li>SRM699-11, [位运算, 贪心], 位独立，对于每一位，枚举异或和确定具体值，如果不合法则用未确定值进行调整。O(nlogV)。</li>
<li>SRM699-12, [数论], 注意到每个b[i]都能代表一组数，只需要b[i]和a[j]间有一个过渡值即可连边i-&gt;j。O(n^2)。</li>
<li>SRM700-11, [贪心], 对leaders排序，首先要满足与leaders[i]的大小关系，其次leaders[i+1]不能过大。O(nlogn)。</li>
<li>SRM700-12, [组合], 分解成用 n 个点构成 k 棵有根树，再用 k 个有根树的顶点连成一堆环。后者的答案就是 k!，从第1个顶点开始，每个顶点都可以选择形成自环或者连到 1..i-1 其中一个前面。前半部分，首先 C(n,k) 选取 k 个顶点，然后用类似 prufer 定理的方法删掉这些顶点之外的点，得到一个长为 n-k 的序列，这个序列的最后一项是 k 个顶点之一，其他项都可以任取 1..n，因此是 C(n,k)<em>k</em>n^(n-k-1)。O(n)。</li>
<li>SRM701-11, [博弈], 可取数量&lt;=5，若只考虑必胜/必败，则只涉及前5个阶段共10个bit，因此最多1024个状态，求循环节即可。O(2^(2*step))。</li>
<li>SRM701-12, [字符串, DP], k大序列可以考虑按位枚举，统计特定前缀对应的解数量。本题的变换有很优美的性质，即解可以两两对称。因此生成方式只是考虑将i放在头或尾，倒过来考虑即可DP。O(sigma*n^3)。</li>
</ul>
}}}

list

1. 2016.10.13 SRM 700: 300, 500

2. 2016.10.15 SRM 699: 250, 500

3. 2016.10.18 SRM 697: 300, 500

4. 2016.10.25 SRM 680: 250, 450

5. 2016.10.26 SRM 701: 300, 600

solution

  • SRM680-11, [贪心], 统计每个段中最多最少能取的偶数数量，求和检查n/2是否可行。O(qlogq)。
  • SRM680-12, [图论], 注意到连通块数量每次至少减半，用1-2^k构造即可。O(m)。
  • SRM697-11, [代数], 对n个不等式求和之后推导。O(n)。
  • SRM697-12, [位运算], 易见a[i]之外的数可以根据LCP分为m组c[]，将每种情况的代价x^2展开后求和得到关于c[]的二次和式，化简后即可快速计算。O(nm)。
  • SRM699-11, [位运算, 贪心], 位独立，对于每一位，枚举异或和确定具体值，如果不合法则用未确定值进行调整。O(nlogV)。
  • SRM699-12, [数论], 注意到每个b[i]都能代表一组数，只需要b[i]和a[j]间有一个过渡值即可连边i->j。O(n^2)。
  • SRM700-11, [贪心], 对leaders排序，首先要满足与leaders[i]的大小关系，其次leaders[i+1]不能过大。O(nlogn)。
  • SRM700-12, [组合], 分解成用 n 个点构成 k 棵有根树，再用 k 个有根树的顶点连成一堆环。后者的答案就是 k!，从第1个顶点开始，每个顶点都可以选择形成自环或者连到 1..i-1 其中一个前面。前半部分，首先 C(n,k) 选取 k 个顶点，然后用类似 prufer 定理的方法删掉这些顶点之外的点，得到一个长为 n-k 的序列，这个序列的最后一项是 k 个顶点之一，其他项都可以任取 1..n，因此是 C(n,k)kn^(n-k-1)。O(n)。
  • SRM701-11, [博弈], 可取数量<=5，若只考虑必胜/必败，则只涉及前5个阶段共10个bit，因此最多1024个状态，求循环节即可。O(2^(2*step))。
  • SRM701-12, [字符串, DP], k大序列可以考虑按位枚举，统计特定前缀对应的解数量。本题的变换有很优美的性质，即解可以两两对称。因此生成方式只是考虑将i放在头或尾，倒过来考虑即可DP。O(sigma*n^3)。