ZigZagK的博客
[广义后缀自动机]2021 ICPC 澳门 I【LCS Spanning Tree】题解
题目概述LCS Spanning Tree解题报告听说这题卡倍增SA,表示强烈谴责😡(不过我没想到SA怎么做)。由于需要求任意两个字符串之间的最长公共子串,因此考虑广义SAM,在构造时,记录一下...
[后缀自动机]The 2021 ICPC Asia Shenyang Regional Contest M【String Problem】题解
题目概述String Problem解题报告首先很显然,对于前缀 $i$ ,答案一定是某一个位置到 $i$ 。用后缀数组可以做,但是思考起来比较麻烦。考虑后缀自动机,在建立后缀自动机的时候我们记...
[AC自动机+倍增]The 2021 China Collegiate Programming Contest (Harbin) L【Karshilov's Matching Problem】
题目概述Karshilov's Matching Problem解题报告首先不难想到对 $n$ 个匹配串建AC自动机,在 $fail$ 树上求和就可以得知匹配到 $p$ 点时的权值和。然后我们观...
[矩阵乘法+线段树]The 2021 ICPC Asia Nanjing Regional Contest E【Paimon Segment Tree】题解
题目概述Paimon Segment Tree解题报告首先肯定考虑离线,把询问 $[L,R],[x,y]$ 拆成 $([L,R],[0,y])-([L,R],[0,x-1])$ 。然后我们按顺序...
[广义后缀自动机+二分]2021-2022 ACM-ICPC Brazil Subregional Programming Contest B【Beautiful Words】题解
题目概述Beautiful Words解题报告先把 $A$ 复制一份,令 $B_i=A[i-n+1,i]$ 。然后二分答案 $mid$ ,这样就只需要验证是否存在 $i\in[n,2n-1]$ ...
[后缀数组+离线+扫描线+线段树二分]2021 CCPC 桂林 J【Suffix Automaton】题解
题目概述Suffix Automaton解题报告被时限骗了,以为做法是两个 $\log$(空间爆炸),其实只要离线就可以一个 $\log$ 。求出后缀数组后,第 $i$ 个后缀多出来的就是 $[...
[扫描线+双标记线段树]2020 ICPC EC-final G【Prof. Pang's sequence】题解
题目概述Prof. Pang's sequence解题报告首先根据经典套路,我们记录 $pre_i$ 表示 $i$ 上次的出现位置,这样的话对于一个左端点 $L$ ,只有 $pre_i<L...
[FWT+高维前缀和]2020 ICPC 沈阳 M【United in Stormwind】题解
题目概述United in Stormwind解题报告太久没做过这种题了,其实非常套路。题目里给出了 $n$ 个 $01$ 串,把两个串异或就可以得到两个串不同位置的集合。首先我们可以利用FWT...
2020 CCPC 长春站 部分题解
F. Strange Memory呜呜呜,想了半天怎么快速处理这个 $i\ \mathbb{xor}\ j$ ,之后发现其实根本没有好的处理方法,只能拆位计算贡献。考虑第 $B$ 位的贡献,那么...
[Trie+复杂度分析]2020 ICPC 济南 K【Kth Query】题解
题目概述Kth Query解题报告这道题给了我01 Trie的新思路QAQ。首先我们考虑没有限制的情况,我们对于每个节点 $x$ 维护 $MIN_{x,k}$ 表示 $x$ 子树中第 $k$ 小...