2017-Sp272-team2

从 Trac 迁移的文章

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

原文章内容如下：

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

== 流水账 ==
出门做I，感觉做法很假，wa了之后很难受。sub丢了B做法给cjb，cjb上机wa了。I继续改进，变成PE。询问clar问了确定PE是自己程序挂而不是超出询问次数。之后sub发现自己给的做法有个corner case，fix之后'''B2y99'''。cjb让yzc造了个大点，发现yzc的cmp函数没return找到问题后'''I3y125'''。之后sub做了个G，'''G1y143'''。榜上很自闭，sub和yzc决定大力容斥一下K，发现能跑出来，打表'''K1y195'''。最后sub和yzc努力搞E，一开始打算线段树高斯消元，后来变成一段精简的代码，'''E1y243'''。
=== chenjb ===
今天打得很好啊？这个I要果断点不要自闭啊？感觉跟榜跟的很对.jpg
=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：

 * B：找到x的最高的1所在位置p，然后把所有数字按照前p-1位分组，答案是组之间贡献相乘，组内可以取0、1、2，0只有一种，1有size个，2就插进trie里暴力统计即可。注意如果x是0，特判输出2^n^。

 * C：

 * D：

 * E：按w从大到小排序，储存被前i个人消出的最小可能自由元，然后插入维护O(128)。

 * F：a+b>=s要满足，首先a>=s/2和b>=s/2至少一个满足，于是把每条边拆成2个值为s/2的事件，每个连通块用set维护事件，每次把新触发的事件放进全局的set中，从小到大处理。对于一个i，如果触发了事件但是还不满足，就插入两个事件x+(s-x-y)/2,y+(s-x-y)/2，由于s-x-y的值每次至少/2，所以至多NlogC次插入新事件，总复杂度NlogNlogC。

 * G：所有情况减掉到到达字母相同的时候的情况，可以O(n)枚举踏入那种情况的边界，计算即可。

 * H：每个询问很容易建出费用流模型，不妨设区间选恰好x个满足题意的区间的答案为f(x)，根据费用流的性质，f(x)-f(x-1)是递减的，所以f(x)构成了一个凸包。考虑用线段树维护区间[l,r]，左端点在不在，右端点在不在的凸包，合并两个凸包相当于求闵可夫斯基和，注意左边的右端点和右边的左端点同时存在时，还可以转移到区间个数-1。对于询问，考虑wqs二分，然后在相应的线段树区间上二分出最大值，类似预处理进行合并。由于可以离线，所以考虑整体二分，但是不进行分治，而是对于同一层的二分，根据询问的斜率排序，则可以省去凸包上二分这一步。总复杂度16*(N+Q)logNlogC，C为wqs二分的取值范围。

 * I：每次找到重心，二分在哪棵子树里，二分方式是按照子树大小二分。

 * J：考虑DP，f[i][j][0/1]表示i这棵子树，选了j个匹配，节点i选/不选的答案。可以发现，dp值构成了一个凸包，考虑轻重链剖分，每个节点v维护三元组：1.考虑所有轻儿子的DP值的凸包，2.考虑所有轻儿子和节点v的DP值的凸包，3.节点v和父亲的边的长度。对于每个节点v，我们首先对其每一个轻儿子x，将x为顶端的整条重链的三元组合并，合并方式为在重链上分治，用[0/1][0/1]状态表示区间左右端分别有没有被选。然后，将每个轻儿子合并出的结果合并起来，作为节点v的三元组，合并方式依旧还是分治，每个轻儿子在递归底端插入和父亲的边，在分治区间为[l,r]时，将[l,mid]中不插入父亲边的结果合并入[mid+1,r]中，反过来同理，然后取最优作为区间结果。最后需要对根节点再做一次重链合并。所有的DP值合并操作均为求两个凸包的闵可夫斯基和，直接逐差之后归并排序，然后再累加起来即可。

 * K：枚举所有不合法情况出现不出现，用并查集维护，容斥，及时退出。打表即可。

