[线段树二分+树状数组]2020 ICPC 澳门 J【Jewel Grab】题解
题目概述Jewel Grab解题报告因为 $k\le 10$ ，其实就是个暴力题。记录 $pre_x$ 表示 $x$ 前面第一个颜色相同的位置（没有就记成 $0$ ），如果不能跳过，那么一定是在...
[离线+线段树套单调栈+线段树二分]2019 ICPC 香港 H【Hold the Line】题解
题目概述Hold the Line解题报告直接线段树套set是过不了的，我们需要一个小常数的做法。考虑离线，这样第 $i$ 次事件插入 $x$ 位置时，就可以认为是 $i$ 时刻 $x$ 才出现...
[cdq分治+阈值优化+NTT]2022ICPC网络赛第一场 I【Permutation】题解
题目概述给出一个排列 $\{a_n\}$ ，对于这个排列的所有循环同构，求出排列的排名，对所有排名求和。解题报告对于一个固定的 $\{a_n\}$ ，根据康托展开，可以得到排名：$$
1+\su...
[回文自动机回退]2020 ICPC 昆明 F【Generating Strings】题解
题目概述Generating Strings解题报告裸的回文自动机回退。对于一个长度为 $len$ 的回文串，在 $s$ 中出现一次的权值为 $(N-len+1)\cdot26^{N-len}$...
[广义后缀自动机]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$ 。用后缀数组可以做，但是思考起来比较麻烦。考虑后缀自动机，在建立后缀自动机的时候我们记...
[矩阵乘法+线段树]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]$ ...
[扫描线+双标记线段树]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...
