ZigZagK的博客
[离线+分块+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个礼拜...