[BFS+链表]BZOJ1098(POI2007)【办公楼biu】题解
题目概述有 $n$ 个人和 $m$ 条关系 $(x,y)$ 表示 $x$ 和 $y$ 有联系方式。如果两个人没有联系方式就需要在同一个连通块，求出连通块个数和每个连通块点的个数。解题报告其实就是...
[区间DP]BZOJ1939(Croatian2010)【Zuma】题解
题目概述有 $n$ 个珠子，可以把不少于 $K$ 个同样颜色的连续珠子消去并把两端接起来。现在可以随意加珠子，问最少加多少珠子使得所有珠子都消去。解题报告挺妙的DP：$f_{i,j,k}$ 表示...
[Dsu on tree+主席树优化建图+最大流]BZOJ3681【Arietta】题解
题目概述一棵 $n$ 个节点带点权的树，有 $m$ 种取节点的方法，第 $i$ 种 $[L,R,D,T]$ 表示只能取点权在 $[L,R]$ ，$D$ 子树中的点且只能取 $T$ 次。一个点不能...
[数位DP+堆]BZOJ3131(Sdoi2013)【淘金】题解
题目概述有 $n\times n$ 的网格，每个格子有 $1$ 块金子，现在处在 $(i,j)$ 的会变到 $(f(i),f(j))$ ，其中 $f(i)$ 表示 $i$ 十进制表示下所有位的乘...
[KMP-border]BZOJ4974(Lydsy1708月赛)【字符串大师】题解
题目概述如果 $S$ 是 $T$ 重复无数次之后的前缀，那么 $T$ 就是 $S$ 的循环节，现在给出一个串每个前缀 $i$ 的最短循环节 $per_i$ 表示前缀 $per_i$ 是前缀 $i...
[倍增+线性基]BZOJ4568(Scoi2016)【幸运数字】题解
题目概述给出一棵树，求从 $x$ 到 $y$ ，经过的每个点都可以决定异或还是不异或，求能够得到的最大异或值。解题报告倍增+线性基就好啦，复杂度为 $O(60^2nlog_2n)$ ，这是假的完...
[扫描线+笛卡尔树+随机]BZOJ2658(Zjoi2012)【小蓝的好友(mrx)】题解
题目概述有一个 $R\times C$ 的网格，其中 $n$ 个格子有资源点，问至少有一个资源点的子网格个数。解题报告万年神坑。先补集转化，那么就是用总方案数减去一个资源点都没有的子网格个数，把...
[Manacher+DP]BZOJ3790【神奇项链】题解
题目概述有一个字符串，用若干个回文串覆盖该串，回文串可以重叠，问需要的最少的回文串数 $-1$ 。解题报告很容易想到DP $f_i=f_j+1$ 其中以 $i$ 为回文中心的最长回文子串与以 $...
[莫队]BZOJ4542(Hnoi2016)【大数】题解
题目概述有一个字符串，现在问这个字符串的一个子串中有多少子串是给出的素数 $p$ 的倍数（ $0$ 也算）。解题报告$10^5$ ？莫队？先把满足条件的子串的式子列出来：$sum_R-sum_{...
[期望DP]BZOJ4832(Lydsy1704月赛)【抵制克苏恩】题解
题目概述刚开始有 $A$ 个一点血的奴隶主，$B$ 个两点血的奴隶主，$C$ 个三点血的奴隶主。有一个克苏恩要攻击 $K$ 次，每次攻击随机攻击奴隶主或者玩家。奴隶主被攻击之后没死并且现在的奴隶...
