2020-team06/C114

从 Trac 迁移的文章

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

原文章内容如下：

== Rank和提交情况 ==
[[Image(2020-C04.jpg,1000px)]] 

Solved: 4/11

== 流水账 ==by zyh

其实这种较难场没啥策略上可写的东西，开场cyb会了I,zgz叫我去看G觉得我适合做这种题，此时我读了E感觉可能之后会有思路先屯着没去细想，然后因为我们队一直没有树上点分治的板子导致了本场最大的失误就是让cyb手撕点分治出了问题，一开始一直以为是算法需要打补丁，没想到纯粹就是因为点分治写错了，这确实是一个大问题，之前也碰到过一次了，但是那次打完赛季就结束了所以把这事忘了...现在已经有了这个板子，之后zgz会了B我会了G,然后cyb终于过了I，日常井喷式过题，然后我让cyb去碰一碰F,感觉他听擅长这种东西，我和zgz胡起了E,胡了一会儿我会了不考虑维护最大值的线性基部分，然后和zgz探讨怎么维护最大值，先嘴了个作法冲了一发有点问题，然后打了个补丁就过了，然后又到了cyb的rush时间，这次他甚至连编译都没完成，实在是菜菜。总的来说，感觉我们队的罚时一直偏高最近，然后中期老是井喷式过题，还是应该利用好前期的时间，用板子减少dirt率，同时也不能太相信cyb.
== 补题 ==


A:

C:

D:

F:

H:

J:

K: Upd by zgz：

暴力枚举所有能使串非法的tandem repeats的起始位置和长度，然后容斥这些限制。只需维护一些位置是否必然相同的并查集即可。

复杂度显然是爆炸的，一个优化是如果一个限制不影响并查集的状态，那显然可以删去它。

加上这个还不够，在n>>k的时候，random_shuffle一下限制序列可以快很多。

但是奥妙重重的是，在n≈k的时候，random_shuffle一下限制序列可以慢很多。

然后就过了。

Rank和提交情况

Solved: 4/11

== 流水账 ==by zyh

其实这种较难场没啥策略上可写的东西，开场cyb会了I,zgz叫我去看G觉得我适合做这种题，此时我读了E感觉可能之后会有思路先屯着没去细想，然后因为我们队一直没有树上点分治的板子导致了本场最大的失误就是让cyb手撕点分治出了问题，一开始一直以为是算法需要打补丁，没想到纯粹就是因为点分治写错了，这确实是一个大问题，之前也碰到过一次了，但是那次打完赛季就结束了所以把这事忘了...现在已经有了这个板子，之后zgz会了B我会了G,然后cyb终于过了I，日常井喷式过题，然后我让cyb去碰一碰F,感觉他听擅长这种东西，我和zgz胡起了E,胡了一会儿我会了不考虑维护最大值的线性基部分，然后和zgz探讨怎么维护最大值，先嘴了个作法冲了一发有点问题，然后打了个补丁就过了，然后又到了cyb的rush时间，这次他甚至连编译都没完成，实在是菜菜。总的来说，感觉我们队的罚时一直偏高最近，然后中期老是井喷式过题，还是应该利用好前期的时间，用板子减少dirt率，同时也不能太相信cyb.

补题

A:

C:

D:

F:

H:

J:

K: Upd by zgz：

暴力枚举所有能使串非法的tandem repeats的起始位置和长度，然后容斥这些限制。只需维护一些位置是否必然相同的并查集即可。

复杂度显然是爆炸的，一个优化是如果一个限制不影响并查集的状态，那显然可以删去它。

加上这个还不够，在n>>k的时候，random_shuffle一下限制序列可以快很多。

但是奥妙重重的是，在n≈k的时候，random_shuffle一下限制序列可以慢很多。

然后就过了。