[离线+分块+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]$ 边从 $...
[bitset+树链剖分+线段树+霍尔定理]BZOJ5404【party】题解
题目概述有 $n$ 个点的有根树，每个节点只能往上走，且每个节点有一个特产。现在有 $q$ 个询问，每次询问 $c$ 个点，求这些点走到他们的公共祖先，在满足：1.每个人带的特产数量相等。2.没...
[离线+后缀数组+STL乱搞]LOJ6041(雅礼集训 2017 Day7)【事情的相似度】题解
题目概述有长度为 $n$ 的 $01$ 串 $s$ 和 $m$ 个询问，每次询问 $[L,R]$ 表示 $s$ 的 $[L,R]$ 这些前缀之间的最大公共后缀。解题报告SAM+LCT什么的好大啊...
[STL乱搞+压位]BZOJ5087【Polycomp】题解
题目概述给出 $f(x),g(x),h(x)$ ，求 $f(g(x))\ mod\ h(x)$ ，系数在 $mod\ 2$ 意义下。解题报告直接就有一个 $O(n^2log_2n)$ 的多项式取...
[莫队+STL乱搞]BZOJ4810(Ynoi2017)【由乃的玉米田】题解
题目概述给出一个序列 $\{a_n\}$ 和 $m$ 次询问，每次询问 $[L,R]$ 中是否有两个数相加为 $x$ 或两个数相减为 $x$ 或两个数相乘为 $x$ 。解题报告看我都死了3个礼拜...
