2017-Sp338-team2

从 Trac 迁移的文章

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

原文章内容如下：

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

=== subconscious  ===

== 题解 == 

 * A：暴搜。

 * B：f[0/1/2]表示要父亲点亮，父亲自己会亮但不会点我，我去点父亲三种情况，直接转移。

 * C：n^3^枚举判定。

 * D：按题意模拟。

 * E：令a[1]=-1，a[2..1999]=s，则s*1998+k=(s-1)*1999，解出来得到s的取值，不断贪心减去min(s,1000000)放置即可。

 * F：设gcd的质因子个数为m，转化成每个人有至多2^m^种贡献方式，注意到答案涉及的人数不超过m，所以对于每种贡献方式只保留e最小的m个人即可，注意预处理的时候需要把本质相同的人一起处理。

 * G：考虑记忆化搜索，把图跑一遍传递闭包后进行hash，每个点的hash值是后继hash值的集合hash值，还有自己的出度入度相关的函数，整张图的hash值是所有点的集合hash，大概只有8000+状态。

 * H：枚举n*n%i==0，则1/(n+i)+1/(n+n*n/i)=1/n，更新答案即可。

 * I：一开始先取出最大的X，如果不止一个就无解，否则这个值就是最大值，然后搜索每次取出当前最大的X，如果不止两个就无解，如果只有一个就枚举是跟0的差还是最大值的差，如果是两个的话，就两边各有一个，注意特判和0差x跟和最大值差x相等的情况。

 * J：枚举，bitset优化。

 * K：合并果子裸题。

 * L：求出凸包，如果凸包点数为3，则枚举剩下一个点，否则枚举a和c两个点，b和d随着c移动单调不减，更新答案即可。

 * M：取出质因子，计算每种质因子的数量，剩下的拿走即可，最后crt合并。

流水账

chenjb

oipotato

subconscious

题解

A：暴搜。
B：f[0/1/2]表示要父亲点亮，父亲自己会亮但不会点我，我去点父亲三种情况，直接转移。
C：n³枚举判定。
D：按题意模拟。
E：令a[1]=-1，a[2..1999]=s，则s*1998+k=(s-1)*1999，解出来得到s的取值，不断贪心减去min(s,1000000)放置即可。
F：设gcd的质因子个数为m，转化成每个人有至多2^m种贡献方式，注意到答案涉及的人数不超过m，所以对于每种贡献方式只保留e最小的m个人即可，注意预处理的时候需要把本质相同的人一起处理。
G：考虑记忆化搜索，把图跑一遍传递闭包后进行hash，每个点的hash值是后继hash值的集合hash值，还有自己的出度入度相关的函数，整张图的hash值是所有点的集合hash，大概只有8000+状态。
H：枚举n*n%i==0，则1/(n+i)+1/(n+n*n/i)=1/n，更新答案即可。
I：一开始先取出最大的X，如果不止一个就无解，否则这个值就是最大值，然后搜索每次取出当前最大的X，如果不止两个就无解，如果只有一个就枚举是跟0的差还是最大值的差，如果是两个的话，就两边各有一个，注意特判和0差x跟和最大值差x相等的情况。
J：枚举，bitset优化。
K：合并果子裸题。
L：求出凸包，如果凸包点数为3，则枚举剩下一个点，否则枚举a和c两个点，b和d随着c移动单调不减，更新答案即可。
M：取出质因子，计算每种质因子的数量，剩下的拿走即可，最后crt合并。