2017-Sp186-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，sub上机写H，'''H1y13'''，cjb上机写A，'''A1y18'''，yzc上机wa C，cjb和sub确认D之后上机写D，'''D1y45'''，sub上机写I，'''I1y48'''，yzc上机搞C，'''C3y55'''。cjb上机写G，'''G1y84'''。cjb丢了J给yzc，yzc上机'''J1y109'''。然后三人开始讨论F，cjb给出了一个线段树的维护方式，之后yzc和sub上机'''F2y182'''。之后三人讨论E，yzc和sub最后'''E2y257'''，sub上机rush B，结束后才过，痛失AK。
== 总结 ==
=== chenjb ===
感觉如果想AK的前提是我和yzc能不靠sub搞出E。
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：同色连0，异色连1，floyd之后对于每个人取最远的距离然后取min，和原题意等价。

 * B：三分起点到圆上的位置，再三分终点到圆的位置，在圆上每次跳t即可。

 * C：广搜。

 * D：三分时间t即可。

 * E：f[0/1][I][j]表示i这个子树有j个人作弊，0/1代表i的儿子是否作弊，转移的时候先剔除所有系数，最后乘以(size[i]-1)!除以size[son[i]]!，在1转移的时候还需要一个额外系数。

 * F：分解质因数，对于每个质因数，取拥有这个质因数的前驱和后继，可以算出有哪些区间变为了非法区间，用线段树维护最小值及最小值个数，删除同理。

 * G：爆搜每一条最短路，检查时将最短路上的点权值置为w[i]，用dij算出最小代价即可。

 * H：维护前缀不同的gcd，最后直接在1到100里扫一遍即可。

 * I：在n以内不同的区间和只有nlogn种，预处理枚举即可。

 * J：旅行商问题，状压dp即可，稍微复杂一点。

流水账

出门各自看题，sub上机写H，H1y13，cjb上机写A，A1y18，yzc上机wa C，cjb和sub确认D之后上机写D，D1y45，sub上机写I，I1y48，yzc上机搞C，C3y55。cjb上机写G，G1y84。cjb丢了J给yzc，yzc上机J1y109。然后三人开始讨论F，cjb给出了一个线段树的维护方式，之后yzc和sub上机F2y182。之后三人讨论E，yzc和sub最后E2y257，sub上机rush B，结束后才过，痛失AK。

总结

chenjb

感觉如果想AK的前提是我和yzc能不靠sub搞出E。

oipotato

subconscious

题解

• A：同色连0，异色连1，floyd之后对于每个人取最远的距离然后取min，和原题意等价。
• B：三分起点到圆上的位置，再三分终点到圆的位置，在圆上每次跳t即可。
• C：广搜。
• D：三分时间t即可。
• E：f[0/1][I][j]表示i这个子树有j个人作弊，0/1代表i的儿子是否作弊，转移的时候先剔除所有系数，最后乘以(size[i]-1)!除以size[son[i]]!，在1转移的时候还需要一个额外系数。
• F：分解质因数，对于每个质因数，取拥有这个质因数的前驱和后继，可以算出有哪些区间变为了非法区间，用线段树维护最小值及最小值个数，删除同理。
• G：爆搜每一条最短路，检查时将最短路上的点权值置为w[i]，用dij算出最小代价即可。
• H：维护前缀不同的gcd，最后直接在1到100里扫一遍即可。
• I：在n以内不同的区间和只有nlogn种，预处理枚举即可。
• J：旅行商问题，状压dp即可，稍微复杂一点。

附加文件

• 1.png by chenjb