2017-Sp339-team2

从 Trac 迁移的文章

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

原文章内容如下：

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

=== subconscious  ===

== 题解 == 

 * A：显然只会操作第一个最大值左边的数，对于一个数，如果它前面，有数字比它大，就不可能把它加到最大值，一组数字都达到最大值的操作数量是最小值和最大值的差，所以枚举起点，往后遇到>=的就取，就能得到每个起点的最优值，当我们加入一个人的时候，根据是否变大，将会对前面每个人的操作数量，还有贡献值都产生相同的影响，当数字严格比之前的最大值大的时候，就会产生新的起点，每个起点都是一个二元组，然后每个询问也是一个二元组，用凸包维护点积的最大值。

 * B：可以理解为恰好k棵有向生成树，用wqs二分解决，将特殊边连上每个点，把是否是特殊边的信息压进边权，需要用左偏树优化的朱刘。

 * C：三分套三分。

 * D：黑白染色，取出现少的。

 * E：相当于对转移的n个矩形做扫描线。

 * F：质数p=3k+2，有k+1到2k+1 (%p)是一个解，且每个值*t%p也是一个解，随机t。(顺便一提这个叫sum-free subset)

 * G：

 * H：

 * I：

 * J：f[i][0/1][j]表示i到父亲的边染了黑色或白色，子树里需要另一种颜色的路径头最深的是j的方案数，分类讨论转移即可。

 * K：考虑最终状态，一定是前面一些无关的数当中1-k，后面一些无关的数当中1-k，这样答案就由1-k内部的逆序对，和1-k跟内部无关的数的逆序对组成，所以求出前i个无关的数，各自都有多少个1-k在之前，剩下的数有多少个1-k在之后，取min即可。

 * L：暴力取前k位，然后循环，不够的话就+1，注意进位。

 * M：枚举一一对应谁，暴力check。

流水账

chenjb

oipotato

subconscious

题解

• A：显然只会操作第一个最大值左边的数，对于一个数，如果它前面，有数字比它大，就不可能把它加到最大值，一组数字都达到最大值的操作数量是最小值和最大值的差，所以枚举起点，往后遇到>=的就取，就能得到每个起点的最优值，当我们加入一个人的时候，根据是否变大，将会对前面每个人的操作数量，还有贡献值都产生相同的影响，当数字严格比之前的最大值大的时候，就会产生新的起点，每个起点都是一个二元组，然后每个询问也是一个二元组，用凸包维护点积的最大值。
• B：可以理解为恰好k棵有向生成树，用wqs二分解决，将特殊边连上每个点，把是否是特殊边的信息压进边权，需要用左偏树优化的朱刘。
• C：三分套三分。
• D：黑白染色，取出现少的。
• E：相当于对转移的n个矩形做扫描线。
• F：质数p=3k+2，有k+1到2k+1 (%p)是一个解，且每个值*t%p也是一个解，随机t。(顺便一提这个叫sum-free subset)
• G：
• H：
• I：
• J：f[i][0/1][j]表示i到父亲的边染了黑色或白色，子树里需要另一种颜色的路径头最深的是j的方案数，分类讨论转移即可。
• K：考虑最终状态，一定是前面一些无关的数当中1-k，后面一些无关的数当中1-k，这样答案就由1-k内部的逆序对，和1-k跟内部无关的数的逆序对组成，所以求出前i个无关的数，各自都有多少个1-k在之前，剩下的数有多少个1-k在之后，取min即可。
• L：暴力取前k位，然后循环，不够的话就+1，注意进位。
• M：枚举一一对应谁，暴力check。