2017-Sp247-team2

从 Trac 迁移的文章

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

原文章内容如下：

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

== 流水账 ==
出门cjb上机写E，没看清有向图和清0，'''E3y25'''。yzc和sub讨论了B，yzc上机tle，之后fix了变成wa，看不透。cjb上机抄NTT，sub上机'''L1y89'''，yzc写着对拍发现问题，'''B4y111'''。sub上机继续写M，'''M1y128'''。sub写D，wa了看不出错，cjb发现用了long double(hdu不能用)，之后'''D3y155'''。cjb和yzc决定上机莽一发I，'''I3y175'''。sub上机写K，'''K1y210'''。cjb和yzc不会做A，sub表示有个复杂度很高的dp，上机wa了对拍，最后'''A2y264'''。最后试图卡F的常，果然卡不过去。咖啡鸡最后过了J。
=== chenjb ===
今天问题在于，我和yzc在A和I上浪费了很多时间，sub则一直在写写写写，互相没有什么交流。一方面是数据范围给的太满，比较怂，另一个还是对于常数没有估计清楚，如果能空出4-50分钟的话，J应该是能过的。过了J，才算是打得还行。
=== oipotato ===

=== subconscious  ===

== 题解 == 
 * A：f[i][j][k][l]代表目前到i，除了最近的一个之外，其他三个数字分别在j，k，l出现，注意压缩状态，O(n^4^)常数/24。

 * B：线性基维护每一个后缀，走到哪里线性基才会变化，只会变化30次，消元时记录最高位在哪里，这样是O(30)的。

 * C：sub

 * D：二分答案，模拟。

 * E：最短路图求最小割。

 * F：yzc

 * G：sub

 * H：sub

 * I：逐位判定，用剩余的L的和和R的和，以及剩下位数判定合法，O(26*26*n)但是能过。

 * J：cjb

 * K：gcd最大只有1e7，下取整的结果是确定的，因此可以直接算出，最后在每个对应gcd乘phi求和即可。

 * L：统计1-3各有多少个，生成函数做FFT。

 * M：判定两个凸包有没有交，注意corner case。

流水账

出门cjb上机写E，没看清有向图和清0，E3y25。yzc和sub讨论了B，yzc上机tle，之后fix了变成wa，看不透。cjb上机抄NTT，sub上机L1y89，yzc写着对拍发现问题，B4y111。sub上机继续写M，M1y128。sub写D，wa了看不出错，cjb发现用了long double(hdu不能用)，之后D3y155。cjb和yzc决定上机莽一发I，I3y175。sub上机写K，K1y210。cjb和yzc不会做A，sub表示有个复杂度很高的dp，上机wa了对拍，最后A2y264。最后试图卡F的常，果然卡不过去。咖啡鸡最后过了J。

chenjb

今天问题在于，我和yzc在A和I上浪费了很多时间，sub则一直在写写写写，互相没有什么交流。一方面是数据范围给的太满，比较怂，另一个还是对于常数没有估计清楚，如果能空出4-50分钟的话，J应该是能过的。过了J，才算是打得还行。

oipotato

subconscious

题解

A：f[i][j][k][l]代表目前到i，除了最近的一个之外，其他三个数字分别在j，k，l出现，注意压缩状态，O(n⁴)常数/24。
B：线性基维护每一个后缀，走到哪里线性基才会变化，只会变化30次，消元时记录最高位在哪里，这样是O(30)的。
C：sub
D：二分答案，模拟。
E：最短路图求最小割。
F：yzc
G：sub
H：sub
I：逐位判定，用剩余的L的和和R的和，以及剩下位数判定合法，O(26*26*n)但是能过。
J：cjb
K：gcd最大只有1e7，下取整的结果是确定的，因此可以直接算出，最后在每个对应gcd乘phi求和即可。
L：统计1-3各有多少个，生成函数做FFT。
M：判定两个凸包有没有交，注意corner case。

附加文件

1.png by chenjb