2018-Sp22-lyk

从 Trac 迁移的文章

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

原文章内容如下：

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

[/wiki/2018-team3 返回Helianthus]

[http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001424]

[http://10.71.10.90/pia/trac/wiki/2017-Sp126-team2 Legilimens]

== 流水账 ==
点开start就卡住，以为没开始，其实开始了，晚了五分钟。lyk看了A，写了一发，WA。heltion上机写F，写到一半换lyk改了改A，'''A2y39'''。heltion写完F又写了G，'''F1y47''','''G1y54'''。jhguai上机签B，因为接到空的后面时，链表尾指针没有重新赋值WA一发，'''B2y77'''。lyk和heltion讨论了E题，积(bai)分(du)出了扇形重心公式，lyk写了一发，发现比想象中好写很多(环状区间dpGET！)，调了调过了样例，'''E1y130'''。jhguai上机乱搞K，没过样例，下机。期间lyk和heltion讨论出了C，上机快写完了。jhguai发现了错误，测试了几发，大数据比较慢，莽了一发，居然过了，'''K1y205'''。lyk继续上机写C，过了样例，查看了中间过程，确认无误，交了一发，'''C1y214'''。之后一起讨论了H，是个2SAT，讨论后得出3种情况的判断方式，jhguai上机，调了调过了样例，交一发WA了，发现坏孩子可能以前没出现过，fix了下，'''H2y273'''。
== 总结 ==
=== LYK ===
今天非常顺利，。jhguai的乱搞kdtree终于过题了，感动！heltion签到签的很开心，感动！校板的2sat非常好用，mark。学一下2sat。把曼哈顿距离、欧几里得距离最小生成树抄进板子。
=== Jhguai  ===
=== Heltion ===

== 题解 ==
 * A: 模拟
 * B: 模拟
 * C: 答案为1或2,判断是否全部边都是轮廓线,判断方法:坐标轴扩展为两倍,沿轮廓flood-fill一遍得到轮廓线,再枚举所有经过点是否在轮廓线上.
 * D: 答案为选四个点减去不合法的方案,一种是四点共线,一种是三角形加上内部或边界的一个点,第二种枚举与最左边的点相邻两条边的形状,用pick定理可以算出内部点数量,预处理gcd后复杂度是O((rc)^2^).
 * E: 枚举第一个移除的,转化为区间二维DP,O(n)转移,复杂度为O(n^3^)
 * F: 模拟
 * G: 解方程
 * H: 判断2-SAT,如果可行,缩点拓扑排序判断给定的点是否其中两个在一条链上
 * I: 不能做的
 * J:
 * K: std瞎搞方法:分成500*500块 只对块与块之间距离小于某个值(根号(8*10^6^*10^6^/ n)之间的块的点连边;jhguai瞎搞方法:用KDtree每个点只与其距离最近的8个点连边

== 补题 ==

[/wiki/2018-team3 返回Helianthus]

http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001424

Legilimens

流水账

点开start就卡住，以为没开始，其实开始了，晚了五分钟。lyk看了A，写了一发，WA。heltion上机写F，写到一半换lyk改了改A，A2y39。heltion写完F又写了G，F1y47,G1y54。jhguai上机签B，因为接到空的后面时，链表尾指针没有重新赋值WA一发，B2y77。lyk和heltion讨论了E题，积(bai)分(du)出了扇形重心公式，lyk写了一发，发现比想象中好写很多(环状区间dpGET！)，调了调过了样例，E1y130。jhguai上机乱搞K，没过样例，下机。期间lyk和heltion讨论出了C，上机快写完了。jhguai发现了错误，测试了几发，大数据比较慢，莽了一发，居然过了，K1y205。lyk继续上机写C，过了样例，查看了中间过程，确认无误，交了一发，C1y214。之后一起讨论了H，是个2SAT，讨论后得出3种情况的判断方式，jhguai上机，调了调过了样例，交一发WA了，发现坏孩子可能以前没出现过，fix了下，H2y273。

总结

LYK

今天非常顺利，。jhguai的乱搞kdtree终于过题了，感动！heltion签到签的很开心，感动！校板的2sat非常好用，mark。学一下2sat。把曼哈顿距离、欧几里得距离最小生成树抄进板子。

Jhguai

Heltion

题解

• A: 模拟
• B: 模拟
• C: 答案为1或2,判断是否全部边都是轮廓线,判断方法:坐标轴扩展为两倍,沿轮廓flood-fill一遍得到轮廓线,再枚举所有经过点是否在轮廓线上.
• D: 答案为选四个点减去不合法的方案,一种是四点共线,一种是三角形加上内部或边界的一个点,第二种枚举与最左边的点相邻两条边的形状,用pick定理可以算出内部点数量,预处理gcd后复杂度是O((rc)²).
• E: 枚举第一个移除的,转化为区间二维DP,O(n)转移,复杂度为O(n³)
• F: 模拟
• G: 解方程
• H: 判断2-SAT,如果可行,缩点拓扑排序判断给定的点是否其中两个在一条链上
• I: 不能做的
• J:
• K: std瞎搞方法:分成500*500块 只对块与块之间距离小于某个值(根号(8*10⁶*10⁶/ n)之间的块的点连边;jhguai瞎搞方法:用KDtree每个点只与其距离最近的8个点连边

补题

附加文件

• 1.jpg by Heltion