2017-C14-team1

从 Trac 迁移的文章

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

原文章内容如下：

== lsmll ==

流水账：仍然倒着看。看了K感觉是DP或者点分，但是没思路，跳过，看了J仍然没思路。shb看前面几题也差不多。此时看榜发现E和F有人过了，于是我看了F，发现是简单DP，于是上机写，但是最后减去不合法方案时我直接减去了n/w+1，没有和h+1取min，导致WA了一次，而且看了10min才发现，值得检讨。shb同时发现E是一个裸的FFT，于是上机写并通过。之后继续跟榜我看了I题，shb则去看B和C。立刻发现I只有nlogn对距离要求，于是上机写并通过，换shb写C题，同时我看D。D我发现只要二分答案再树形DP即可，向shb确认了子树背包合并总复杂度是n^2^，于是C通过之后就开始写，并通过。然后我们讨论了G和J题，都没什么很好的想法。后来shb看了K发现点分+维护凸壳即可，于是上机开始写，期间我大概想出了J的做法，求出每个点第一次被黑色覆盖和最后一次被白色覆盖的时间作为事件，然后扫一下这些事件即可。用set维护每行、每列没有被覆盖的点，然后正着扫一次，再倒着一次即可求第一次和最后一次覆盖的时间。于是shb在K题WA了之后，就下机我来写J，然而写完得到了MLE，于是在shb建议下改成了用vector开set，而不是静态开2000000个set，得到了WA。然后shb继续调试K，我打印看了代码后发现了一个比较大的bug，居然能过样例。改了之后通过。之后shb在写了对拍之后过了K。

总结:今天F题的低级失误以后要避免。另外空的set貌似内存比较大？以后要注意

== shb ==
流水账：出门看到E是个FFT，台湾人竟然8分钟就过了，我决定把榜带的更歪一点，在sm学长改完签到题F以后我上去写，写完就过了。然后看别的题，感觉都不太会做？看到C题N只有15，估计是个傻逼状压，推了一下感觉挺简单的，想了一下转移的复杂度，我感觉是应该是可能接受的级别（我以为是2^N^的几倍，但其实是3^N^），上机写了个枚举子集试了一下，发现只有10^7^左右，感觉能过，写完发现过不了样例，打印换sm学长写D，发现输出有问题，改了还是错，仔细看了下题发现矩形长宽并不能交换，改了就过了。之后讨论了一波B，sm感觉暴力就行，我想了一下感觉科学，就甩锅给他，结果一会儿就写完1A了，太强了。之后感觉G和J没什么思路，K是个点分，想想没什么事干，就我来写，同时sm觉得J有思路了，而我点分写完喜获WA5，于是我看代码，换学长写J。我看了很久，感觉没什么问题，在4小时30分钟时学长过了J，我上机对拍，然后发现我凸壳的单调栈完全是错的，改了就过了，十分开心。。

总结：感觉今天罚时有点大，以后交题要注意调试信息等东西。还是要提高智商，感觉H十分有趣。

== 补题 ==

A []

G []

H []

lsmll

流水账：仍然倒着看。看了K感觉是DP或者点分，但是没思路，跳过，看了J仍然没思路。shb看前面几题也差不多。此时看榜发现E和F有人过了，于是我看了F，发现是简单DP，于是上机写，但是最后减去不合法方案时我直接减去了n/w+1，没有和h+1取min，导致WA了一次，而且看了10min才发现，值得检讨。shb同时发现E是一个裸的FFT，于是上机写并通过。之后继续跟榜我看了I题，shb则去看B和C。立刻发现I只有nlogn对距离要求，于是上机写并通过，换shb写C题，同时我看D。D我发现只要二分答案再树形DP即可，向shb确认了子树背包合并总复杂度是n²，于是C通过之后就开始写，并通过。然后我们讨论了G和J题，都没什么很好的想法。后来shb看了K发现点分+维护凸壳即可，于是上机开始写，期间我大概想出了J的做法，求出每个点第一次被黑色覆盖和最后一次被白色覆盖的时间作为事件，然后扫一下这些事件即可。用set维护每行、每列没有被覆盖的点，然后正着扫一次，再倒着一次即可求第一次和最后一次覆盖的时间。于是shb在K题WA了之后，就下机我来写J，然而写完得到了MLE，于是在shb建议下改成了用vector开set，而不是静态开2000000个set，得到了WA。然后shb继续调试K，我打印看了代码后发现了一个比较大的bug，居然能过样例。改了之后通过。之后shb在写了对拍之后过了K。

总结:今天F题的低级失误以后要避免。另外空的set貌似内存比较大？以后要注意

shb

流水账：出门看到E是个FFT，台湾人竟然8分钟就过了，我决定把榜带的更歪一点，在sm学长改完签到题F以后我上去写，写完就过了。然后看别的题，感觉都不太会做？看到C题N只有15，估计是个傻逼状压，推了一下感觉挺简单的，想了一下转移的复杂度，我感觉是应该是可能接受的级别（我以为是2^N的几倍，但其实是3^N），上机写了个枚举子集试了一下，发现只有10⁷左右，感觉能过，写完发现过不了样例，打印换sm学长写D，发现输出有问题，改了还是错，仔细看了下题发现矩形长宽并不能交换，改了就过了。之后讨论了一波B，sm感觉暴力就行，我想了一下感觉科学，就甩锅给他，结果一会儿就写完1A了，太强了。之后感觉G和J没什么思路，K是个点分，想想没什么事干，就我来写，同时sm觉得J有思路了，而我点分写完喜获WA5，于是我看代码，换学长写J。我看了很久，感觉没什么问题，在4小时30分钟时学长过了J，我上机对拍，然后发现我凸壳的单调栈完全是错的，改了就过了，十分开心。。

总结：感觉今天罚时有点大，以后交题要注意调试信息等东西。还是要提高智商，感觉H十分有趣。

补题

A []

G []

H []