2018-team8-E23

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(gululu.png)]]

== 流水账 ==

zhhhplus: 一开场我看了一下K题，发现是个三角形交圆的题，顺口问了一句cyw有没有板子，据说没有？随便列了7种K题的分类讨论，非常自闭，于是决定先放着。接着cyw告诉我E题好像是之前做过的原题，和我描述了一下题意，基本就是我之前补掉了的博弈DP，然后我去写了一下打了一下表，找了一下规律，写了一下交了过了。接着回头找别的题做，然后看到了G题已经被人过了，然后我就尝试找了一下三维凸包的板子，放弃了红书是因为好像少一个判断共面的函数不好处理？因为这东西行数还蛮多的而且还要自己处理一些东西所以有点自闭。之后发现大家纷纷过了K题？我就重新翻了一下板子，找到了多边形和圆的交这个东西，虽然有点杀鸡用牛刀，但是总是比我自己手写的靠谱的，于是我上去敲板子，lsy和cyw开别的题，然后cyw据说有了B题解法，lsy似乎开出了F题（似乎是一个我看了一下表示大概是拆成链DP的DP题？（迅速甩锅给DP选手lsy）），过了很长时间终于抄完了板子，改了几个错误（得到启示：红书跟在板子后面的Hint非常重要，Hint是好文明，HDU几何板子是坏文明），然后一发过了K题，lsy继续写F题，不久之后F题就过了，cyw似乎已经开始尝试Java写B题了？接着我们发现I题似乎可以做，我感受了一小段时间（第一步是随口说这玩意儿像割点，我觉得我随口说的习惯需要改一改），觉得应该二分图做一下匹配，如果能两次匹配成满的匹配就输出Yes，然后跟lsy讲了一下做法，觉得做法大科学。但是cyw在写B题，lsy在开D题（此前cyw和我提起过D题的做法，好像是什么倍增什么SAM的记不太清，但是他们似乎遇到了一点问题），但是我当时感觉这个东西可能得像昨天的网络流染色题那样做，暂时不太会，决定留给lsy或cyw来写，看到机器暂时是空的，于是决定强行打一发G题，在斟酌了一下之后觉得HDU有same()函数，决定抄HDU，然后刷新了我一场中打的代码行数的记录……之后基本就是在帮忙调错，抄板子，改代码的过程中度过了，还剩一个小时多一点的时候心态有点爆炸，对HDU充满了不信任（“相信自己的卡牌”），因为大家手里还塞着D题I题和B题，决定把G题放弃掉。然后我们让cyw重新读一下自己I题的代码（因为再想了一下，结论（建图）绝对没有错），接着发现是n和m打反了，于是我们把cyw打了一顿（雾）之后过了I题。接着就是lsy调D题和cyw调B题了，B题改了一点小错之后觉得好像改不出什么bug了，交上去试了一下结果获得了WA？然后我来听cyw讲他B题的做法，发现cyw没有把n*p给计算进去，让cyw改了一发之后T16，cyw此时提出要换C++高精度板子，我按住了他，表示这个点T掉了一定是复杂度在哪里爆炸了，让他好好想想，然后cyw思考了一会儿之后决定记忆化求阶乘（emmmmmmmm），然后改了一发T5，我一脸懵，表示让我康康这个代码，发现阶乘是用BigInteger来存的，表示改成int看一下吧，然后T18，我表示你再想想你的复杂度有没有问题，然后又过了一段时间之后cyw表示是有问题的，也能改了，上去写了个欧拉函数（cyw：是欧拉定理！），把复杂度又降下来了，交上去才过了。还有20+分钟，lsy在机器上写D题，WA8收尾。

== 总结 ==

zhhhplus: 我再抄HDU的几何板子我就是狗！得合理感受一下开题量呢（这次还蛮合理的，就是H题可能比G题更加可能写出来？感觉明明cyw读了题，但是就是没发现它的签到本质呢）。

Pepcy_Ch: 想错了 H 的难点（跑次 dij 就行倒是想到了，但迷之卡在了边权的改变上），导致痛失一道水题。

== 补题 ==

 * D: LIN452
 * G: Pepcy_Ch
 * H: Pepcy_Ch

