2017-Sp204-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，cjb坐在机上，先签了个'''J1y8'''，然后又签了个'''A1y11'''，之后抄了个kmp '''L1y20'''。yzc接了sub丢过来的I，'''I1y31'''。cjb开了个H，丢给yzc，'''H1y46'''。cjb接了个sub丢过来的D，'''D2y72'''。yzc理清了E，上机写E，'''E1y88'''。yzc开K，sub和cjb开B，sub上机'''B3y150'''，yzc上机搞K，在sub帮助下'''K2y183'''。cjb期间把F的暴力写好验证了dp方程，然后推出了G的答案上界丢给sub，yzc单开F，之后两人先后上机，yzc发现算法不太对，sub写到了最后MLE了2发。
== 总结 ==
=== chenjb ===
这个F和G有点疼痛啊？DFA合并我们队好像都不太会啊？
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：按题意判定。

 * B：每次有更近的就往更近的走，最后落在正解或者正解的正对面，沿着同一个方向走，直到走到对面，取路径中点即可判断哪个是正解。

 * C：

 * D：f[l][r]表示l到r联通到对应左下角的最短路径，区间dp，注意最后对齐到(0,0)。

 * E：定了颜色的联通块留下一个颜色和一个生成树，未定颜色的联通块留下一个生成树，其余边均可删去。

 * F：yzc

 * G：sub学下？

 * H：所有人归到2a，取2/3的人加上d-a，再取1/3加上d-a，用主席树维护。

 * I：对于1e7所有质数p，如果1.q^n^ mod p=1 2.对于n的所有质因子f，q^n/f^ mod p !=1，则将p统计入答案中。

 * J：模拟。

 * K：二分，每一段折线再二分到能划的最远的位置，用求导找到极值点，判断和下界有无交。

 * L：kmp算出最早最晚匹配位置，看看是否能不overlap。

流水账

出门各自看题，cjb坐在机上，先签了个J1y8，然后又签了个A1y11，之后抄了个kmp L1y20。yzc接了sub丢过来的I，I1y31。cjb开了个H，丢给yzc，H1y46。cjb接了个sub丢过来的D，D2y72。yzc理清了E，上机写E，E1y88。yzc开K，sub和cjb开B，sub上机B3y150，yzc上机搞K，在sub帮助下K2y183。cjb期间把F的暴力写好验证了dp方程，然后推出了G的答案上界丢给sub，yzc单开F，之后两人先后上机，yzc发现算法不太对，sub写到了最后MLE了2发。

总结

chenjb

这个F和G有点疼痛啊？DFA合并我们队好像都不太会啊？

oipotato

subconscious

题解

A：按题意判定。
B：每次有更近的就往更近的走，最后落在正解或者正解的正对面，沿着同一个方向走，直到走到对面，取路径中点即可判断哪个是正解。
C：
D：f[l][r]表示l到r联通到对应左下角的最短路径，区间dp，注意最后对齐到(0,0)。
E：定了颜色的联通块留下一个颜色和一个生成树，未定颜色的联通块留下一个生成树，其余边均可删去。
F：yzc
G：sub学下？
H：所有人归到2a，取2/3的人加上d-a，再取1/3加上d-a，用主席树维护。
I：对于1e7所有质数p，如果1.qⁿ mod p=1 2.对于n的所有质因子f，q^n/f mod p !=1，则将p统计入答案中。
J：模拟。
K：二分，每一段折线再二分到能划的最远的位置，用求导找到极值点，判断和下界有无交。
L：kmp算出最早最晚匹配位置，看看是否能不overlap。

附加文件

1.png by chenjb