2017-Sp208-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，cjb开F，yzc开I，sub开H，yzc上机忘记return函数值，结果'''I2y23'''，sub上机'''H1y33'''，cjb上机'''F1y52'''。sub和yzc讨论C，之后yzc上机，wa了两发，换sub写A，'''A1y113'''。yzc发现了bug，'''C3y115'''。cjb上机写B，wa了两发，yzc和sub讨论之后上机写D，'''D1y171'''，'''B3y177'''。yzc上机验证G的结论，然后sub上机dp，tle后一直卡常，卡到赛后才过。
== 总结 ==
=== chenjb ===
G比较可惜，赛后才卡过去。
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：f[i][j][k]代表当前在第i层，当前层有j个节点，当前层及更深的层用了k个节点，组合数往上dp即可。

 * B：先特判0、2、5，然后以K作为模数哈希，枚举至多2K位一定会出现同余数，中间这段则为可能的解，需要另外用哈希判大小。

 * C：先把所有数字置为最小的字符，如果>=则凉了，否则逐一换成最大的字符，只要有一瞬间发生变化，则除这个位置之外大于等于号和小于号是平分的，二分确定出这个位置的字符，对于这个字符前面的可以直接二分，对于后面的置为最大值之后如果还是小于号那这个位置就是最小的字符，否则可以二分。

 * D：枚举n^k^+1的平方因子，枚举到3000即可，一定能枚举出直接不断*4即可得到答案，特判2和3。

 * E：

 * F：先判断是否合法，然后处理出所有点入度出度，S向出度>入度的点连差值/2的边，出度<入度的点向T连差值/2的边，然后所有已有的边从x连向y费用为1，跑费用流即可。

 * G：结论是答案和or的结果有关，只需要两个数就能凑出所有情况，2^8^状压数位dp，优化常数即可。

 * H：OEIS结论：Σ2^k^(k>=1,k=n%2^k^)。

 * I：差分之后维护线段树最小值。

 * J：牛逼构造@sub

 * K：牛逼博弈@cjb

流水账

出门各自看题，cjb开F，yzc开I，sub开H，yzc上机忘记return函数值，结果I2y23，sub上机H1y33，cjb上机F1y52。sub和yzc讨论C，之后yzc上机，wa了两发，换sub写A，A1y113。yzc发现了bug，C3y115。cjb上机写B，wa了两发，yzc和sub讨论之后上机写D，D1y171，B3y177。yzc上机验证G的结论，然后sub上机dp，tle后一直卡常，卡到赛后才过。

总结

chenjb

G比较可惜，赛后才卡过去。

oipotato

subconscious

题解

• A：f[i][j][k]代表当前在第i层，当前层有j个节点，当前层及更深的层用了k个节点，组合数往上dp即可。
• B：先特判0、2、5，然后以K作为模数哈希，枚举至多2K位一定会出现同余数，中间这段则为可能的解，需要另外用哈希判大小。
• C：先把所有数字置为最小的字符，如果>=则凉了，否则逐一换成最大的字符，只要有一瞬间发生变化，则除这个位置之外大于等于号和小于号是平分的，二分确定出这个位置的字符，对于这个字符前面的可以直接二分，对于后面的置为最大值之后如果还是小于号那这个位置就是最小的字符，否则可以二分。
• D：枚举n^k+1的平方因子，枚举到3000即可，一定能枚举出直接不断*4即可得到答案，特判2和3。
• E：
• F：先判断是否合法，然后处理出所有点入度出度，S向出度>入度的点连差值/2的边，出度<入度的点向T连差值/2的边，然后所有已有的边从x连向y费用为1，跑费用流即可。
• G：结论是答案和or的结果有关，只需要两个数就能凑出所有情况，2⁸状压数位dp，优化常数即可。
• H：OEIS结论：Σ2^k(k>=1,k=n%2^k)。
• I：差分之后维护线段树最小值。
• J：牛逼构造@sub
• K：牛逼博弈@cjb

附加文件

• 1.png by chenjb