[最小割]BZOJ3144(Hnoi2013)【切糕】题解
题目概述有一块 $X\times Y\times Z$ 的切糕，每个点 $(x,y,z)$ 都有不和谐值 $v(x,y,z)$ 。现在要切这块切糕，为每个直线 $(x,y)$ 选出一个点 $z$...
[二分+后缀数组]BZOJ4310【跳蚤】题解
题目概述有一个串 $S$ ，现在要把 $S$ 分成不超过 $k$ 段，从每一个子串选出最大的子串，再从这些最大的子串中选出最大的串"JZ串"，求最小的"JZ串"（题面有误，应该是最小的而不是最大...
[决策单调性]BZOJ2369【区间】题解
题目概述有 $n$ 个区间 $A_i=[L_i,R_i]$ ，现在选 $m$ 个 $(m>1)$ 区间，贡献为 $|A_{k_1}\cap A_{k_2}\cap A_{k_3}\cdot...
[DP]BZOJ1566(NOI2009)【管道取珠】题解
题目概述有两个管道，第一个有 $n$ 个黑白珠子，第二个有 $m$ 个黑白珠子，每次可以从一个管道取出最靠管道口的珠子。假设有 $k$ 中取珠子的方法，第 $i$ 种方案的方案数为 $a_i$ ...
[最小割+Tarjan]BZOJ1797(Ahoi2009)【Mincut 最小割】题解
题目概述给出一张 $n$ 个点 $m$ 条有向边的图，现在要求 $S,T$ 的最小割，问每一条边：有没有可能出现在最小割中。是否一定出现在最小割中。解题报告先跑出随意一种最小割（最大流），然后在...
[最大权闭合图]BZOJ4873(Shoi2017)【寿司餐厅】题解
题目概述题目太复杂了QAQ，自己去看吧……吃我传送门。解题报告很显然最优解一定是选若干个不相交的区间。我们观察题目里的条件，发现带有很多“强制”操作，比如吃了 $[L,R]$ ，里面的所有子区间...
[最大权闭合图]BZOJ1497(NOI2006)【最大获利】题解
题目概述有 $n$ 个点 $m$ 条边，每个点需要花费 $p_i$ 购买，每条边可以得到 $c_i$ 的价值。现在要购买一些点，如果一条边两端的点都被购买了，就可以得到这条边的价值。求最大价值。...
[贪心+线性基]BZOJ2460(BeiJing2011)【元素】题解
题目概述有 $n$ 种无数个的物品，每种物品带有ZZK的蒟蒻值 $weak_i$ 和JZ的神犇值 $strong_i$ ，你现在可以选任意个物品，将得到所有物品神犇值之和的JZ神犇值。但是ZZK...
[Tarjan+树形背包]BZOJ2427(HAOI2010)【软件安装】题解
题目概述有 $n$ 个软件和 $m$ 的容量，每个软件需要 $w_i$ 的容量，有 $v_i$ 的价值，同时依赖 $d_i$ 软件( $d_i=0$ 则没有依赖)。问最大的价值。解题报告这是道假...
[裴蜀定理]BZOJ2299(HAOI2011)【向量】题解
题目概述问能否用任意个向量 $(\pm a,\pm b)$ 和 $(\pm b,\pm a)$ 组合出向量 $(x,y)$ 。
