[离线+分块+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$ 长度和不会很长，可以...
[树上解方程+组合数化简]2022牛客暑期多校训练营3 D【Directed】题解
题目概述Directed解题报告这题竟是脑子题……显然这是个树上解方程的题目，设 $D_x$ 为 $x$ 的度数，$fa$ 为 $x$ 的父亲，$u$ 为 $x$ 儿子：$$
f_{x}={1\...
[容斥+DP+多项式求逆]2022“杭电杯”中国大学生算法设计超级联赛（1）1010【Walk】题解
题目概述HDU7147解题报告从来没做过这种容斥，长见识了😭。定义 $f_i$ 表示走了 $i$ 行都合法的权值和，以及 $g_i$ 表示走了 $i$ 行全非法的权值和（特殊的，如果 $i=1$...
[后缀自动机parent树+虚树]2022牛客暑期多校训练营1 B【Spirit Circle Observation】题解
题目概述Spirit Circle Observation解题报告找性质题最烦了.jpg。首先建SAM，考虑一个直观的做法。直接考虑枚举SAM里的节点，然后在节点上考虑 $a999\cdots$...
[线段树合并/分裂]2022牛客暑期多校训练营1 F【Cut】题解
题目概述Cut解题报告这题思路是不难的，但是如果没写过类似的就会巨难写（细节比较多）……把 $[l,r]$ 内的排序其实就是认为 $[l,r]$ 这一块按照权值线段树的顺序进行排列（正序或者倒序...
[背包回退+二进制状压DP+NTT]2022牛客暑期多校训练营1 H【Fly】题解
题目概述Fly解题报告首先想到DP：$f_{i,j,0/1/2}$ 表示前 $i$ 个二进制位（从低位到高位），到 $i$ 这位时背包大小为 $j$ ，并且状态为 $0$ 小于 $1$ 相等 $...
[阈值优化+分块]洛谷5309【[Ynoi2011] 初始化】题解
题目概述Luogu5309解题报告题目保证 $y\le x$ ，因此每次都是全局 $i\bmod x=y$ 的 $a_i$ 加上 $z$ 。不难想到 $x>\sqrt n$ 时，我们直接暴...
