ZigZagK的博客
[离线+可持久化树+线段树分治+并查集按秩合并+哈希]2022牛客暑期多校训练营8 I【Equivalence in Connectivity】题解
题目概述Equivalence in Connectivity解题报告好像确实有维护动态图的方法……但是可能是考场上写不出的那种……考虑离线,建出可持久化树,如果用并查集维护图的连通性,会发现不...
[后缀数组+复杂度分析]2022牛客暑期多校训练营7 I【Suffix Sort】题解
题目概述Suffix Sort解题报告一直在想Hash,然后寄了……实际上应该分析一下性质。首先有一个比较显然的想法是将 $S$ 变为另一个数组,$a_i$ 表示 $S_i$ 与上一个相同字符的...
[KMP+后缀数组+主席树]2022牛客暑期多校训练营6 L【Striking String Problem】题解
题目概述Striking String Problem解题报告神仙题,根本想不到。记 $n$ 为 $S$ 长度,$m$ 为 $T$ 长度,$U_i$ 表示 $S[l_1,r_1]+\cdots+...
[DP+复杂度分析]2022“杭电杯”中国大学生算法设计超级联赛(7)【Counting Good Arrays】题解
题目概述HDU7217解题报告一个显然的想法:定义 $f_{i,j}$ 表示放了 $i$ 位,第 $i$ 位为 $j$ 的方案数,那么:$$ f_{i,j}=\sum_{d|j}f_{i-1,d...
[Bluestein套路+多项式ln]2022“杭电杯”中国大学生算法设计超级联赛(7)1010【Connectivity of Erdős-Rényi Graph】题解
题目概述HDU7218解题报告这道题看起来和城市规划很像,但是由于要考虑概率,所以卷积式子和求方案数的式子不一致。定义 $f_i$ 表示 $i$ 个点成为一个连通块的概率,考虑两个连通块的概率:...
[容斥+多项式求逆]2022“杭电杯”中国大学生算法设计超级联赛(8)1013【Shattrath City】题解
题目概述HDU7232解题报告比赛的时候想的是正着做,写完DP式子发现是个看起来很可做的东西,结果实际上不能做,寄掉了。实际上应该倒着做,$f_{i}$ 表示 $[1,n]$ 排列第一次出现在 ...
[多项式exp]2022“杭电杯”中国大学生算法设计超级联赛(6)1003【Find the Number of Paths】题解
题目概述HDU7199解题报告多项式套路题,需要把题目中两种路径对应到比较容易处理的多项式形式。首先是 $i\to i+1$ ,有 $n+k-i$ 条路径,这个形式不太友好,因此我们考虑把整个序...
[珂朵莉树+线段树]2022“杭电杯”中国大学生算法设计超级联赛(5)1001【Pandaemonium Asphodelos: The First Circle (Savage)】题解
题目概述HDU7185解题报告其实并不难。由于每次区间操作都是直接覆盖成一种颜色,所以我们可以考虑用set维护所有的颜色相同的线段,然后每次操作就是对set中的线段进行分裂以及合并,复杂度分析和...
[回文自动机回退]2020 ICPC 昆明 F【Generating Strings】题解
题目概述Generating Strings解题报告裸的回文自动机回退。对于一个长度为 $len$ 的回文串,在 $s$ 中出现一次的权值为 $(N-len+1)\cdot26^{N-len}$...
[三维不重复数点]2022牛客暑期多校训练营4 E【Jobs (Hard Version)】题解
题目概述Jobs (Hard Version)解题报告首先我们先考虑二维不重复数点问题:不难发现按照 $x$ 排序后,只有 $y$ 递降的那些点是有用的,其他点肯定都被包含在了某些点中。假设前一...