[Kruskal重构树]BZOJ3732【Network】题解
题目概述给出一张无向图，多次询问两个点之间最长边的最小值为多少。解题报告因为最小生成树神奇的性质，我们只需要建出最小生成树然后求最小生成树路经上的最长边就是答案。不过我是来写Kruskal重构树...
[DFS树+线性基]BZOJ3569【DZY Loves Chinese II】题解
题目概述给出 $n$ 个点 $m$ 条无向边，有 $Q$ 个询问每次删除 $k_i$ 条边（之后还原），问图是否连通。解题报告先特判掉没删边就不连通，然后我们建出一棵DFS树，那么图不连通说明一...
[Tarjan求割点]BZOJ2730(HNOI2012)【矿场搭建】题解
题目概述煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍...
[二分+后缀树+ST表]BZOJ5405【platform】题解
题目概述给出一个长度为 $n$ 的字符串和一个长度为 $n$ 的序列 $\{a_n\}$，问有多少个子串 $s_{[L,R]}$ 满足 $Rank(s_{[L,R]})=\sum_{i=L}^{...
[哈希]BZOJ2795(Poi2012)【A Horrible Poem】题解
题目概述给出一个长度为 $n$ 的字符串和 $q$ 个询问，每个询问形如 $(l_i,r_i)$ 表示求 $s_{[l_i,r_i]}$ 的最短循环节的长度（最短循环节表示循环若干次之后和原串相...
[DP]BZOJ2424(HAOI2010)【订货】题解
题目概述在第 $i$ 个月月初需要提供 $w_i$ 的货物，购买货物的单位价格为 $p_i$ 。货物可以存在上限为 $S$ 的仓库，但每月月底需要支付的单位价格为 $m$ ，仓库刚开始为空最后也...
[分数规划+树形DP]BZOJ4753(Jsoi2016)【最佳团体】题解
题目概述有 $n+1$ 个人，选第 $i$ 个人需要花费 $s_i$ ，得到 $p_i$ 的贡献，第一个人必选，没有花费和贡献。$2\sim n+1$ 都有一个推荐人（推荐人编号小于自己的编号）...
[数位DP,矩阵快速幂]BZOJ3329【Xorequ】题解
题目概述求 $[1,n]$ 中满足 $x\ xor\ 3x=2x$ 的 $x$ 的个数以及 $[1,2^n]$ 中 $x$ 的个数。解题报告我竟然分析成了 $x=3x\ xor\ 2x$ ，然后...
[DP]BZOJ1190(HNOI2007)【梦幻岛宝珠】题解
题目概述有 $n$ 个物品，每个物品的体积满足 $a\cdot 2^b$ ，背包体积为 $W$ ，求最大价值。解题报告直接上背包！因为每个物品体积满足 $a\cdot 2^b$ ，所以我们可以定...
[状压DP]BZOJ2734(HNOI2012)【集合选数】题解
题目概述如果选了 $x$ 就不能选 $2x$ 和 $3x$ ，求 $1..n$ 满足条件的子集个数。解题报告这种神题完全做不来，一波转化日神仙： x 3x 9x ...
2x 6x 18x...
