[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$ 递降的那些点是有用的，其他点肯定都被包含在了某些点中。假设前一...
[离线+分块+Tarjan缩点+bitset维护传递闭包]The 19th Zhejiang Provincial Collegiate Programming Contest K【Dynamic Reachability】题解
题目概述CF GYM103687K解题报告科技题过于困难。考虑离线，如果我们把询问分成若干个长度为 $BLK$ 的块，那么块中最多涉及到 $BLK$ 条边，$2BLK$ 个点。这样就可以大大减小...
[离线+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$ 个点求完凸包之后的最小圆覆盖是一样的。而且数据保证随机，那么...
[离线+Trie+倍增]2022牛客暑期多校训练营2 F【NIO with String Game】题解
题目概述NIO with String Game解题报告感觉赛时榜都歪飞了……这题明明不难却只有20个队过。由于对 $t_i$ 只有单字符加的操作，因此最终所有 $t_i$ 长度和不会很长，可以...
