2019-Acyclic_SD/AugTrain-31

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(Train-31.png,500px)]]

== 总结 ==

=== Todobe ===

前一个小时签完到，后四个小时把H和K翻过来调过去想了好几个来回，脑细胞精疲力竭，然后GG。

K题甚至还想整个线段树套线段树，后来想想nlog2好像时间和空间也承受不来。

jj倒是把H题分析的差不多，但是写了也没能过。

期间还试图去找G题有没有板子，但是看榜上过题数好像也不是板子题？QWQ

苦苦挣扎，K题没有想到分治的做法。



=== wxx_louisa ===

K题：【Make Rounddog Happy】题解中的办法不够好。题解是枚举最大值所在的一侧区间端点，这样左边和右边分别枚举时会产生重复，会多一些麻烦的处理。其实还可以启发式合并，处理[L,R]时找到最大值所在位置K，考虑跨过K的区间，枚举较短的那一侧端点，另一侧直接维护就好了，预处理部分都很normal。我觉得今天我们一定是失了智，否则套路启发式分治还是可以想一想的！

H题：【Coins】jj啥都想到了，但我们没讨论到将硬币组分成两类。贪心+决策单调性优化。jj还在wa。

G题：【Closest Pair of Segments】O(n2) 加一点剪枝好像可以过。具体剪枝方法是将所有线段排一排序，题解中的二分答案+香肠法，不怎么看得懂。。。


== 补题 ==

总结

Todobe

前一个小时签完到，后四个小时把H和K翻过来调过去想了好几个来回，脑细胞精疲力竭，然后GG。

K题甚至还想整个线段树套线段树，后来想想nlog2好像时间和空间也承受不来。

jj倒是把H题分析的差不多，但是写了也没能过。

期间还试图去找G题有没有板子，但是看榜上过题数好像也不是板子题？QWQ

苦苦挣扎，K题没有想到分治的做法。

wxx_louisa

K题：【Make Rounddog Happy】题解中的办法不够好。题解是枚举最大值所在的一侧区间端点，这样左边和右边分别枚举时会产生重复，会多一些麻烦的处理。其实还可以启发式合并，处理[L,R]时找到最大值所在位置K，考虑跨过K的区间，枚举较短的那一侧端点，另一侧直接维护就好了，预处理部分都很normal。我觉得今天我们一定是失了智，否则套路启发式分治还是可以想一想的！

H题：【Coins】jj啥都想到了，但我们没讨论到将硬币组分成两类。贪心+决策单调性优化。jj还在wa。

G题：【Closest Pair of Segments】O(n2) 加一点剪枝好像可以过。具体剪枝方法是将所有线段排一排序，题解中的二分答案+香肠法，不怎么看得懂。。。

补题