2017-C08-team1

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(team1c8.jpg)]]

== lsmll ==
流水账：仍然倒着看。今天jsb学长有事稍微迟到了一会。看了J和I觉得应该都是有一定难度的题。看榜发现很多过了G，打开一看想了一会发现是水题，于是上机写了并通过。之后shb在WA了一次后过了D题。然后我们决定跟榜做H和J两题，H题shb提出先按a排序，然后每次一定剪右边的一段，于是我马上想到了可以用线段树，每种植物高度写成a(x-c)+b，然后就能维护了，此时他们还在讨论J题细节，于是我先上机去写H。后来发现sigma(a*c)可能爆long long，于是使用了`__`int128，不过赛后知道三队并不是这样做的，而且我的线段树做法内存很卡（时间我估计也很卡），可能不是标算。写完之后WA了，于是和J题交替上机，最后J题先过。我看了几次代码没看出什么问题，于是J过了后，我决定写对拍，后来发现是在线段树上二分的时候用到了左儿子信息，但没有先对其标记下传，修改后通过。同时jsb和shb大概讨论出了E题做法。于是后来jsb上机去写，我和shb讨论A题和B题，B他提出了一种做法，但我感觉不太靠谱，然后我们转而研究A，发现可以倍增，我给shb指出了实现上的一些细节，交给他写，我和jsb再研究B题。最后shb先写了他很简单的B题做法，没过，后来转而写A并最终通过。后来B题我们对shb做法提出了一些改进，然而来不及写了。

总结：感觉我们今天J和H都卡的挺伤的，不然最后可能能搞出B。因为平时的区间修改线段树都不需要用到左儿子信息，所以不用对左儿子标记下传，然而这个在线段树上二分就需要在父亲的调用中用到左儿子信息以决定往哪个儿子走。以后写代码时要仔细考虑，不能按照经验想当然。毕竟写对拍比较费时间。

== shb ==
流水账：开场蒋爷爷不在，我和sm双开。出门从头开始看。感觉A有可能是数论题，B看起来很不可做，C看起来是SCC上搞个必经点树之类的东西？D感觉也不太会。。然后我看到有好多人过了G，催sm学长看一看，他一下子就秒了。之后有人过了D，我们俩讨论了一下，感觉拓扑排序搞一搞就行了。写完交了一发，结果WA了。想了想感觉做法很科学，再读了一次发现要sort一下答案。然后jsb来了。不少人过了J，我们讨论了一下，感觉枚举直角顶点，然后极角排序，扫描二分就行了。但是蒋爷爷写的并不是很顺利，过了样例以后并过不了我的数据。这段时间我和sm学长讨论H，很快就有了做法，但是好像会爆LL。之后一段时间就是交替写J和H，但是两题都WA了。修了很久，终于在接近三个小时的时候都过了。我和jsb讨论了一下E，我感觉也许可以分治，但是并不会做，蒋爷爷想了一下感觉会做了，于是就上机写并过了。这段时间我和sm讨论了A，感觉可以倍增，决定由我来写。之后我先写了一个B的傻逼做法，果然WA2。。于是写A，比起前几次写题还算顺利，但是TLE18。后来经过强力的常数优化，本地运行时间从3.7s降到了0.4s（orz jsb），果然过了。最后我们试图修一下B，但是不太会维护我们的做法，于是就gg了。

总结：今天做题不是很顺利，H和J卡的有点久，有点拖慢后期的节奏。感觉我们对于极角排序这种比较常见的操作应该做点准备，不该现场想各种corner case。我可能还是需要提高智商。。感觉我们之间的交流和配合比刚组队时要好一些了，继续加油。

== jsb ==
流水账：最近在新生报道，有很多杂事，就晚到了一会儿。我们队过了签到的D和G后看了看榜，发现有个队15min过J了。我们讨论了一下，只要枚举直角顶点，然后极角排序+二分即可。思路比较清晰，我就上机去写了。由于几何能力薄弱，我的“360°的极角排序”卡了很久（堡学长给我造的数据很强前期一直过不去）；最后感觉万无一失交上去的时候WA了，后来发现倍长了数组但是没有开够：很是不应该。期间颜学长和我交替上机，最后他通过对拍发现了错误并过了H。后来我和堡学长讨论E，开始效率是O(N*logN*M^2^)(N=10W,M=10)的，后来感觉能优化掉一个M，但是细节繁琐且可能要卡内存。于是我打算先精细地实现前者；WA了一发之后改了个傻逼错误就神奇地过了。后期，堡学长单机做A，我和ismll学长讨论B。堡堡的程序TLE了，我尝试加了个以前经常用到的优化就过了。然而我们最后并没有完全想出B，最后的乱搞也没时间写了。

总结：感觉我们今天J和H都卡的挺伤的，不然最后可能能搞出B。还有感觉智商不够，所以跟榜能力不行。

