ZigZagK的博客
[DP+多项式exp]HDU5279【YJC plays Minecraft】题解
题目概述HDU5279解题报告首先每个连通块里必须是森林,然后连接每个连通块的 $n$ 条边只要删掉一条,就肯定不会存在全局环,这样每个连通块就独立了。定义 $f_i$ 表示 $i$ 个点树的方...
[DP+分治NTT]HDU5322【Hope】题解
题目概述HDU5322解题报告考虑连通块是什么样的,对于 $n$ 的排列,$n$ 所在位置之前的点肯定都是 $n$ 连通块中的,并且 $n$ 没有往后的边。然后对于 $n$ 右边的数列也可以递归...
[Palindrome Series+exgcd]HDU6320【Cut The String】题解
题目概述HDU6320解题报告暴力想法:枚举 $L$ 开始的回文串 $A$ ,和 $R$ 结尾的回文串 $B$ ,如果 $|A|+|B|=R-L+1$ 则找到一个满足的位置。由于是枚举结尾回文串...
[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中的线段进行分裂以及合并,复杂度分析和...
[离线+bitset维护传递闭包+卡空间]2022“杭电杯”中国大学生算法设计超级联赛(3)10【Range Reachability Query】题解
题目概述HDU7171解题报告题目保证了DAG,所以是个DAG上的传递闭包问题,考虑用bitset做。定义 $f_{i,j}$ 表示是否能通过 $j$ 询问中的 $[l_i,r_i]$ 边从 $...
[随机化+线段树维护凸包+最小圆覆盖]2022“杭电杯”中国大学生算法设计超级联赛(3)1006【Dusk Moon】题解
题目概述HDU7167解题报告被队内计算几何选手演了😡,本来写个最小圆覆盖就过了。首先很显然 $n$ 个点的最小圆覆盖和这个 $n$ 个点求完凸包之后的最小圆覆盖是一样的。而且数据保证随机,那么...