[期望DP]BZOJ4832(Lydsy1704月赛)【抵制克苏恩】题解
题目概述刚开始有 $A$ 个一点血的奴隶主，$B$ 个两点血的奴隶主，$C$ 个三点血的奴隶主。有一个克苏恩要攻击 $K$ 次，每次攻击随机攻击奴隶主或者玩家。奴隶主被攻击之后没死并且现在的奴隶...
[wqs二分+决策单调性]POJ1160【Post Office】题解
题目概述有 $n$ 个村庄，现在要建 $m$ 个邮局，一种方案的代价是每个村庄到最近的邮局的距离之和。解题报告我再来水一遍这道题……之前已经用了wqs二分去掉了一维状态，这时候DP的状态数，转移...
[树形DP]入门BZOJ3004(Noi2016十连测第一场)【访问计划】题解
题目概述有一棵带边权的树，现在要从根节点出发，至少经过所有边一次，可以传送 $K$ 次，代价为 $C$ 。问走回根节点经过的最小边权和。解题报告先考虑把传送换成另一个问题，经过一条路径并走回来的...
[贪心+阈值优化+精度]入门BZOJ3003(Noi2016十连测第一场)【奥义商店】题解
题目概述有 $n$ 个有权值的物品，现在给出若干个询问：$m$ 个颜色，每种颜色有 $c_i$ 个且和为 $n-1$ ，现在要在 $K$ 这个位置选择一个颜色，然后从 $K$ 向两边以 $D$ ...
[线段树+复杂度分析]Codeforces793F【Julia the snail】题解
题目概述有 $n$ 个点和 $m$ 个传送点 $(l,r)$ 表示可以从 $l$ 传送到 $r$ ，只能往下爬或者传送。问从 $x$ 出发在不超过 $y$ 且不低于 $x$ 的前提下能够达到的最...
[生成函数+FFT]计蒜客NAIPC2016E【K-Inversions】题解
题目概述有一个AB字符串，问间距为 $k$ 的BA对有多少，其中 $k\in[1,n-1]$ 。解题报告emm……应该算是生成函数吧？令A的位置的权值为下标，B的位置的权值为下标的相反数，那么只...
[矩阵快速幂]BZOJ4870(Shoi2017)【组合数问题】题解
题目概述求 $\sum_{i=0}^{+\infty}{nk\choose ik+r}$ 。解题报告我好斯波啊……这个式子很明显不可算，应该考虑实际意义，发现就是在 $nk$ 个里选出 $mod...
[可并堆]BZOJ4003(JLOI2015)【城池攻占】题解
题目概述有一棵 $n$ 个节点的树，每个节点有个防御值。有 $m$ 个骑士在树的节点上，如果骑士攻击力大于等于防御值就可以攻占这个节点获得收益并向上攻占，否则凉凉。问每个节点凉了多少骑士，每个骑...
[随机堆]BZOJ2333(SCOI2011)【棘手的操作】题解
题目概述加边；单点加；连通块加；整体加；单点询问；连通块最大值；整体最大值。解题报告平衡树启合好像会TLE来着，加边只求最大值就是个可并堆嘛……连通块加打tag，整体加记个量，但是要单点加怎么办...
[可持久化Trie]BZOJ3261【最大异或和】题解
题目概述有 $m$ 个操作：1.在末尾添加一个数 $a_{n+1}$ 。2.询问 $max\{a_p\ xor\ a_{p+1}\ xor\ \cdots\ xor\ a_n\ xor\ x|...
