ZigZagK的博客
真正的退役 | ACM生涯回忆录
ACM,作为OI生涯的延续,占据了我大学前三年的大部分时间。在三年ACM经历中,我获得过成功,也跌落过低谷,达到过新的高峰,也留下了一些遗憾。由于心境的成长,相比于OI退役时的遗憾不舍,ACM...
第47届ICPC EC-Final现场赛游记
Day [-n,-1]这次是我和熊哥第一次EC(也是最后一次),柴老师是第二次。我们新组的杭电4队这赛季取得了不错的成绩,但是训练时还是偶尔会发现严重的短板,那就是乱搞题和脑子题,并不能稳定快速...
[可持久化平衡树]洛谷5055【可持久化文艺平衡树】题解
题目概述Luogu5055解题报告带tag的可持久化平衡树,Pushdown需要在新建的节点上进行,并且Pushdown需要新建两个儿子,以避免影响之前的信息。好像看到了很多Pushdown在原...
[可持久化平衡树]洛谷3835【可持久化平衡树】题解
题目概述Luogu3835解题报告由于非旋Treap的Split和Merge都是自上而下的操作,因此可以很方便的可持久化。未解之谜:Split肯定需要新建节点,但是Merge好像并不需要?洛谷这...
[线段树二分+树状数组]2020 ICPC 澳门 J【Jewel Grab】题解
题目概述Jewel Grab解题报告因为 $k\le 10$ ,其实就是个暴力题。记录 $pre_x$ 表示 $x$ 前面第一个颜色相同的位置(没有就记成 $0$ ),如果不能跳过,那么一定是在...
[主席树二分+复杂度分析]牛客IOI周赛28-提高组 C【下克上の天邪鬼】题解
题目概述下克上の天邪鬼解题报告顺着 ${\lfloor{a_i\over 2}\rfloor}\le a_j<a_i$ 想,不难想到利用这个 $\lfloor{a_i\over 2}\rf...
[Splay+并查集]AGM 2020 Qualification Round【Unpredictable Tree】题解
题目概述CFGYM102566L解题报告如果没有询问路径就是很裸的平衡树维护DFS序,对于每个节点维护入栈节点 $x_{in}$ 和出栈节点 $x_{out}$ ,就可以方便的维护出DFS序。套...
[后缀自动机+线段树合并]Codeforces1037H【Security】题解
题目概述CF1037H解题报告算法不难得出:对于 $x$ 的每个前缀 $x[1,i]$ ,往后添加一个比 $x_{i+1}$ 大的字符 $ch$ ,$i$ 越大 $ch$ 越小得到的答案就越小。...
[广义后缀自动机+DP+单调队列]洛谷4022(CTSC2012)【熟悉的文章】题解
题目概述Luogu4022解题报告不难想到二分答案 $mid$ ,然后求 $L\ge mid$ 是否可行。令 $K={\lfloor{len\over 10}\rfloor}$ ,那么舍弃的位置...
[广义后缀自动机]Codeforces316G3【Good Substrings】题解
题目概述CF316G3解题报告用广义后缀自动机做可以避免很多复杂的情况。把 $s$ 和所有 $p$ 都扔进广义SAM里,然后把 $s$ 扔进SAM匹配得出所有属于 $s$ 的节点(注意 $fai...