2017-C07-team3

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(Screenshot from 2017-08-25 22-56-47.png)]]
= 流水账 =
      今天大爆炸。

      A题lzw学长稳健的签掉了，然后reku看看D感觉时限20s，不是随便写，然而最后交了一发4000*4000*log(16000000)的都没过，感觉很绝望。然后lzw学长过来把map改成了手写的hash，终于搞了过去，这个时候已经一个多小时了。然后Johann学长去写B，因为一些小问题，也看了一会。lzw学长写C，也因为一些小问题，看了一会，不过所幸最后这两个题都过掉了。

    然后开始看G，Johann学长告诉reku和lzw题意，然后大家讨论了一个小时，还很迷惑为什么大家都会这个题目。然后讨论出了一个细节很多，正确性也很迷的做法，reku开始上去写，WA3、WA6，然后Johann学长换了个写法，WA6。

    最后两分钟让lzw学长重新读了一下题，果然读错题了，喜获垫底，打出GG。
= 总结 =

== reku ==
    今天D的锅是我的，主要是实现上面太过草率，基本没怎么考虑常数。还是写题的习惯不太好。

    然后G题，我觉得我作为队长，应该了解到自己队伍的实力还没有那么差，很多人都会的题目，我们理论上来说也应该很快就会。但是讨论了一个小时，此时就应该意识到题目读错了，应该去重新读题了。然而就一直觉得这个题意是可做的，我们可能陷入的解题误区之类的。感觉非常糟糕，读错题在所难免，一定要及时纠正，不仅要算样例，如果感觉题目难度和现场过题情况差距过大的时候，就一定要重新读题了！

    这几天都有读错题和卡题的情况发生，一定要调整好状态。
== lzw4896s ==
    G题看错题, H，I都没有想出来, 好菜菜。。。
== Johann ==
    今天大爆炸主要是我的锅。感觉这两天读题出了三四次问题。今天先在B题对题意有一个错误的推断，导致错了一个细节，调试了一段时间。G题则因为读错了题，告诉了队友错误的题意，整场奋战，原地爆炸，打出GG。以后看题、解释题意，都要基于文本，耐心一些。

= 教训 =
    读题要基于文本！文本！
= 题解 =
  * H : 先tarjan缩个点，然后看每个SCC中，是不是一个仅由2号边构成的树，如果不是的话，那就说明有环。然后把所有的SCC拓扑排序，在一个SCC中，可以通过两次dfs来更新后继的值

  * I : 令xbb=a，ybb=b。根据gcd(a,b)的大小分类讨论。若gcd的值很小。可以采取连接对角线，再取第三个点(x,y)，使得|ax-by|=t的值尽量小。可以使用扩展欧几里得算法。若gcd的值很大，可以构造一个V型的凹四边形，可以证明结果非常清真。Orz ZJL, JSB。

  * J : 考虑圆所在位置的圆心。显然对于一个固定的x，不同y得到的答案是单峰的。我们记每一个横坐标x下能获得的最大面积交为s[x]。可以猜想，s[x]关于x也是单峰的。（证明待补）那么我们可以先后对x和y三分，然后求面积交（jsb：“YuanJiao”）。求面积交的方法可以这样操作。对多边形的每条边与圆求交。将所有的交点按逆时针排列。将这些交点和多边形的顶点与圆心相连。这样得到一些扇形和三角形，面积相加即可。

  * E : 按照给出的模式，递归下降进行语法分析就好了

流水账

今天大爆炸。

A题lzw学长稳健的签掉了，然后reku看看D感觉时限20s，不是随便写，然而最后交了一发4000*4000*log(16000000)的都没过，感觉很绝望。然后lzw学长过来把map改成了手写的hash，终于搞了过去，这个时候已经一个多小时了。然后Johann学长去写B，因为一些小问题，也看了一会。lzw学长写C，也因为一些小问题，看了一会，不过所幸最后这两个题都过掉了。

然后开始看G，Johann学长告诉reku和lzw题意，然后大家讨论了一个小时，还很迷惑为什么大家都会这个题目。然后讨论出了一个细节很多，正确性也很迷的做法，reku开始上去写，WA3、WA6，然后Johann学长换了个写法，WA6。

最后两分钟让lzw学长重新读了一下题，果然读错题了，喜获垫底，打出GG。

总结

reku

今天D的锅是我的，主要是实现上面太过草率，基本没怎么考虑常数。还是写题的习惯不太好。

然后G题，我觉得我作为队长，应该了解到自己队伍的实力还没有那么差，很多人都会的题目，我们理论上来说也应该很快就会。但是讨论了一个小时，此时就应该意识到题目读错了，应该去重新读题了。然而就一直觉得这个题意是可做的，我们可能陷入的解题误区之类的。感觉非常糟糕，读错题在所难免，一定要及时纠正，不仅要算样例，如果感觉题目难度和现场过题情况差距过大的时候，就一定要重新读题了！

这几天都有读错题和卡题的情况发生，一定要调整好状态。

lzw4896s

G题看错题, H，I都没有想出来, 好菜菜。。。

Johann

今天大爆炸主要是我的锅。感觉这两天读题出了三四次问题。今天先在B题对题意有一个错误的推断，导致错了一个细节，调试了一段时间。G题则因为读错了题，告诉了队友错误的题意，整场奋战，原地爆炸，打出GG。以后看题、解释题意，都要基于文本，耐心一些。

教训

读题要基于文本！文本！

题解

H : 先tarjan缩个点，然后看每个SCC中，是不是一个仅由2号边构成的树，如果不是的话，那就说明有环。然后把所有的SCC拓扑排序，在一个SCC中，可以通过两次dfs来更新后继的值
I : 令xbb=a，ybb=b。根据gcd(a,b)的大小分类讨论。若gcd的值很小。可以采取连接对角线，再取第三个点(x,y)，使得|ax-by|=t的值尽量小。可以使用扩展欧几里得算法。若gcd的值很大，可以构造一个V型的凹四边形，可以证明结果非常清真。Orz ZJL, JSB。
J : 考虑圆所在位置的圆心。显然对于一个固定的x，不同y得到的答案是单峰的。我们记每一个横坐标x下能获得的最大面积交为s[x]。可以猜想，s[x]关于x也是单峰的。（证明待补）那么我们可以先后对x和y三分，然后求面积交（jsb：“YuanJiao”）。求面积交的方法可以这样操作。对多边形的每条边与圆求交。将所有的交点按逆时针排列。将这些交点和多边形的顶点与圆心相连。这样得到一些扇形和三角形，面积相加即可。
E : 按照给出的模式，递归下降进行语法分析就好了

附加文件

Screenshot from 2017-08-25 22-56-47.png by ruiker