流水账

出门做I，感觉做法很假，wa了之后很难受。sub丢了B做法给cjb，cjb上机wa了。I继续改进，变成PE。询问clar问了确定PE是自己程序挂而不是超出询问次数。之后sub发现自己给的做法有个corner case，fix之后B2y99。cjb让yzc造了个大点，发现yzc的cmp函数没return找到问题后I3y125。之后sub做了个G，G1y143。榜上很自闭，sub和yzc决定大力容斥一下K，发现能跑出来，打表K1y195。最后sub和yzc努力搞E，一开始打算线段树高斯消元，后来变成一段精简的代码，E1y243。

chenjb

今天打得很好啊？这个I要果断点不要自闭啊？感觉跟榜跟的很对.jpg

oipotato

subconscious

题解

A：
B：找到x的最高的1所在位置p，然后把所有数字按照前p-1位分组，答案是组之间贡献相乘，组内可以取0、1、2，0只有一种，1有size个，2就插进trie里暴力统计即可。注意如果x是0，特判输出2ⁿ。
C：
D：
E：按w从大到小排序，储存被前i个人消出的最小可能自由元，然后插入维护O(128)。
F：a+b>=s要满足，首先a>=s/2和b>=s/2至少一个满足，于是把每条边拆成2个值为s/2的事件，每个连通块用set维护事件，每次把新触发的事件放进全局的set中，从小到大处理。对于一个i，如果触发了事件但是还不满足，就插入两个事件x+(s-x-y)/2,y+(s-x-y)/2，由于s-x-y的值每次至少/2，所以至多NlogC次插入新事件，总复杂度NlogNlogC。
G：所有情况减掉到到达字母相同的时候的情况，可以O(n)枚举踏入那种情况的边界，计算即可。
H：每个询问很容易建出费用流模型，不妨设区间选恰好x个满足题意的区间的答案为f(x)，根据费用流的性质，f(x)-f(x-1)是递减的，所以f(x)构成了一个凸包。考虑用线段树维护区间[l,r]，左端点在不在，右端点在不在的凸包，合并两个凸包相当于求闵可夫斯基和，注意左边的右端点和右边的左端点同时存在时，还可以转移到区间个数-1。对于询问，考虑wqs二分，然后在相应的线段树区间上二分出最大值，类似预处理进行合并。由于可以离线，所以考虑整体二分，但是不进行分治，而是对于同一层的二分，根据询问的斜率排序，则可以省去凸包上二分这一步。总复杂度16*(N+Q)logNlogC，C为wqs二分的取值范围。
I：每次找到重心，二分在哪棵子树里，二分方式是按照子树大小二分。
J：考虑DP，f[i][j][0/1]表示i这棵子树，选了j个匹配，节点i选/不选的答案。可以发现，dp值构成了一个凸包，考虑轻重链剖分，每个节点v维护三元组：1.考虑所有轻儿子的DP值的凸包，2.考虑所有轻儿子和节点v的DP值的凸包，3.节点v和父亲的边的长度。对于每个节点v，我们首先对其每一个轻儿子x，将x为顶端的整条重链的三元组合并，合并方式为在重链上分治，用[0/1][0/1]状态表示区间左右端分别有没有被选。然后，将每个轻儿子合并出的结果合并起来，作为节点v的三元组，合并方式依旧还是分治，每个轻儿子在递归底端插入和父亲的边，在分治区间为[l,r]时，将[l,mid]中不插入父亲边的结果合并入[mid+1,r]中，反过来同理，然后取最优作为区间结果。最后需要对根节点再做一次重链合并。所有的DP值合并操作均为求两个凸包的闵可夫斯基和，直接逐差之后归并排序，然后再累加起来即可。
K：枚举所有不合法情况出现不出现，用并查集维护，容斥，及时退出。打表即可。

附加文件

1.png by chenjb