2017-C12-team7

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(DDay.jpg)]]

== zhhhplus ==

流水账：今天看快要迟到了，疯狂赶路，没有买早饭就到机房了（貌似每次我迟到全队就会爆炸得很惨？）。随后大家看到榜上A题和B题都在十几秒的时候被人过掉了，感觉很震惊，确信这俩队不是正常的队伍。大家开始各自看题，我看到榜上过K的人很多的样子，跟队友解释了一小会儿之后觉得讲解太麻烦了，题又简单，于是自己上去敲了，平稳地1A了这道题（'''K1y13'''）。大约此时chy和wyz也在讨论F题了，也和我讲了一下题意，我觉得ok啊，过了一会儿wyz就开始敲F题了。随后和chy一起讨论H题，一段时间之后想出了做法，chy表示是个背包，总之大家觉得可以这样做，在wyz过了F题（'''F1y40'''）之后就让chy上去敲H题了。然后wyz觉得优势很大，可以看一下全部题目，我则抱着A题和B题想，苦于不太会AC自动机的那套理论（今天打算学习一波），没什么思路，A题也万万没想到最后的解法是O(n²)的，于是就都没想出来。看到C题我觉得可能是个不太好写的lazy标记线段树，但是chy在过掉H题之后（'''H1y63'''）掏出了他的板子，表示用可持久化treap可以O(logn)做区间复制操作，然后我觉得可以，但是觉得极端情况要复制太多次，不太行，提出了可以倍增一下的操作，chy和wyz此时还不太明白为什么会进行很多次复制，我解释了一会儿，然后被暂时说服似乎不用，以为自己题目读错了，在缓过来之后斥责（并没有）了两位队友，chy觉得倍增不太理解，大家在找题开，一会儿之后我觉得机子空着不是办法，表示先把treap敲上去吧，打算自己上去敲板子，把智力活动交给两位，chy拦住了我，我表示倍增我写吧，于是他就去敲了板子，我则跟wyz讲了倍增的做法，在板子敲好之后完美甩锅给wyz。在此期间，我和他们分别想了一下A题和B题（wyz还想了I题）。一个半小时之后C题敲好了，大家兴奋地交了一发，获得了一发MLE，我觉得可持久化的操作new的点数太多了，大概可以减少一些，但是大家不太知道应该怎么做（并没有想到类似替罪羊树的直接拍平操作）（据说这样写能过，可能是拍平重建的姿势不对，赛后TLE了两发，还在修改中）（以及据说另外一种做法的删点操作很复杂，不太适合写）。于是就去想A题和B题，我们队的策略是把B题分配给chy，我和wyz则想A题，chy不负众望想出了一个AC自动机的DP，调了很久细节，在最后一小时的时候我和chy讲A题可以压缩，但是似乎没什么用，wyz猜测可能是个O(n²/64)的做法，并且想了出来，两人觉得不是很靠谱而且不会用bitset，就放弃掉了。中间似乎也有想过节约C题的空间的方法，看没什么人过，就扔掉了。到了赛后总结，听说我们的C题是正解，就差个拍平的操作，表示震惊。

总结：'''wyz回去学习一下bitset来传授全队吧，我要学习一下AC自动机，避免这套理论只有chy会的尴尬局面'''，大家有空调一下C题，还是很美滋滋的。今天的题目比较（之前某几场）难，也没见过A题这样的题，要避免一个大块（常见）的算法只有一个队员会的情况，没有想到拍平操作还是见得少了，开题顺序可能也有点问题，总之大家努力提高一下自己的知识水平，做到广泛的了解，一个算法则至少有一个人能敲（于是算法们就分成两部分了呢，似乎没什么问题？）。我也偶尔敲一下签到题，给队友空出时间来思考后面的题目。

== other ==
补题：B(√)

zhhhplus

流水账：今天看快要迟到了，疯狂赶路，没有买早饭就到机房了（貌似每次我迟到全队就会爆炸得很惨？）。随后大家看到榜上A题和B题都在十几秒的时候被人过掉了，感觉很震惊，确信这俩队不是正常的队伍。大家开始各自看题，我看到榜上过K的人很多的样子，跟队友解释了一小会儿之后觉得讲解太麻烦了，题又简单，于是自己上去敲了，平稳地1A了这道题（K1y13）。大约此时chy和wyz也在讨论F题了，也和我讲了一下题意，我觉得ok啊，过了一会儿wyz就开始敲F题了。随后和chy一起讨论H题，一段时间之后想出了做法，chy表示是个背包，总之大家觉得可以这样做，在wyz过了F题（F1y40）之后就让chy上去敲H题了。然后wyz觉得优势很大，可以看一下全部题目，我则抱着A题和B题想，苦于不太会AC自动机的那套理论（今天打算学习一波），没什么思路，A题也万万没想到最后的解法是O(n²)的，于是就都没想出来。看到C题我觉得可能是个不太好写的lazy标记线段树，但是chy在过掉H题之后（H1y63）掏出了他的板子，表示用可持久化treap可以O(logn)做区间复制操作，然后我觉得可以，但是觉得极端情况要复制太多次，不太行，提出了可以倍增一下的操作，chy和wyz此时还不太明白为什么会进行很多次复制，我解释了一会儿，然后被暂时说服似乎不用，以为自己题目读错了，在缓过来之后斥责（并没有）了两位队友，chy觉得倍增不太理解，大家在找题开，一会儿之后我觉得机子空着不是办法，表示先把treap敲上去吧，打算自己上去敲板子，把智力活动交给两位，chy拦住了我，我表示倍增我写吧，于是他就去敲了板子，我则跟wyz讲了倍增的做法，在板子敲好之后完美甩锅给wyz。在此期间，我和他们分别想了一下A题和B题（wyz还想了I题）。一个半小时之后C题敲好了，大家兴奋地交了一发，获得了一发MLE，我觉得可持久化的操作new的点数太多了，大概可以减少一些，但是大家不太知道应该怎么做（并没有想到类似替罪羊树的直接拍平操作）（据说这样写能过，可能是拍平重建的姿势不对，赛后TLE了两发，还在修改中）（以及据说另外一种做法的删点操作很复杂，不太适合写）。于是就去想A题和B题，我们队的策略是把B题分配给chy，我和wyz则想A题，chy不负众望想出了一个AC自动机的DP，调了很久细节，在最后一小时的时候我和chy讲A题可以压缩，但是似乎没什么用，wyz猜测可能是个O(n²/64)的做法，并且想了出来，两人觉得不是很靠谱而且不会用bitset，就放弃掉了。中间似乎也有想过节约C题的空间的方法，看没什么人过，就扔掉了。到了赛后总结，听说我们的C题是正解，就差个拍平的操作，表示震惊。

总结：wyz回去学习一下bitset来传授全队吧，我要学习一下AC自动机，避免这套理论只有chy会的尴尬局面，大家有空调一下C题，还是很美滋滋的。今天的题目比较（之前某几场）难，也没见过A题这样的题，要避免一个大块（常见）的算法只有一个队员会的情况，没有想到拍平操作还是见得少了，开题顺序可能也有点问题，总之大家努力提高一下自己的知识水平，做到广泛的了解，一个算法则至少有一个人能敲（于是算法们就分成两部分了呢，似乎没什么问题？）。我也偶尔敲一下签到题，给队友空出时间来思考后面的题目。

other

补题：B(√)

附加文件