[LCT维护最大生成树+二分图判定]BZOJ4025【二分图】题解
题目概述有 $n$ 个点 $m$ 条边，每条边有个出现时间 $s$ 和消失时间 $t$ ，问每个时刻是不是二分图。解题报告法老给我们上课用的PPT表示：把边加到线段树里然后线段树二分用LCT判奇...
[莫比乌斯函数+线性筛求积性函数]BZOJ4804【欧拉心算】题解
题目概述求 $\sum_{i=1}^{n}\sum_{j=1}^{n}\varphi(gcd(i,j))$ 。解题报告推式子：$\sum_{T=1}^{n}\lfloor{n\over T}\r...
[KMP-fail树]BZOJ3670(Noi2014)【动物园】题解
题目概述一个字符串，令 $num_{i}$ 表示前缀 $i$ 的长度 $\le{i\over 2}$ 的 $border$ 数量，求 $\prod_{i=1}^{n}num_i+1$ 。解题报告...
[DFS树+差分+二分图判定]BZOJ4424(Cf19E)【Fairy】题解
题目概述CF19E数据加大版。解题报告不能分治+LCT啦。由于只删除一条边所以可以大力分类讨论。先用DFS树+差分求出树边被多少个奇环覆盖以及被多少个偶环覆盖，然后：树边：如果处于所有奇环之间，...
[two-pointer+线段树]BZOJ4653(Noi2016)【区间】题解
题目概述有 $n$ 个区间，求取 $m$ 个区间使得交不为空时的最小 $max\{len\}-min\{len\}$ 。解题报告我不会做题啦……很显然区间越多交越小而且解也不会优，所以可以按照长...
[计数+分段打表]BZOJ5383(湖南省队集训2018 Day2)【游戏】题解
题目概述在 $n\times n$ 的棋盘上放 $n$ 个车(ju)，使得车之间不会吃到，且在不经过车的情况下能够从 $(1,1)$ 走到 $(n,n)$ ，求方案数。解题报告能走到只需要满足没...
[Pollard-Rho+分块枚举子集]BZOJ5382(湖南省队集训2018 Day2)【走路】题解
题目概述有一棵树，如果 $w_i|w_j$ 且 $j$ 是 $i$ 的祖先那么 $j$ 可以直接到达 $i$ ，问从第一个点到所有点的方案数。解题报告$O(n^2)$ DP很显然，考虑优化。如果...
[贪心+ST表]BZOJ4444(Scoi2015)【国旗计划】题解
题目概述在一个长为 $m$ 的环上有 $n$ 个线段 $(s_i,t_i)$ ，问第 $i$ 个线段必选时至少需要多少线段能够覆盖这个环。解题报告和BZOJ5397差不多，唯一要注意的就是在BZ...
[贪心+ST表]BZOJ5397(湖南省队集训2018 Day3)【circular】题解
题目概述在一个长为 $m$ 的环上有 $n$ 个线段 $(s_i,t_i)$ ，在线段不交的情况下最多选择多少个线段？解题报告思路还停留在以前的斯波解法上……然后gg……没环的话可以有三种做法：...
[离线+斜率优化+二分]BZOJ5380【Function】题解
题目概述$$
f(x,y)=\begin{cases}A_y&x=1\\f(x-1,y)+A_y&y=1\land x\not=1\\min\{f(x-1,y-1),f(x-1)...