流水账

zhhhplus: 一开场我看了一下K题，发现是个三角形交圆的题，顺口问了一句cyw有没有板子，据说没有？随便列了7种K题的分类讨论，非常自闭，于是决定先放着。接着cyw告诉我E题好像是之前做过的原题，和我描述了一下题意，基本就是我之前补掉了的博弈DP，然后我去写了一下打了一下表，找了一下规律，写了一下交了过了。接着回头找别的题做，然后看到了G题已经被人过了，然后我就尝试找了一下三维凸包的板子，放弃了红书是因为好像少一个判断共面的函数不好处理？因为这东西行数还蛮多的而且还要自己处理一些东西所以有点自闭。之后发现大家纷纷过了K题？我就重新翻了一下板子，找到了多边形和圆的交这个东西，虽然有点杀鸡用牛刀，但是总是比我自己手写的靠谱的，于是我上去敲板子，lsy和cyw开别的题，然后cyw据说有了B题解法，lsy似乎开出了F题（似乎是一个我看了一下表示大概是拆成链DP的DP题？（迅速甩锅给DP选手lsy）），过了很长时间终于抄完了板子，改了几个错误（得到启示：红书跟在板子后面的Hint非常重要，Hint是好文明，HDU几何板子是坏文明），然后一发过了K题，lsy继续写F题，不久之后F题就过了，cyw似乎已经开始尝试Java写B题了？接着我们发现I题似乎可以做，我感受了一小段时间（第一步是随口说这玩意儿像割点，我觉得我随口说的习惯需要改一改），觉得应该二分图做一下匹配，如果能两次匹配成满的匹配就输出Yes，然后跟lsy讲了一下做法，觉得做法大科学。但是cyw在写B题，lsy在开D题（此前cyw和我提起过D题的做法，好像是什么倍增什么SAM的记不太清，但是他们似乎遇到了一点问题），但是我当时感觉这个东西可能得像昨天的网络流染色题那样做，暂时不太会，决定留给lsy或cyw来写，看到机器暂时是空的，于是决定强行打一发G题，在斟酌了一下之后觉得HDU有same()函数，决定抄HDU，然后刷新了我一场中打的代码行数的记录……之后基本就是在帮忙调错，抄板子，改代码的过程中度过了，还剩一个小时多一点的时候心态有点爆炸，对HDU充满了不信任（“相信自己的卡牌”），因为大家手里还塞着D题I题和B题，决定把G题放弃掉。然后我们让cyw重新读一下自己I题的代码（因为再想了一下，结论（建图）绝对没有错），接着发现是n和m打反了，于是我们把cyw打了一顿（雾）之后过了I题。接着就是lsy调D题和cyw调B题了，B题改了一点小错之后觉得好像改不出什么bug了，交上去试了一下结果获得了WA？然后我来听cyw讲他B题的做法，发现cyw没有把n*p给计算进去，让cyw改了一发之后T16，cyw此时提出要换C++高精度板子，我按住了他，表示这个点T掉了一定是复杂度在哪里爆炸了，让他好好想想，然后cyw思考了一会儿之后决定记忆化求阶乘（emmmmmmmm），然后改了一发T5，我一脸懵，表示让我康康这个代码，发现阶乘是用BigInteger来存的，表示改成int看一下吧，然后T18，我表示你再想想你的复杂度有没有问题，然后又过了一段时间之后cyw表示是有问题的，也能改了，上去写了个欧拉函数（cyw：是欧拉定理！），把复杂度又降下来了，交上去才过了。还有20+分钟，lsy在机器上写D题，WA8收尾。

总结

zhhhplus: 我再抄HDU的几何板子我就是狗！得合理感受一下开题量呢（这次还蛮合理的，就是H题可能比G题更加可能写出来？感觉明明cyw读了题，但是就是没发现它的签到本质呢）。

Pepcy_Ch: 想错了 H 的难点（跑次 dij 就行倒是想到了，但迷之卡在了边权的改变上），导致痛失一道水题。

补题

  • D: LIN452
  • G: Pepcy_Ch
  • H: Pepcy_Ch
附加文件