== 补题 ==

B []

C []

F []

I []

lsmll

流水账：仍然倒着看。今天jsb学长有事稍微迟到了一会。看了J和I觉得应该都是有一定难度的题。看榜发现很多过了G，打开一看想了一会发现是水题，于是上机写了并通过。之后shb在WA了一次后过了D题。然后我们决定跟榜做H和J两题，H题shb提出先按a排序，然后每次一定剪右边的一段，于是我马上想到了可以用线段树，每种植物高度写成a(x-c)+b，然后就能维护了，此时他们还在讨论J题细节，于是我先上机去写H。后来发现sigma(a*c)可能爆long long，于是使用了__int128，不过赛后知道三队并不是这样做的，而且我的线段树做法内存很卡（时间我估计也很卡），可能不是标算。写完之后WA了，于是和J题交替上机，最后J题先过。我看了几次代码没看出什么问题，于是J过了后，我决定写对拍，后来发现是在线段树上二分的时候用到了左儿子信息，但没有先对其标记下传，修改后通过。同时jsb和shb大概讨论出了E题做法。于是后来jsb上机去写，我和shb讨论A题和B题，B他提出了一种做法，但我感觉不太靠谱，然后我们转而研究A，发现可以倍增，我给shb指出了实现上的一些细节，交给他写，我和jsb再研究B题。最后shb先写了他很简单的B题做法，没过，后来转而写A并最终通过。后来B题我们对shb做法提出了一些改进，然而来不及写了。

总结：感觉我们今天J和H都卡的挺伤的，不然最后可能能搞出B。因为平时的区间修改线段树都不需要用到左儿子信息，所以不用对左儿子标记下传，然而这个在线段树上二分就需要在父亲的调用中用到左儿子信息以决定往哪个儿子走。以后写代码时要仔细考虑，不能按照经验想当然。毕竟写对拍比较费时间。

shb

流水账：开场蒋爷爷不在，我和sm双开。出门从头开始看。感觉A有可能是数论题，B看起来很不可做，C看起来是SCC上搞个必经点树之类的东西？D感觉也不太会。。然后我看到有好多人过了G，催sm学长看一看，他一下子就秒了。之后有人过了D，我们俩讨论了一下，感觉拓扑排序搞一搞就行了。写完交了一发，结果WA了。想了想感觉做法很科学，再读了一次发现要sort一下答案。然后jsb来了。不少人过了J，我们讨论了一下，感觉枚举直角顶点，然后极角排序，扫描二分就行了。但是蒋爷爷写的并不是很顺利，过了样例以后并过不了我的数据。这段时间我和sm学长讨论H，很快就有了做法，但是好像会爆LL。之后一段时间就是交替写J和H，但是两题都WA了。修了很久，终于在接近三个小时的时候都过了。我和jsb讨论了一下E，我感觉也许可以分治，但是并不会做，蒋爷爷想了一下感觉会做了，于是就上机写并过了。这段时间我和sm讨论了A，感觉可以倍增，决定由我来写。之后我先写了一个B的傻逼做法，果然WA2。。于是写A，比起前几次写题还算顺利，但是TLE18。后来经过强力的常数优化，本地运行时间从3.7s降到了0.4s（orz jsb），果然过了。最后我们试图修一下B，但是不太会维护我们的做法，于是就gg了。

总结：今天做题不是很顺利，H和J卡的有点久，有点拖慢后期的节奏。感觉我们对于极角排序这种比较常见的操作应该做点准备，不该现场想各种corner case。我可能还是需要提高智商。。感觉我们之间的交流和配合比刚组队时要好一些了，继续加油。

jsb

流水账：最近在新生报道，有很多杂事，就晚到了一会儿。我们队过了签到的D和G后看了看榜，发现有个队15min过J了。我们讨论了一下，只要枚举直角顶点，然后极角排序+二分即可。思路比较清晰，我就上机去写了。由于几何能力薄弱，我的“360°的极角排序”卡了很久（堡学长给我造的数据很强前期一直过不去）；最后感觉万无一失交上去的时候WA了，后来发现倍长了数组但是没有开够：很是不应该。期间颜学长和我交替上机，最后他通过对拍发现了错误并过了H。后来我和堡学长讨论E，开始效率是O(N*logN*M2)(N=10W,M=10)的，后来感觉能优化掉一个M，但是细节繁琐且可能要卡内存。于是我打算先精细地实现前者；WA了一发之后改了个傻逼错误就神奇地过了。后期，堡学长单机做A，我和ismll学长讨论B。堡堡的程序TLE了，我尝试加了个以前经常用到的优化就过了。然而我们最后并没有完全想出B，最后的乱搞也没时间写了。

总结：感觉我们今天J和H都卡的挺伤的，不然最后可能能搞出B。还有感觉智商不够，所以跟榜能力不行。

补题

B []

C []

F []

I []

附加文件