2017-Sp279-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]

== 流水账 ==
=== chenjb ===
总体比较顺利，只是字符串没过有点可惜，哨兵思想很不错，值得积累。
=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：

 * B：p型统计easy，把式子改成求和-能够被整除的部分，把所有的除数k对数组2k,3k..做贡献，然后每个数直接就是数组上的前缀和。

 * C：

 * D：处理读入后最小割树。

 * E：枚举与最大值前k位相同，k+1位不同，O(1)计算最大值和答案，最小值同理，但是要注意判定填充的位置，注意常数优化。

 * F：枚举分割点后变成最长公共子序列，bitset优化。

 * G：套出球缺公式。

 * H：显然快排分成两部分依然均匀分布，然后dp即可。

 * I：

 * J：枚举2k，每k位设为关键点，显然不存在长度2k的串能覆盖3个关键点，所以对于任意相邻的两个关键点，满足条件的串左端点是单调的，二分求出最长公共前后缀即可。常数优化有判定关键点字母相同，求最长公共后缀先看目前这个最长的前缀能不能接出一个后缀。用树状数组/线段树维护答案。

 * K：暴力枚举，注意写法要达到12!/3!3!3!3!4!。

 * L：

流水账

chenjb

总体比较顺利，只是字符串没过有点可惜，哨兵思想很不错，值得积累。

oipotato

subconscious

题解

  • A：
  • B：p型统计easy，把式子改成求和-能够被整除的部分，把所有的除数k对数组2k,3k..做贡献，然后每个数直接就是数组上的前缀和。
  • C：
  • D：处理读入后最小割树。
  • E：枚举与最大值前k位相同，k+1位不同，O(1)计算最大值和答案，最小值同理，但是要注意判定填充的位置，注意常数优化。
  • F：枚举分割点后变成最长公共子序列，bitset优化。
  • G：套出球缺公式。
  • H：显然快排分成两部分依然均匀分布，然后dp即可。
  • I：
  • J：枚举2k，每k位设为关键点，显然不存在长度2k的串能覆盖3个关键点，所以对于任意相邻的两个关键点，满足条件的串左端点是单调的，二分求出最长公共前后缀即可。常数优化有判定关键点字母相同，求最长公共后缀先看目前这个最长的前缀能不能接出一个后缀。用树状数组/线段树维护答案。
  • K：暴力枚举，注意写法要达到12!/3!3!3!3!4!。
  • L：
附加文件