2018-team8-E09

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(day9.png)]]

== 流水账 ==

zhhhplus: 今天又踩了wyz！心情舒畅。开场的时候看到一大片人过了A题，然后lsy跟我讲了题意之后我觉得是个CFdiv2A题的水平，就上去快速签到了。1A之后cyw发现K题可以签了，就上来写K题，也是1A。lsy告诉我J题是个暴力搜索，我一听有点虚，然后反正机子没有人占着，就让lsy去写个爆搜看看。WA了一发之后才过，好像是少判断了什么条件。此时看榜过F题的人挺多的，而cyw似乎已经出解法了，上去写F题。我和lsy看了一下榜发现B题可做，以及I题可做，都看了一下感觉不太到做法，B题我吸取了昨天的教训，在想了一小会儿线性规划之后觉得不可能是这个解法，lsy问了我一下线性规划的板子。在cyw WA了两次F题之后我突然发现B题是个sb实数背包，上去写了写就过掉了（中间稍微改了改写法，以求更稳，然后虽然没考虑到a_i_和b_i_可能为0也过掉了）。接着除了cyw的F题，大概可做的就只有I题和E题，E题没什么思路，I题猜测和LIS做法差不多，接着在我想E题的时候lsy得到了I题的做法，也打算上机写，在cyw调完F题代码之后上机写了I题，非常稳地1A了。此时我看了一眼时间，发现还2.5小时，觉得必须再出一个题，比如E题，然后开始考虑E题的做法，另外可做的可能就只有D题，cyw想了想E题感觉不太会之后去读了一下D题，我们发现D题是个看上去有点烦的几何题，cyw不太会算里面的一些东西，感觉了一下两个多小时也可能莽不出来，我提出用蒙特卡洛随便试试，cyw去坐到机子前，我和lsy接着想B题。直到最后一个小时才发现E题我一开始提出的划分做法不是指数级复杂度的，我还发现了对每个结点出发的构造方法，稍微结合一下就得到了解法，cyw那边几何题可能写不出来，于是和cyw讲了一下划分的方法，打算让cyw快速写个分辨点出来，然后lsy来写构造的必胜环。但是到结束没有写完。不过这个划分方法可能有一点细节上的问题，尽管随机化了我方出拳的方案，但是如果对方的方案是个大环，但是分支节点只有其中一个，可能会出现随机不出来那个划分的情况，对于这点可能需要在每次划分的时候枚举三种出拳方案，以便不要错过能够划分的时机。半场的时候我以为在场的各队最高至少能到8题，结果一直到最后都是6题。

== 总结 ==

zhhhplus：今天除了F题罚时比较糟糕，其余题目都还行，感觉没有特别奇怪的卡题和特别冒失的提交。至于今天踩wyz主要是wyz他们打炸了，最后两个半小时都没有把D题和E题写出来可能也不太应该？赛后想想任何一题可能都能在两个半小时里面写出来的。

== 补题 ==

 * D: Pepcy_Ch
 * E:

流水账

zhhhplus: 今天又踩了wyz！心情舒畅。开场的时候看到一大片人过了A题，然后lsy跟我讲了题意之后我觉得是个CFdiv2A题的水平，就上去快速签到了。1A之后cyw发现K题可以签了，就上来写K题，也是1A。lsy告诉我J题是个暴力搜索，我一听有点虚，然后反正机子没有人占着，就让lsy去写个爆搜看看。WA了一发之后才过，好像是少判断了什么条件。此时看榜过F题的人挺多的，而cyw似乎已经出解法了，上去写F题。我和lsy看了一下榜发现B题可做，以及I题可做，都看了一下感觉不太到做法，B题我吸取了昨天的教训，在想了一小会儿线性规划之后觉得不可能是这个解法，lsy问了我一下线性规划的板子。在cyw WA了两次F题之后我突然发现B题是个sb实数背包，上去写了写就过掉了（中间稍微改了改写法，以求更稳，然后虽然没考虑到a_i_和b_i_可能为0也过掉了）。接着除了cyw的F题，大概可做的就只有I题和E题，E题没什么思路，I题猜测和LIS做法差不多，接着在我想E题的时候lsy得到了I题的做法，也打算上机写，在cyw调完F题代码之后上机写了I题，非常稳地1A了。此时我看了一眼时间，发现还2.5小时，觉得必须再出一个题，比如E题，然后开始考虑E题的做法，另外可做的可能就只有D题，cyw想了想E题感觉不太会之后去读了一下D题，我们发现D题是个看上去有点烦的几何题，cyw不太会算里面的一些东西，感觉了一下两个多小时也可能莽不出来，我提出用蒙特卡洛随便试试，cyw去坐到机子前，我和lsy接着想B题。直到最后一个小时才发现E题我一开始提出的划分做法不是指数级复杂度的，我还发现了对每个结点出发的构造方法，稍微结合一下就得到了解法，cyw那边几何题可能写不出来，于是和cyw讲了一下划分的方法，打算让cyw快速写个分辨点出来，然后lsy来写构造的必胜环。但是到结束没有写完。不过这个划分方法可能有一点细节上的问题，尽管随机化了我方出拳的方案，但是如果对方的方案是个大环，但是分支节点只有其中一个，可能会出现随机不出来那个划分的情况，对于这点可能需要在每次划分的时候枚举三种出拳方案，以便不要错过能够划分的时机。半场的时候我以为在场的各队最高至少能到8题，结果一直到最后都是6题。

总结

zhhhplus：今天除了F题罚时比较糟糕，其余题目都还行，感觉没有特别奇怪的卡题和特别冒失的提交。至于今天踩wyz主要是wyz他们打炸了，最后两个半小时都没有把D题和E题写出来可能也不太应该？赛后想想任何一题可能都能在两个半小时里面写出来的。

补题

  • D: Pepcy_Ch
  • E:
附加文件