2019-Sp026-lyk
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[[Image(1.png,700px)]]
[[Image(2.png,700px)]]
[http://10.71.10.90/pia/trac/wiki/2019-team2 返回Runespoor]
[http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=006236 contest]
== 流水账 ==
今天题目不难，节奏感强。但是最后没有ak，还是有需要提升的地方。
签到：A , B , C , D
中期： F , H , E
后期： G , I , J
== 总结 ==
zqq: 今天我真的很不清醒，可能是因为午觉睡过头了。
开始把C题状压看成了斯坦纳树，想了很久。然后D题题意还读错了，根本没有意识到榜上过来很多的题目必定是签到题。
lyk的J题搜索很稳，我们后期才有时间去把I和G做出来
I题是一个比较常规的高消，但是其中的细节还是比较多的。E题仍旧被卡精读，'''算几真的角度要少用'''
后期我整个人都在想G，想这么久的原因是因为开始完全走到了错误的结论上面。后来heltion一下子就说出了正确的方向，然后转化成一个堆维护费用流的模型。这个东西其实没有什么细节，莫名其妙的想了很久，还写错了好多地方。没有想清楚。
像E题放在最后是正确的。或许我早点过G，E题的判断方法多一个人想可能会想出叉积的做法。
总结一下。今天的题目偏简单，但是仍然犯了很多错误，离ak还是有非常大的差距！虽然在榜上ak的队伍很少，可能因为那些强队刚组建或者状态不太好。今天题目涉及的范围还是比较广，但是套路有点老和常规。
Heltion: 每天都在和精度作斗争.H不会算弓形面积WA了2发.
lyk: E题使用atan2不仅精度有问题，而且区间合并也很麻烦。学着标程用点对表示区间，叉积去合并，很快就过了。标程用了与数据相关的动态eps，把角度范围向内缩了1e8分之1。我用了静态的eps，直接判最后叉积是否大于eps。两种都能过，但标程的感觉比较好。
== 题解 ==
[wiki:2017-Sp225-team2 legilimens]
[https://blog.csdn.net/qq_39972971/article/details/86677172 G的加强版]
* E : 镜面对称但是没有终点不能翻转点，只能翻转多边形。最后判断的时候角度范围应该用叉积，用atan2难写并且卡精度。
* G ： 每个点都有度数限制的最小生成树是不可做问题，而这道题是利用边权 = |pj - pi|的性质。把度数 >= 2点连成链，然后度数为一的点和他们匹配。匹配直接用堆维护，因为“餐厅”不带权，所以维护单边撤销即可。复杂度O(nlogn)
* I ： 高消。可以暴搜出所有有效状态，即一些点的右下角已经完成匹配。状态只有252种
* J ： 暴搜 + 剪枝。开始以为可以压位直接判定，然而复杂度压不下来。lyk告诉我直接暴搜。剪枝技巧很好所以直接过了！但是很多队都卡了很久。
== 补题 ==
流水账
今天题目不难，节奏感强。但是最后没有ak，还是有需要提升的地方。
签到：A , B , C , D
中期： F , H , E
后期： G , I , J
总结
zqq: 今天我真的很不清醒，可能是因为午觉睡过头了。
开始把C题状压看成了斯坦纳树，想了很久。然后D题题意还读错了，根本没有意识到榜上过来很多的题目必定是签到题。
lyk的J题搜索很稳，我们后期才有时间去把I和G做出来
I题是一个比较常规的高消，但是其中的细节还是比较多的。E题仍旧被卡精读，算几真的角度要少用
后期我整个人都在想G，想这么久的原因是因为开始完全走到了错误的结论上面。后来heltion一下子就说出了正确的方向，然后转化成一个堆维护费用流的模型。这个东西其实没有什么细节，莫名其妙的想了很久，还写错了好多地方。没有想清楚。
像E题放在最后是正确的。或许我早点过G，E题的判断方法多一个人想可能会想出叉积的做法。
总结一下。今天的题目偏简单，但是仍然犯了很多错误，离ak还是有非常大的差距！虽然在榜上ak的队伍很少，可能因为那些强队刚组建或者状态不太好。今天题目涉及的范围还是比较广，但是套路有点老和常规。
Heltion: 每天都在和精度作斗争.H不会算弓形面积WA了2发.
lyk: E题使用atan2不仅精度有问题，而且区间合并也很麻烦。学着标程用点对表示区间，叉积去合并，很快就过了。标程用了与数据相关的动态eps，把角度范围向内缩了1e8分之1。我用了静态的eps，直接判最后叉积是否大于eps。两种都能过，但标程的感觉比较好。
题解
- E : 镜面对称但是没有终点不能翻转点，只能翻转多边形。最后判断的时候角度范围应该用叉积，用atan2难写并且卡精度。
- G ： 每个点都有度数限制的最小生成树是不可做问题，而这道题是利用边权 = |pj - pi|的性质。把度数 >= 2点连成链，然后度数为一的点和他们匹配。匹配直接用堆维护，因为“餐厅”不带权，所以维护单边撤销即可。复杂度O(nlogn)
- I ： 高消。可以暴搜出所有有效状态，即一些点的右下角已经完成匹配。状态只有252种
- J ： 暴搜 + 剪枝。开始以为可以压位直接判定，然而复杂度压不下来。lyk告诉我直接暴搜。剪枝技巧很好所以直接过了！但是很多队都卡了很久。