[树形DP]入门BZOJ3004(Noi2016十连测第一场)【访问计划】题解
题目概述有一棵带边权的树，现在要从根节点出发，至少经过所有边一次，可以传送 $K$ 次，代价为 $C$ 。问走回根节点经过的最小边权和。解题报告先考虑把传送换成另一个问题，经过一条路径并走回来的...
[贪心+阈值优化+精度]入门BZOJ3003(Noi2016十连测第一场)【奥义商店】题解
题目概述有 $n$ 个有权值的物品，现在给出若干个询问：$m$ 个颜色，每种颜色有 $c_i$ 个且和为 $n-1$ ，现在要在 $K$ 这个位置选择一个颜色，然后从 $K$ 向两边以 $D$ ...
[矩阵快速幂]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|...
[二分图增广路+Tarjan]BZOJ2140【稳定婚姻】题解
题目概述有 $n$ 对CP，和 $m$ 对前男女友关系，一对CP（因抢着打隔膜导致电脑爆炸所以）解散之后可能会旧情复燃，导致很多CP都解散。问第 $i$ 对CP解散之后还能否使得所有人都找到新C...
[二分+DP]BZOJ1181(CROATIAN2009)【IZBROI选举】题解
题目概述有 $n$ 个组 $V$ 张票，假设 $i$ 组有 $V_i$ 的票。总共有 $m$ 个钦点机会，令 $S_i$ 表示目前 $i$ 组被钦点了几次，每次会钦点 $V_i\over{S_i...
[LCT+构造]BZOJ3091【城市旅行】题解
题目概述维护森林，每次询问一条路径 $(X,Y)$ 上任意选出两个点 $(x,y)$ 的路径权值和的期望。解题报告刚开始竟然极其斯波的想成了路径权值和的 $size$ 倍……把一条路径排成序列，...
[离线+霍尔定理+线段树]BZOJ2138【stone】题解
题目概述有 $n$ 堆石子，每堆 $a_i$ 个，现在要取 $m$ 次，第 $i$ 次在 $[L_i,R_i]$ 中取 $K_i$ 个（不够 $K_i$ 就取完）。问在前 $i-1$ 次取到的最...
