2017-Sp316-team2

从 Trac 迁移的文章

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

原文章内容如下：

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

=== subconscious  ===

== 题解 == 

 * A：先*个16^n^，然后套公式即可。

 * B：考虑上下一对边，如果有一条不存在，另一条必为桥，并且两边的情况独立。所以考虑用set维护所有的连续的上下一对边都完整的区间，每个区间内的非桥边的数量就是最靠近两端的竖线之间的横线数量和所有的竖线数量。用线段树维护竖线即可动态得到一个区间的答案。横线发生变动时维护set并维护非桥边数量即可。答案显然就是边的数量减去非桥边数量。

 * C：最大空凸包

 * D：

 * E：

 * F：递推式为f[i]=4f[i-1]-f[i-2]

 * G：魔改后缀数组。

 * H：大力概率dp，注意精度。

 * I：把四个数加起来，注意输出的小trick。

 * J：

 * K：要么是a[1]..a[n-1]，要么是a[2]..a[n]的空格数量，取max。

 * L：对于一条边，只要两端子树>=k就能放进答案。

 * M：每个点按照度数等比例取值，直接统计被删掉的数量即可。

流水账

chenjb

oipotato

subconscious

题解

• A：先*个16ⁿ，然后套公式即可。
• B：考虑上下一对边，如果有一条不存在，另一条必为桥，并且两边的情况独立。所以考虑用set维护所有的连续的上下一对边都完整的区间，每个区间内的非桥边的数量就是最靠近两端的竖线之间的横线数量和所有的竖线数量。用线段树维护竖线即可动态得到一个区间的答案。横线发生变动时维护set并维护非桥边数量即可。答案显然就是边的数量减去非桥边数量。
• C：最大空凸包
• D：
• E：
• F：递推式为f[i]=4f[i-1]-f[i-2]
• G：魔改后缀数组。
• H：大力概率dp，注意精度。
• I：把四个数加起来，注意输出的小trick。
• J：
• K：要么是a[1]..a[n-1]，要么是a[2]..a[n]的空格数量，取max。
• L：对于一条边，只要两端子树>=k就能放进答案。
• M：每个点按照度数等比例取值，直接统计被删掉的数量即可。