2017-Sp282-team2

从 Trac 迁移的文章

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

原文章内容如下：

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

== 流水账 ==
=== chenjb ===
最后E过了还是很不错的，通过这个题对动态点分治、树的重心加深了理解。
=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：每个点的答案是跟自己至少差k个1的子集的最大值+1，对每个点维护一个长度k的数组，表示它的子集对它的贡献还差几个1才能真正产生贡献，考虑如果差的步数更多，值还更小，那就没有存在的必要，所以把长度为k的数组维护成变长的单调队列。

 * B：cjb

 * C：从大到小排序，特判有没有多个最小值，有的话直接bitset模拟dp，倍增可以证明是n^2^/64。

 * D：考虑从全集中去掉一定的物品，取magic个权值最小的物品出来做min背包即可。

 * E：考虑点分治树某个点的贡献，就是它到那些需要增长的关键点的距离差的一个函数，按照mod k意义下讨论即可。

 * F：枚举长度，枚举第一个字母可以确定方案，对差分数组hash来判定是否可行，暴力判定最优答案即可。

 * G：yzc

 * H：sub

 * I：合并两个概率x,y之后得到x+p-2*p*x，动态开点线段树维护即可。

 * J：数学推导可以最后变成对于每个二进制1，选择一个x的合法幂次乘上去，问最后有多少个数字出现奇数次，状态压缩*2^20^动态规划。

流水账

chenjb

最后E过了还是很不错的，通过这个题对动态点分治、树的重心加深了理解。

oipotato

subconscious

题解

• A：每个点的答案是跟自己至少差k个1的子集的最大值+1，对每个点维护一个长度k的数组，表示它的子集对它的贡献还差几个1才能真正产生贡献，考虑如果差的步数更多，值还更小，那就没有存在的必要，所以把长度为k的数组维护成变长的单调队列。
• B：cjb
• C：从大到小排序，特判有没有多个最小值，有的话直接bitset模拟dp，倍增可以证明是n²/64。
• D：考虑从全集中去掉一定的物品，取magic个权值最小的物品出来做min背包即可。
• E：考虑点分治树某个点的贡献，就是它到那些需要增长的关键点的距离差的一个函数，按照mod k意义下讨论即可。
• F：枚举长度，枚举第一个字母可以确定方案，对差分数组hash来判定是否可行，暴力判定最优答案即可。
• G：yzc
• H：sub
• I：合并两个概率x,y之后得到x+p-2*p*x，动态开点线段树维护即可。
• J：数学推导可以最后变成对于每个二进制1，选择一个x的合法幂次乘上去，问最后有多少个数字出现奇数次，状态压缩*2²⁰动态规划。

附加文件

• 1.png by chenjb