2017-Sp228-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
比较迷，这个F和wf2017A一模一样，大家当年过的比谁都快，猜了一发数据弱，wa了，非常绝望。yzc上机写I，tle了。然后cjb上机写B，wa了，yzc改了改又tle了，???。cjb找到了错误，'''B2y72'''。sub让yzc去预处理，'''I3y84'''。sub和yzc开J，yzc上机'''J1y215'''。这期间cjb在很努力地写C，但是写法不太对，fix了很多次，'''C2y252'''。实在无奈，贴了个'''F1y256'''。最后cjb和sub rush H，'''H4y288'''。
== 总结 ==
=== chenjb ===
F 4分钟真的能过吗???????????  我又tm写错双向广搜了，要吸取教训，理解为两边一人走一步，碰到一起就求出解了，同一层要一起转移。
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：

 * B：等价于保留n-1-k条边，排序后从大到小尽可能贪心取，用并查集维护连通性及是否有黑点。

 * C：hash压成long long，双向广搜44步，第45步直接输出。

 * D：

 * E：

 * F：同wf2017 A。

 * G：

 * H：考察最终答案的单调性，上下移动某个点，最后一定可以移到只有一些人在地面上，某些人在同一高度的平面，转化成分数规划问题，二分答案跑网络流，S向i连b[i]，然后两两连c[i][j]，i向T连k的边，最大流值和n*k比较。

 * I：分段矩乘，预处理倍增数组。

 * J：f[i]存i子树的答案和i这个联通块的大小，显然只需要统计儿子中答案最大值，和最大值对应的块大小的和，如果块大小的和能做到在b以内，就能并成一块，否则i号点直接独立成一块。每个点的答案换根dp求值。

流水账

比较迷，这个F和wf2017A一模一样，大家当年过的比谁都快，猜了一发数据弱，wa了，非常绝望。yzc上机写I，tle了。然后cjb上机写B，wa了，yzc改了改又tle了，???。cjb找到了错误，B2y72。sub让yzc去预处理，I3y84。sub和yzc开J，yzc上机J1y215。这期间cjb在很努力地写C，但是写法不太对，fix了很多次，C2y252。实在无奈，贴了个F1y256。最后cjb和sub rush H，H4y288。

总结

chenjb

F 4分钟真的能过吗??????????? 我又tm写错双向广搜了，要吸取教训，理解为两边一人走一步，碰到一起就求出解了，同一层要一起转移。

oipotato

subconscious

题解

• A：
• B：等价于保留n-1-k条边，排序后从大到小尽可能贪心取，用并查集维护连通性及是否有黑点。
• C：hash压成long long，双向广搜44步，第45步直接输出。
• D：
• E：
• F：同wf2017 A。
• G：
• H：考察最终答案的单调性，上下移动某个点，最后一定可以移到只有一些人在地面上，某些人在同一高度的平面，转化成分数规划问题，二分答案跑网络流，S向i连b[i]，然后两两连c[i][j]，i向T连k的边，最大流值和n*k比较。
• I：分段矩乘，预处理倍增数组。
• J：f[i]存i子树的答案和i这个联通块的大小，显然只需要统计儿子中答案最大值，和最大值对应的块大小的和，如果块大小的和能做到在b以内，就能并成一块，否则i号点直接独立成一块。每个点的答案换根dp求值。

附加文件

• 1.png by chenjb