2017-Sp100-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，一直没人过题，之后终于发现K可做，yzc和sub讨论了K的做法，上机写K，wa了之后发现有个情况没考虑，'''K2y58'''。cjb和sub讨论了D，cjb上机'''D1y93'''。之后sub上机写C，一直在wa。cjb和yzc研究I和E，之后终于有了I的做法，yzc上机写I，期间sub多次上机还是wa。yzc I wa了，准备写对拍，cjb想到了corner case，修改之后'''I2y197'''。之后sub继续搞C，yzc和cjb搞E，之后cjb给yzc讲了A，yzc开始构造A，sub终于过了'''C8y228'''。之后cjb和sub上机写E，yzc推A，最后疯狂wa E，yzc推好了一半的情况，另一半需要一个暴力，时间不够了，没能出题，最后现场榜rk 16。
== 总结 ==
=== chenjb ===
有点可惜，封榜策略还是要磨炼。另外这个F好像是个傻屌题啊，感觉没读亏大了.....一定要注意多读题，不要迷信榜。
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：构造找到方法从n推到n+4的方法，由于3->7该方法不可行，所以要暴力找出3~7的解。

 * B：离散的食物部分是一个多重背包，按照不同的剩余系分开处理之后DP方程就是一个斜率优化的式子了，连续的食物部分@sub。

 * C：算出重心，根据多边形最左接地侧和最右接地侧分类讨论即可。

 * D：枚举终点，f[i]表示从i出发到终点的最小步数，bfs更新，只考虑取bfs到的第一个集合的值更新f[x]。

 * E：迭代哈希，点哈希值为它的所有邻居和其邻居的邻居沿逆时针方向走一圈的哈希值再哈希起来。

 * F：二分送信时间t，然后把b的时间往前提t和a对齐，然后就是两条折线求最近距离是否<=t了，向量做个差处理成离原点最近距离，抄个点到线段距离就好了(不懂几何的cjb如是说)。

 * G：不妨设A>=B，从大到小枚举A的值，然后B的值显然可以二分，然后用2-sat跑tarjan判定，这样是O(n^4^log(n^2^))。然而考虑枚举到第k大边，从1到k的边组成的图如果不能黑白染色，那么显然会存在至少一条边，因此此时为下界，做完之后直接break即可。另一种情况是考虑加入一条边后构成偶环，因为如果这条边存在的话，环上一定存在两相邻点同色，那么不符合设定，因此不需要枚举直接continue。综上，只有至多n次有效枚举，所以复杂度变为O(n^3^log(n^2^))。

 * H：高斯消元。考虑这张图的流量图，设第一行的结果为未知数，一路推到最后一行即可得解，注意最后答案要归一化。

 * I：枚举最远的两点，以这两点距离p为半径作圆，圆中的点若距离超过p则连边，此图一定是二分图，求最大独立集即可。

 * J：'''听Dreadnought说要暴力存所有的速度区间???怎么只有华沙过???? 咕咕咕'''

 * K：倍增求出每个点为起点走2^p^步能到达的最远端，暴力枚举跨越断点的区间，用倍增求出答案，记得在一开始求一遍从1-n的答案。

 * L：'''farmland，记得用sjtu板子  sub'''

 * [https://wiki-nightfall.icpc-camp.org/World%20Finals%202014 Nightfall]

 * [https://wiki.icpc-camp.org/new-meta/2017/3/19%20WorldFinal2014 New Meta]

 * [https://wiki.icpc-camp.org/dreadnought/World%20Finals%202014 Dreadnought]
== 补题 ==

流水账

开场各自看题，一直没人过题，之后终于发现K可做，yzc和sub讨论了K的做法，上机写K，wa了之后发现有个情况没考虑，K2y58。cjb和sub讨论了D，cjb上机D1y93。之后sub上机写C，一直在wa。cjb和yzc研究I和E，之后终于有了I的做法，yzc上机写I，期间sub多次上机还是wa。yzc I wa了，准备写对拍，cjb想到了corner case，修改之后I2y197。之后sub继续搞C，yzc和cjb搞E，之后cjb给yzc讲了A，yzc开始构造A，sub终于过了C8y228。之后cjb和sub上机写E，yzc推A，最后疯狂wa E，yzc推好了一半的情况，另一半需要一个暴力，时间不够了，没能出题，最后现场榜rk 16。

总结

chenjb

有点可惜，封榜策略还是要磨炼。另外这个F好像是个傻屌题啊，感觉没读亏大了.....一定要注意多读题，不要迷信榜。

oipotato

subconscious

题解

• A：构造找到方法从n推到n+4的方法，由于3->7该方法不可行，所以要暴力找出3~7的解。
• B：离散的食物部分是一个多重背包，按照不同的剩余系分开处理之后DP方程就是一个斜率优化的式子了，连续的食物部分@sub。
• C：算出重心，根据多边形最左接地侧和最右接地侧分类讨论即可。
• D：枚举终点，f[i]表示从i出发到终点的最小步数，bfs更新，只考虑取bfs到的第一个集合的值更新f[x]。
• E：迭代哈希，点哈希值为它的所有邻居和其邻居的邻居沿逆时针方向走一圈的哈希值再哈希起来。
• F：二分送信时间t，然后把b的时间往前提t和a对齐，然后就是两条折线求最近距离是否<=t了，向量做个差处理成离原点最近距离，抄个点到线段距离就好了(不懂几何的cjb如是说)。
• G：不妨设A>=B，从大到小枚举A的值，然后B的值显然可以二分，然后用2-sat跑tarjan判定，这样是O(n⁴log(n²))。然而考虑枚举到第k大边，从1到k的边组成的图如果不能黑白染色，那么显然会存在至少一条边，因此此时为下界，做完之后直接break即可。另一种情况是考虑加入一条边后构成偶环，因为如果这条边存在的话，环上一定存在两相邻点同色，那么不符合设定，因此不需要枚举直接continue。综上，只有至多n次有效枚举，所以复杂度变为O(n³log(n²))。
• H：高斯消元。考虑这张图的流量图，设第一行的结果为未知数，一路推到最后一行即可得解，注意最后答案要归一化。
• I：枚举最远的两点，以这两点距离p为半径作圆，圆中的点若距离超过p则连边，此图一定是二分图，求最大独立集即可。
• J：听Dreadnought说要暴力存所有的速度区间???怎么只有华沙过???? 咕咕咕
• K：倍增求出每个点为起点走2^p步能到达的最远端，暴力枚举跨越断点的区间，用倍增求出答案，记得在一开始求一遍从1-n的答案。
• L：farmland，记得用sjtu板子 sub
• Nightfall
• New Meta
• Dreadnought

补题

附加文件

• 1.png by chenjb