[倍增+线性基]BZOJ4568(Scoi2016)【幸运数字】题解
题目概述给出一棵树，求从 $x$ 到 $y$ ，经过的每个点都可以决定异或还是不异或，求能够得到的最大异或值。解题报告倍增+线性基就好啦，复杂度为 $O(60^2nlog_2n)$ ，这是假的完...
[调和级数+DP]Codeforces1047E【Region Separation】题解
题目概述有一棵树，现在要把树分成若干个级别，每个级别是若干个权值加和相等的连通块。第一个级别是所有节点，之后的级别需要满足第 $i$ 个级别中的连通块均在 $i-1$ 中连通且 $i$ 的块数必...
[倍增+并查集+贪心]Codeforces1059E【Split the Tree】题解
题目概述把一棵有权值的树分成若干条儿子到祖先的路径，每条路径节点个数不能超过 $L$ ，节点权值和不能超过 $S$ ，问最少分成多少路径。解题报告一个不知道正确性的解法，大佬可以来证明或者证伪一...
[扫描线+笛卡尔树+随机]BZOJ2658(Zjoi2012)【小蓝的好友(mrx)】题解
题目概述有一个 $R\times C$ 的网格，其中 $n$ 个格子有资源点，问至少有一个资源点的子网格个数。解题报告万年神坑。先补集转化，那么就是用总方案数减去一个资源点都没有的子网格个数，把...
[二分]Codeforces1059D【Nature Reserve】题解
题目概述求一个半径最小的圆使得和 $x$ 轴相切，并且包含了所有给定的点。解题报告很明显可以二分 $r$ ，那么圆心就是 $(x,r)$ ，通过每个点就可以确定 $x$ 的范围，如果 $x$ 有...
[Manacher+离线+线段树]2015计蒜之道初赛第三场【商品推荐走马灯】题解
题目概述给出一个序列，一个回文区间的权值是区间权值和，问 $[L,R]$ 中所有回文区间的权值和。解题报告刚开始想用回文自动机 $O(n\sqrt n)$ 暴搞，然后我自带大常数TLE了……只需...
[BFS序+线段树]HDU5957【Query on a graph】题解
题目概述给一棵基环树，有两种操作：1.将到 $x$ 的距离 $\le K$ 的点权值均加上 $d$ 。2.询问到 $x$ 距离 $\le K$ 的点的权值和。解题报告emm……DFS序做多了都忘...
[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$ 次，每次攻击随机攻击奴隶主或者玩家。奴隶主被攻击之后没死并且现在的奴隶...
