LibreOJ β Round #2 题解

samzhang 2017-07-02 23:16:33 2017-07-07 20:49:36

By nzhtl1477

这套题还是出了一些小锅的,希望大家谅解(虽然有个原因是我不会 MD 然后请了某个大佬帮我改,然后好像多写了个 0 什么什么的) 顺便说一下,本来是有精美的题面的,可惜某管理员不让我放!!! 哦对了,还有就是每个题里面妹子介绍一下:

  1. 未来日记,番,我妻由乃
  2. Liber7,gal,一条红爱
  3. Flip Flappers,番,可可娜,帕比卡,娅娅卡
  4. 人渣的本愿,番,安乐冈花火
  5. 美好的每一天~不连续的存在~,gal,水上由歧(其实不止一个人)
  6. Angle Beats,番,仲村由理(小百合~)

A 题

直接 O( n^2 + m ) 暴力即可,大家要知道 LOJ 是非常快的~
其实这个题本来 n = 50000 的,可是不让出这么大。
挂了这个题的原因大概应该是没有 memset 成负无穷,或者后缀 \text{max} 的时候没注意细节。
挂了这个题还有个原因可能是你没加 LOJ 群,或者没刷新界面……
群号 631401747,快来加哦~

B 题

可以发现和最多为 1000000 ,所以可以设计出一个 O( n^5 ) 的 DP(假设都同阶), f[i][j] 表示考虑到前 i 个数,现在和为 j 是否可行,然后转移的时候枚举第 i 个数是蛤,发现这个东西可以用 \text{ bitset } 优化,然后发现第二维有 \frac{1}{2} 常数,于是复杂度变成了 O( \frac{n^5} {128} ) ,可以通过此题 其实标程用了 STL 的 bitset,也就 400 ms,所以这个题不卡常的。 挂了这个题的原因大概是你 bitset 开成了 1000000

C 题

发现每次答案一定不会变大,因为这个变换类似合并。发现每次 x \rightarrow y 相当于合并 x y 的集合,然后注意到合并的时候每个点只会和其前驱后继产生贡献,所以可以用启发式合并 set 来实现,复杂度 O( n\log^2n + m ) ,可以通过。
然后还可以通过启发式合并平衡树或者线段树,Trie 来做到 O( n\log{n} + m ) 的复杂度。
挂了这个题的原因大概是你合并的时候没有特判 x = y 的情况。

D 题

我们可以发现,这个排序是所有数都一起排序,所以可以维护一个数据结构,还有一个前缀和,前缀和维护的是没有被 sort 过的东西,数据结构维护的是被 sort 过的东西,然后每次 sort 的时候可以暴力插入所有上次 sort 过后新插入的数。

1 操作直接在前缀和后面加一个数就可以了;
2 操作直接在数据结构和前缀和里面一起查询就可以了。

然后就是怎么实现这个数据结构的问题:

3 操作是所有数 \text{xor} 一个数,所以大概就是个 Trie 的事情了。
Trie 是可以打全局 \text{xor} 标记的,然后前缀和部分明显也可以打全局 \text{xor} 标记。
Trie 的全局 \text{xor} 标记其实非常简单,就是如果这个 \text{xor} 标记这一位为 1 ,就 swap 两个儿子就可以了。
Trie 每个节点维护一个 31 个数的数组,表示这个子树里面每个二进制位的个数,因为要查区间和。
然后就可以通过在 Trie 上面二分得到其前 k 小的数的和了,这个题就做完了。
这个东西挺难描述的,具体实现还是看标程吧,或者问我也可以…
标程自认为写的很可读的~
时间复杂度 O( ( n + m )\log{n}\log{v} ) ,空间复杂度 O( n{\log^2v} ) ,可以用特技优化到 O( n\log{v} ) 的空间.

E 题

先考虑如果不带修改,而且只有一个串,怎么做。
对每个数单独考虑贡献,即可以发现,假设这个串中位置 a_1 , a_2,\dots ,a_n 都是这个数,那么这个数在这个串里面,这个颜色在 v( a_2 – a_1 + 1 ) + v( a_3 – a_2 + 1 ) +\cdots +v(a_n-a_{n-1}+1) 个子串中没有出现,其中 v( x ) \frac{x( x – 1 )}{2}
所以通过统计每个颜色不在哪些子串里面出现可以得到答案。

现在考虑不带修改,多个串。
算出每个串里面每个颜色不在哪些子串里面出现过,然后把所有串里面的这个东西一起乘起来,就得到了答案。

然后怎么带修改?
发现每次只会改变一个颜色在一个串里面不出现的次数,于是用数据结构维护就可以了。

其实挺难写的……

挂了这个题的原因大概是你没特判这个串里面全是这个数的情况,也就是说,按照正常写法来讲,需要维护一个逆元,然而 0 并没有逆元,如果一个串里面全是同一个颜色的话,你这个颜色的答案就会乘上 0 ,然后就会爆炸,所以记下来 0 的个数就可以了。

