2018-team8-E11

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(day11.png)]]

== 流水账 ==

zhhhplus: 今天踩了wyz，开心。今天开场，大家发现场上E题过得很多，cyw上机写一个O(n)的做法，看到数据大小只有1000我还有点虚，但是想了想觉得这个算法一点问题都没有……然后交上去结果WA9了？我决定cyw稍微改一下如果不A这题就换我来签了，然后询问了一下0的个数太多的时候会怎么样，结果果然错在这里，简单改了一下过了，这个罚时有一点冤。然后lsy跟我讲了B题题意，我感觉随便在卷面上手算一下情况然后枚举一下就行了，然后花了十几分钟把全部情况算了一下，之后去写了一个暴力枚举，一边害怕打错数字一边1A了。此时我和lsy想C题，我在鼓捣强连通分量的时候lsy突然告诉我正向边反向边分别做一遍dfs就没了，感觉巨有道理，很快就A掉了C题（在我们还没想出来的时候cyw构造了一个D的方案，上去写了一遍，还没过样例的时候换lsy写C题），A掉C之后过了2分钟就交了一发D题，C题AC但是D题WA4，接着发现D题打错了变量名，改掉之后就A了。此时A题全榜过的人很多，我这边推了一个每个x最多交log级别的圆的结论，尝试离散化暴力一下，发现不行，觉得可以写线段树维护一下区间里的圆（中间有想过CDQ分治，但是不行），但是可能有点难写。此时cyw读了L题，并且马上给出了树链剖分和染色的做法，后面发现染色似乎还不够的时候，lsy提出排一下序就行的观点，cyw写树链剖分去，我们这边接着做A题，但其实想不出什么比线段树维护set更优秀的做法了？cyw一发A掉了L之后，我这边A题又出了一个nlog^2^n的做法，觉得常数比较小，但是复杂度没有线段树优秀，并且解释起来也挺麻烦的，觉得线段树跟暴力没太大差别，算法不可能出问题，就让cyw写了一下线段树维护set。然后我和lsy开F题，怎么感觉都是个sb贪心，细节可能挺多的，cyw写好线段树之后就让lsy去写F题了，cyw这边线段树WA在了很前面，随便测了一个数据发现删圆出了点问题，接着我也看了一遍这份线段树代码，也觉得很对，死活调不出错（机器用来写F题），最后40分钟的时候我问了cyw，觉得线段树调不调得出来，cyw回答不知道WA的数据就调不出来，我果断跟cyw说放弃掉线段树，换我另一个做法，花了几分钟来解释之后，lsy写好了F题正在调，我让lsy先交一发F题，返回RE2，然后换cyw上去写A题，花十几分钟rush出来了一个代码（中间我看着他写，以免出什么交流上的锅，rush完之后就剩下15分钟了），本地测了一下结果交上去WA1，我马上让cyw用custom test一下，发现和本地跑出来的结果不一样，过了一会儿之后我就发现是本地测试的那份代码是A.cpp而不是重写的AA.cpp……接着发现是个小地方写错了（从原代码复制过来的判断距离函数），改了一下之后WA在了15，接着我觉得两个erase操作有点虚，改成了queue+erase之后交了一发WA2，cyw马上发现一个错误点（先break掉了之类的），改掉（在我提议上个goto）之后WA15。然后我又马上发现MAX_LOG开小了，改掉这个之后在还剩下4分钟的时候AC了，激动地欢呼了起来。F题显然已经rush不及了。

== 总结 ==

zhhhplus: 今天踩了wyz，开心。L题很优秀，一下子就1A了，但是A题出得有点晚，其实应该直接写那个nlog^2^n的做法，代码也短，也没有出奇怪的问题，实际上时间如果足够充裕，我们也不会选择非常冒失地一下子交n发罚时来debug的策略，而F题也能空出很多时间来写。

== 补题 ==

 * F: LIN452
 * J: Pepcy_Ch

流水账

zhhhplus: 今天踩了wyz，开心。今天开场，大家发现场上E题过得很多，cyw上机写一个O(n)的做法，看到数据大小只有1000我还有点虚，但是想了想觉得这个算法一点问题都没有……然后交上去结果WA9了？我决定cyw稍微改一下如果不A这题就换我来签了，然后询问了一下0的个数太多的时候会怎么样，结果果然错在这里，简单改了一下过了，这个罚时有一点冤。然后lsy跟我讲了B题题意，我感觉随便在卷面上手算一下情况然后枚举一下就行了，然后花了十几分钟把全部情况算了一下，之后去写了一个暴力枚举，一边害怕打错数字一边1A了。此时我和lsy想C题，我在鼓捣强连通分量的时候lsy突然告诉我正向边反向边分别做一遍dfs就没了，感觉巨有道理，很快就A掉了C题（在我们还没想出来的时候cyw构造了一个D的方案，上去写了一遍，还没过样例的时候换lsy写C题），A掉C之后过了2分钟就交了一发D题，C题AC但是D题WA4，接着发现D题打错了变量名，改掉之后就A了。此时A题全榜过的人很多，我这边推了一个每个x最多交log级别的圆的结论，尝试离散化暴力一下，发现不行，觉得可以写线段树维护一下区间里的圆（中间有想过CDQ分治，但是不行），但是可能有点难写。此时cyw读了L题，并且马上给出了树链剖分和染色的做法，后面发现染色似乎还不够的时候，lsy提出排一下序就行的观点，cyw写树链剖分去，我们这边接着做A题，但其实想不出什么比线段树维护set更优秀的做法了？cyw一发A掉了L之后，我这边A题又出了一个nlog2n的做法，觉得常数比较小，但是复杂度没有线段树优秀，并且解释起来也挺麻烦的，觉得线段树跟暴力没太大差别，算法不可能出问题，就让cyw写了一下线段树维护set。然后我和lsy开F题，怎么感觉都是个sb贪心，细节可能挺多的，cyw写好线段树之后就让lsy去写F题了，cyw这边线段树WA在了很前面，随便测了一个数据发现删圆出了点问题，接着我也看了一遍这份线段树代码，也觉得很对，死活调不出错（机器用来写F题），最后40分钟的时候我问了cyw，觉得线段树调不调得出来，cyw回答不知道WA的数据就调不出来，我果断跟cyw说放弃掉线段树，换我另一个做法，花了几分钟来解释之后，lsy写好了F题正在调，我让lsy先交一发F题，返回RE2，然后换cyw上去写A题，花十几分钟rush出来了一个代码（中间我看着他写，以免出什么交流上的锅，rush完之后就剩下15分钟了），本地测了一下结果交上去WA1，我马上让cyw用custom test一下，发现和本地跑出来的结果不一样，过了一会儿之后我就发现是本地测试的那份代码是A.cpp而不是重写的AA.cpp……接着发现是个小地方写错了（从原代码复制过来的判断距离函数），改了一下之后WA在了15，接着我觉得两个erase操作有点虚，改成了queue+erase之后交了一发WA2，cyw马上发现一个错误点（先break掉了之类的），改掉（在我提议上个goto）之后WA15。然后我又马上发现MAX_LOG开小了，改掉这个之后在还剩下4分钟的时候AC了，激动地欢呼了起来。F题显然已经rush不及了。

总结

zhhhplus: 今天踩了wyz，开心。L题很优秀，一下子就1A了，但是A题出得有点晚，其实应该直接写那个nlog2n的做法，代码也短，也没有出奇怪的问题，实际上时间如果足够充裕，我们也不会选择非常冒失地一下子交n发罚时来debug的策略，而F题也能空出很多时间来写。

补题

  • F: LIN452
  • J: Pepcy_Ch
附加文件