ZigZagK的博客
[多项式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$ 个点求完凸包之后的最小圆覆盖是一样的。而且数据保证随机,那么...
[容斥+DP+多项式求逆]2022“杭电杯”中国大学生算法设计超级联赛(1)1010【Walk】题解
题目概述HDU7147解题报告从来没做过这种容斥,长见识了😭。定义 $f_i$ 表示走了 $i$ 行都合法的权值和,以及 $g_i$ 表示走了 $i$ 行全非法的权值和(特殊的,如果 $i=1$...
[生成函数+记忆化搜索]HDU7057【Buying Snacks】题解
题目概述HDU7057解题报告首先这道题很显然可以用生成函数做,但是 $n$​ 太大了,因此需要考虑类似矩阵快速幂或者分治的办法。定义 $F_i$​​ 表示花费 $i$​​ 时的生成函数,那么不...