2017-Sp264-team2

从 Trac 迁移的文章

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

原文章内容如下：

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

== 流水账 ==
做完前期题后，cjb辛苦做C，封榜后过了，sub和yzc努力爆I，没能像高中生一样爆出来。
=== chenjb ===
我这个C，写的太久太久了...hash错了之后又怀疑起了自己对border的理解，要牢记周期=border。爆I爆不出来好像是我们队的必然啊？非常不懂暴搜剪枝那一套啊？
=== oipotato ===

=== subconscious  ===

== 题解 == 
 * A：背包求出去掉某个人之后取j个人和为k的方案数，算出概率。

 * B：每一位暴力。

 * C：周期=border，每个长度为i的border会在全串长度到i的时候出现，然后持续一段时间后再也不存在，于是抠出区间，二分用哈希判定(l+k,r)和(l,r-k)求出右边界即可。

 * D：CRT

 * E：模拟

 * F：预处理出横竖的答案，枚举竖着的，每个少掉的点只会对三个横着的位置产生影响，用set维护答案。

 * G：要么平行要么垂直，暴力枚举。

 * H：按图判定。

 * I：暴搜+牛逼剪枝可过验题赛数据，正解：随机化。把长度为10的环拆成两个长度为5的。为了防止统计重复，把每个点随机黑白染色，要求连线5个白色点和连续5个黑色点组成10元环。（这样最优解合法的概率是10 / 1024, 随机1000次正确率是1 - (1 / e)^10^）统计长度为5的最长路的方式是先枚举两个点，求出长度为3的路径的前三大，然后再枚举两端的四个点，直接统计答案。复杂度： O(T * m^2^)

 * J：显然是排序后连续地取，写出dp方程后斜率优化即可。

流水账

做完前期题后，cjb辛苦做C，封榜后过了，sub和yzc努力爆I，没能像高中生一样爆出来。

chenjb

我这个C，写的太久太久了...hash错了之后又怀疑起了自己对border的理解，要牢记周期=border。爆I爆不出来好像是我们队的必然啊？非常不懂暴搜剪枝那一套啊？

oipotato

subconscious

题解

• A：背包求出去掉某个人之后取j个人和为k的方案数，算出概率。
• B：每一位暴力。
• C：周期=border，每个长度为i的border会在全串长度到i的时候出现，然后持续一段时间后再也不存在，于是抠出区间，二分用哈希判定(l+k,r)和(l,r-k)求出右边界即可。
• D：CRT
• E：模拟
• F：预处理出横竖的答案，枚举竖着的，每个少掉的点只会对三个横着的位置产生影响，用set维护答案。
• G：要么平行要么垂直，暴力枚举。
• H：按图判定。
• I：暴搜+牛逼剪枝可过验题赛数据，正解：随机化。把长度为10的环拆成两个长度为5的。为了防止统计重复，把每个点随机黑白染色，要求连线5个白色点和连续5个黑色点组成10元环。（这样最优解合法的概率是10 / 1024, 随机1000次正确率是1 - (1 / e)¹⁰）统计长度为5的最长路的方式是先枚举两个点，求出长度为3的路径的前三大，然后再枚举两端的四个点，直接统计答案。复杂度： O(T * m²)
• J：显然是排序后连续地取，写出dp方程后斜率优化即可。

附加文件

• 1.png by chenjb