2017-Sp311-team2

从 Trac 迁移的文章

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

原文章内容如下：

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

=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：sort后按题意模拟。

 * B：优先填数量多的颜色，用抽屉原理剪枝暴搜。

 * C：2倍，列出同余方程。

 * D：倒过来考虑，f[i][j]代表i和j都活着，其余都死了的最少代价。

 * E：预处理出所有L，可以在每个交点统计非法L对的数量。

 * F：枚举三个二进制位，O(8*50)dp。

 * G：把边表排序，对于每个点之后产生的状态是确定的，只会在偏移量上有差别，gen出1e8个答案后O(1)回答询问。
  * upd by yzc:考虑DP计算每个点向后的方案数，根据DP值进行DAG剖分。每个点将DP值最大的后继标记为重后继，并且倍增出每个点连续走2^j^个重后继之后在哪里，还有比这个走法字典序小的方案数。寻找答案时，先不断的跳重后继，直到不能跳时，二分求出跳哪个轻后继。由于轻后继的方案数最多只有当前点的一半，所以最多只有logk次不断的跳重后继直到不能跳的操作和logk次跳轻后继的操作。复杂度(n+m)logn+qlogklogn。由于DP值可能很大，可以和maxk+delta取min。

 * H：折半后fwt合并。

 * I：K圆并板子题。

 * J：

 * K：答案就是有几个数字的后面存在比自己小的数，set维护即可。

流水账

chenjb

oipotato

subconscious

题解

• A：sort后按题意模拟。
• B：优先填数量多的颜色，用抽屉原理剪枝暴搜。
• C：2倍，列出同余方程。
• D：倒过来考虑，f[i][j]代表i和j都活着，其余都死了的最少代价。
• E：预处理出所有L，可以在每个交点统计非法L对的数量。
• F：枚举三个二进制位，O(8*50)dp。
• G：把边表排序，对于每个点之后产生的状态是确定的，只会在偏移量上有差别，gen出1e8个答案后O(1)回答询问。
  • upd by yzc:考虑DP计算每个点向后的方案数，根据DP值进行DAG剖分。每个点将DP值最大的后继标记为重后继，并且倍增出每个点连续走2^j个重后继之后在哪里，还有比这个走法字典序小的方案数。寻找答案时，先不断的跳重后继，直到不能跳时，二分求出跳哪个轻后继。由于轻后继的方案数最多只有当前点的一半，所以最多只有logk次不断的跳重后继直到不能跳的操作和logk次跳轻后继的操作。复杂度(n+m)logn+qlogklogn。由于DP值可能很大，可以和maxk+delta取min。
• H：折半后fwt合并。
• I：K圆并板子题。
• J：
• K：答案就是有几个数字的后面存在比自己小的数，set维护即可。