2017-Sp299-team2

从 Trac 迁移的文章

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

原文章内容如下：

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

== 流水账 ==
=== chenjb ===
这个B和之前300iq contest1和NEERC2018简直如出一辙，然后这个K不明白为什么榜上这么拖沓....我感觉主要问题还是取模看起来有点凶，以及这又是一个国内榜debuff的实例。我学弟靠着具体数学干爆了E，很棒棒啊？
=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：按深度从大到小，f[i]+i从小到大贪心匹配。

 * B：x向a,b1,b2,c1连边，b1向b2连边，c1向c2连边，可以证明该模型等价于最优情况，直接带花树即可，也可以上带权带花树硬艹。注意带花树和匈牙利是不支持一边加边一边匹配的。

 * C：

 * D：显然x的父亲是x+lowbit(x)，每个修改只有log个单点修改，把这些单点修改都在树状数组上操作，那对于一个修改x，它的第i个父亲会得到i*v的贡献，询问就是log个单点的求值，sort后扫一遍即可。

 * E：

 * F：

 * G：注意到包含0和不包含0是两种情况，不包含0的情况要先把位数小于当前的所有情况都加进去，注意unsigned long long。

 * H：用前缀和处理出每个位置是否合法，bfs即可。

 * I：g=gcd(k,n)，每g个一组，当g等于gcd(k,2n)时，每组的奇偶性要相同，否则每组都必须是偶数。

 * J：显然取到两端是最大值和最小值之后就没必要变长，而且对于一条路径，两端的人不是最大值或者最小值都会使得这条路径的计算结果变大，所以题意转化为任意一条路径两端的差加上路径长度，用换根dp维护。

 * K：大力分数规划+ac自动机dp即可，double能过，求稳就在法雷序列上二分。

 * L：考虑f[mask]是结果属于mask的概率，对于每一轮只有2^8^种不同的权值，可以通过预处理前缀积和统计乘除0来得到，最后再减回来即可。

流水账

chenjb

这个B和之前300iq contest1和NEERC2018简直如出一辙，然后这个K不明白为什么榜上这么拖沓....我感觉主要问题还是取模看起来有点凶，以及这又是一个国内榜debuff的实例。我学弟靠着具体数学干爆了E，很棒棒啊？

oipotato

subconscious

题解

A：按深度从大到小，f[i]+i从小到大贪心匹配。
B：x向a,b1,b2,c1连边，b1向b2连边，c1向c2连边，可以证明该模型等价于最优情况，直接带花树即可，也可以上带权带花树硬艹。注意带花树和匈牙利是不支持一边加边一边匹配的。
C：
D：显然x的父亲是x+lowbit(x)，每个修改只有log个单点修改，把这些单点修改都在树状数组上操作，那对于一个修改x，它的第i个父亲会得到i*v的贡献，询问就是log个单点的求值，sort后扫一遍即可。
E：
F：
G：注意到包含0和不包含0是两种情况，不包含0的情况要先把位数小于当前的所有情况都加进去，注意unsigned long long。
H：用前缀和处理出每个位置是否合法，bfs即可。
I：g=gcd(k,n)，每g个一组，当g等于gcd(k,2n)时，每组的奇偶性要相同，否则每组都必须是偶数。
J：显然取到两端是最大值和最小值之后就没必要变长，而且对于一条路径，两端的人不是最大值或者最小值都会使得这条路径的计算结果变大，所以题意转化为任意一条路径两端的差加上路径长度，用换根dp维护。
K：大力分数规划+ac自动机dp即可，double能过，求稳就在法雷序列上二分。
L：考虑f[mask]是结果属于mask的概率，对于每一轮只有2⁸种不同的权值，可以通过预处理前缀积和统计乘除0来得到，最后再减回来即可。

附加文件

1.png by chenjb