F 题

“可持久化启发式合并”,这个题本来预备给 YnOI2018 的,但是由于有个简单做法,而且可以通过黑科技过掉这个题,所以就放到 YnOI2016 了。
如果不带撤销,这个就是个经典的合并数据结构问题,可以用 Trie 或者平衡树做到 O( n\log{n} ) 的合并。
但是带撤销就有大问题了,因为数据结构合并都是均摊的……
那只要让每次复杂度严格就可以了~!

第一个做法

首先考虑使用 bitset,bitset 怎么处理相同元素呢?只需要离散化的时候维护一下就可以了。
然后合并的时候可以直接合并两个 bitset,复杂度 O( \frac{n}{64} )
好像没问题……?等等,空间为什么是 50 MB 啊,我的做法要 1280 MB 啊,这还让我怎么活?
其实用点小技巧这个空间复杂度立马 O( nm ) \rightarrow O( n\log{n} )
因为没有强制在线,所以可以离线建操作树,然后操作树上面 DFS。
bitset 怎么压空间?bitset 其实可以用一个 vector 来存,就是说对于每个 64 位,如果全是 0 我们就不存这 64 位,然后我们 bitset 里面每个节点还需要记录一下现在这个节点在 bitset 里面第几位,也就是说可以通过缩点将 bitset 中连续 64 个全是 0 的位缩掉的意思,这样时间复杂度不变,但是空间复杂度可以大大改良~

离线 DFS 操作树的时候,假设这次操作是把 bitset A 和 bitset B 合并得到 bitset C ,为了撤销这次合并,我们需要保存 a 或者 b 中的一个,当然保存最小的一个啦!

然后这个空间复杂度就变成 O( n\log{n} ) 了。

还是证明一下吧:
因为把 A B 合并,如果保存小的那个 bitset,就是一个类似于启发式合并的东西。
可以理解为 A 集合的大小至少扩大了一倍,而代价是 O( \operatorname{sizeof}( A ) ) 的,这样显然每个元素只会被记录 \log 次,所以空间复杂度自然是 O( n\log{n} ) ,还有个 \frac{1}{8} 左右的常数吧。

因为离线建操作树,所以空间代价是到所有叶子节点的时候空间的最大值,而不是空间的和,这一点大大优化了空间。
时间复杂度 O( \frac{nm} {64} ) ,空间复杂度 O( n\log{n} + m ) 的做法!
而且很多人做这个题的想法应该是:
第一眼:这个不是裸的平衡树启发式合并吗。
第二眼:好像要可持久化平衡树。
第三眼:woc 没法做啊。
最后发现本质上还是要启发式合并来优化。

千古神犇 zzq 好像会一个空间 O( n + m ) 的神犇做法。

可以问问她哦~

第二个做法

还是考虑怎么优化这个合并的复杂度,变成严格了。
发现可以通过维护值域分块来做到这一点,也就是说在值域上,每 sqrt 个数存一下前面有多少个数这样的操作。
然后这个可以 O( \sqrt{ n} ) 合并。
然后我们可以 O( \sqrt{ n} ) 来定位这次查询的答案是在哪个块里面,但是我们光知道哪个块还是没用的,需要知道具体是哪个数。
可以通过维护一个带撤销的并查集来 O( \log{ n} ) check 每个数是否存于这个集合里面。
时间复杂度 O( m\sqrt{ n\log{n} } ) ,空间复杂度 O( m\sqrt{ n\log{n} } )
但是怎么可能让这么简单的东西直接过掉。
这个空间明显超标。
所以需要用一些黑科技来卡空间。
反正被一个大佬用这个方法艹了这个题的标程,非常可惜。

题解到此结束,有问题来问出题人吧~

共 12 条回复

liu_cheng_ao

hahah.gif

nzhtl1477

我早已猜到了这一结果(黑框滑稽)

AntiLeaf

MDZZ 时间空间双双被卡常,算了不玩了……

Sky_miner

笑看楼下 TLE + MLE & 坐在我对面发疯

AntiLeaf

可以哇……今天有点晚了,明天下午写一发试试吧 (虽然感觉应该会被卡常

nzhtl1477

你要不要写一发试试。。?

AntiLeaf

蛤……好像写错了,空间是 O(n\log n) 的……(因为还要建 Trie ……)

nzhtl1477

诶空间是线性的。。?

nzhtl1477

F题的O( nsqrt( n )logn )的块状链表做法 我觉得应该会TLE+MLE的。。。 因为我说的那个O( nsqrt( nlogn ) ) 做法用的是值域分块和并查集,比这个常数小太多了 而且写那份代码的是个卡常大佬,还用了一堆乱搞东西。。。

xc01

我觉得我B题是n^4的DP怎么办啊QAQ https://loj.ac/submission/11127