2017-Sp335-team2

从 Trac 迁移的文章

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

原文章内容如下：

== 流水账 ==
=== chenjb ===
=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：枚举第一块在对应面上的对应位置，在方块上爬，判重。

 * B：cjb

 * C：对于当前位置，如果出现次数比较多，下降到出现次数等于当前值的位置，否则下降到当前值等于出现次数的位置。

 * D：黑白染色，分开连两条链；然后在前两行错位一下，连起来。注意1*1有解，1*n和n*1和2*2都无解。

 * E：枚举长度，按照长度分成好几块，相邻完全一样的块一起处理，每一段前后各找到最远的和自己相等的位置，然后在里面取长度为kx的子串的方案数，直接求。注意特判k=1。

 * F：换根dp。

 * G：x大的时候，暴力跳，用O(1)-O(sqrt(N))维护（每sqrt次重构前缀和，块内暴力）。x小的时候，每个x分别做，用O(sqrt(N))-O(1)维护（分块）。

 * H：随机k染色，然后用状压dp求出经历不同颜色的最长链，做k^k^/k!的错误概率是1/e，乘个常数，做个300左右。

 * I：欧拉定理判定。

 * J：按题意模拟。

 * K：若有a+b>Σa且>Σb，答案是sum-a-b，否则是min(a,b)。

流水账

chenjb

oipotato

subconscious

题解

• A：枚举第一块在对应面上的对应位置，在方块上爬，判重。
• B：cjb
• C：对于当前位置，如果出现次数比较多，下降到出现次数等于当前值的位置，否则下降到当前值等于出现次数的位置。
• D：黑白染色，分开连两条链；然后在前两行错位一下，连起来。注意1*1有解，1*n和n*1和2*2都无解。
• E：枚举长度，按照长度分成好几块，相邻完全一样的块一起处理，每一段前后各找到最远的和自己相等的位置，然后在里面取长度为kx的子串的方案数，直接求。注意特判k=1。
• F：换根dp。
• G：x大的时候，暴力跳，用O(1)-O(sqrt(N))维护（每sqrt次重构前缀和，块内暴力）。x小的时候，每个x分别做，用O(sqrt(N))-O(1)维护（分块）。
• H：随机k染色，然后用状压dp求出经历不同颜色的最长链，做k^k/k!的错误概率是1/e，乘个常数，做个300左右。
• I：欧拉定理判定。
• J：按题意模拟。
• K：若有a+b>Σa且>Σb，答案是sum-a-b，否则是min(a,b)。