2016-S04-team1
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
比赛链接: http://10.71.10.90/sfiction/ranklist/2016_CCPC_Final_Ningbo/ranklist.htm
== 流水账 ==
[http://www.cc98.org/dispbbs.asp?boardID=329&ID=4670121 2016 CCPC Final小结 by sfiction @Siunaus]
== 总结 ==
== 题解 ==
AJL略去不表。
=== B. Wash [sfiction] ===
先考虑前半问题，可以用一个堆维护每个洗衣机再加一件衣服的结束时间。取其中最小值即可。又注意到后半部分可以令所有烘干机都恰好在最后结束任务，容易发现两部分是对称的。因此做两遍，然后倒序相加取最大值即可。O(Llogn)。
=== D. Mr.Panda and Survey [sfiction] ===
首先将Tom一般化，将i-R也加入边。保留u<=v的单向边。从小到大枚举u，检查所有对应v。用vis[v]表示v是否已被访问，如果已被访问说明至少存在一个比u更高级别的人，u不可能成为v的leader。如果未被访问，则u有可能成为v的leader。当u可能成为的leader数量大于c[u]时，超出的部分（选择哪些v并不影响结果）的leader应该另有其人，可以是一个stranger，也可以是排名比u更高的人，因此可以作为一种待定ranklist。当u可能成为的leader数量小于c[u]时，缺少的部分可以从满足限制的待定ranklist中获得，也可以靠stranger获得。上述过程中u也可能是自己的leader，因此需要加入(u,u)的边。O(n+m)。
=== F. Periodical Cicadas [sfiction] ===
1-40的LCM在long long范围内，合并同余式可以用CRT，单次合并复杂度为O(logn)。用ST表维护可以做到O(n^2^log^2^nlogV+QlogV)。
=== G. Pandaland [JTJL && Akalm] ===
平面图上的最小环问题。正解是转化对偶图+全局最小割解决。赛场上我们直接枚举起点和终点并禁用连接他们的边，然后dij+优先队列通过。要在更新到终点的时候立刻跳出结束，否则会T。
=== H. Engineer Assignment [Akalm] ===
f[i][mask]表示当前已处理i个项目，工程师使用状况为mask的最多通过项目数。暴力枚举工程师使用集合即可。
=== I. Mr.Panda and Crystal [sfiction] ===
考虑求出所有物品的最小产生代价，然后做一遍背包。因为用一个物品A去产生另一个物品B，代价一定不会更低，因此可以用类似Dijkstra的方法，每次取一个代价最小的物品根据公式去更新其他物品。代价相同时选哪个都无所谓。O(n(n+K)+nm)。比赛链接: http://10.71.10.90/sfiction/ranklist/2016_CCPC_Final_Ningbo/ranklist.htm
流水账
2016 CCPC Final小结 by sfiction @Siunaus
总结
题解
AJL略去不表。
B. Wash [sfiction]
先考虑前半问题，可以用一个堆维护每个洗衣机再加一件衣服的结束时间。取其中最小值即可。又注意到后半部分可以令所有烘干机都恰好在最后结束任务，容易发现两部分是对称的。因此做两遍，然后倒序相加取最大值即可。O(Llogn)。
D. Mr.Panda and Survey [sfiction]
首先将Tom一般化，将i-R也加入边。保留u<=v的单向边。从小到大枚举u，检查所有对应v。用vis[v]表示v是否已被访问，如果已被访问说明至少存在一个比u更高级别的人，u不可能成为v的leader。如果未被访问，则u有可能成为v的leader。当u可能成为的leader数量大于c[u]时，超出的部分（选择哪些v并不影响结果）的leader应该另有其人，可以是一个stranger，也可以是排名比u更高的人，因此可以作为一种待定ranklist。当u可能成为的leader数量小于c[u]时，缺少的部分可以从满足限制的待定ranklist中获得，也可以靠stranger获得。上述过程中u也可能是自己的leader，因此需要加入(u,u)的边。O(n+m)。
F. Periodical Cicadas [sfiction]
1-40的LCM在long long范围内，合并同余式可以用CRT，单次合并复杂度为O(logn)。用ST表维护可以做到O(n2log2nlogV+QlogV)。
G. Pandaland [JTJL && Akalm]
平面图上的最小环问题。正解是转化对偶图+全局最小割解决。赛场上我们直接枚举起点和终点并禁用连接他们的边，然后dij+优先队列通过。要在更新到终点的时候立刻跳出结束，否则会T。
H. Engineer Assignment [Akalm]
f[i][mask]表示当前已处理i个项目，工程师使用状况为mask的最多通过项目数。暴力枚举工程师使用集合即可。
I. Mr.Panda and Crystal [sfiction]
考虑求出所有物品的最小产生代价，然后做一遍背包。因为用一个物品A去产生另一个物品B，代价一定不会更低，因此可以用类似Dijkstra的方法，每次取一个代价最小的物品根据公式去更新其他物品。代价相同时选哪个都无所谓。O(n(n+K)+nm)。