2017-Sp310-team2

从 Trac 迁移的文章

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

原文章内容如下：

== 流水账 ==
=== chenjb ===
md这个流量平衡绝对是我的锅
=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：整个行为可以视为一个序列，到最后一个1结束，可以直接算出对于一个集合，这个集合都被抽完的概率，前缀减即可。

 * B：模拟。

 * C：对于每个数统计互质的数*(n-1-互质的数)，答案是所有人-和/2。

 * D：一定保留连续的一段，答案是方差，直接统计。

 * E：直接dp。

 * F：

 * G：考虑每个人要么小于阈值，要么高于阈值，且肯定在其中选择w最大的，然后海明距离为1的点连边可以按1的个数奇偶分成二分图，对于奇，S向i连w[L[i]]流量的边，i向T连w[R[i]]流量的边，偶反过来。然后对于额外收益直接奇向偶连，跑网络流求最小割即可。注意：由于w有负数，可以统一抬高到正数，但是额外收益不能一起抬，因为会导致流量不平衡。

 * H：打表，不要产生重复数字，半分钟内打完，104的答案是10比较慢。

 * I：按题意模拟，注意不要溢出。

 * J：

 * K：暴力枚举匹配情况，polya。

 * L：就是在AC自动机的fail树上进行，将给定点集的子树并+1，询问给定点集到根的链并之和。对于操作，子树的并按dfs序排序之后，如果当前修改的点在上一个修改的点的子树里，就直接删除；对于询问，按dfs排序后，每个人到根的答案-相邻lca到根的答案。对于到根的路径上每个标记，贡献是两个点的深度差，用两个树状数组维护即可。

流水账

chenjb

md这个流量平衡绝对是我的锅

oipotato

subconscious

题解

• A：整个行为可以视为一个序列，到最后一个1结束，可以直接算出对于一个集合，这个集合都被抽完的概率，前缀减即可。
• B：模拟。
• C：对于每个数统计互质的数*(n-1-互质的数)，答案是所有人-和/2。
• D：一定保留连续的一段，答案是方差，直接统计。
• E：直接dp。
• F：
• G：考虑每个人要么小于阈值，要么高于阈值，且肯定在其中选择w最大的，然后海明距离为1的点连边可以按1的个数奇偶分成二分图，对于奇，S向i连w[L[i]]流量的边，i向T连w[R[i]]流量的边，偶反过来。然后对于额外收益直接奇向偶连，跑网络流求最小割即可。注意：由于w有负数，可以统一抬高到正数，但是额外收益不能一起抬，因为会导致流量不平衡。
• H：打表，不要产生重复数字，半分钟内打完，104的答案是10比较慢。
• I：按题意模拟，注意不要溢出。
• J：
• K：暴力枚举匹配情况，polya。
• L：就是在AC自动机的fail树上进行，将给定点集的子树并+1，询问给定点集到根的链并之和。对于操作，子树的并按dfs序排序之后，如果当前修改的点在上一个修改的点的子树里，就直接删除；对于询问，按dfs排序后，每个人到根的答案-相邻lca到根的答案。对于到根的路径上每个标记，贡献是两个点的深度差，用两个树状数组维护即可。