[DP]LOJ6501(雅礼集训 2018 Day4)【Cube】题解
题目概述定义 $0$ 维基础图形为点，$1$ 维基础图形为边，$2$ 维基础图形是正方形，$3$ 维基础图形是正方体，以此类推。问 $n$ 维基础图形由多少个 $m$ 维基础图形组成。解题报告感...
[DFS树+线性基+复杂度分析]UOJ138(UER #3)【开学前的涂鸦】题解
题目概述原来有 $n$ 个点的一棵树，现在加进了 $K$ 条边。问多少种方案删边使得图依然连通。解题报告非正解警告……接下来要讲的是原题解中的算法七，不过这个解法能艹标程（度教rank1，翰...
[二分+随机+斯坦纳树+思维]LOJ2977(THUSCH 2017)【巧克力】题解
题目概述给出一个 $n\times m$ 的巧克力，每个位置有形状和美味值，求一个个数最小的连通块满足形状数 $\ge K$ ，且在个数最小的前提下，美味值的中位数也要最小。解题报告人类智慧题Q...
[FWT+快速乘]Codeforces453D【Little Pony and Elements of Harmony】题解
题目概述$a_{t}[i]=\sum_{j}a_{t-1}[j]b[count(i\ xor\ j)]$ ，其中 $count(i)$ 表示 $i$ 二进制下 $1$ 的个数。给出 $a_0,b...
[斯坦纳树+随机]HHHOJ200【稗田的梦中之梦】题解
解题报告题目里要我们找出的实际上是一个满足条件的连通块，又因为数据范围这么小，所以想到斯坦纳树来做这种连通块最小值问题。令 $f_{i,j,s}$ 表示 $i,j$ 这个点与 $s$ 这些颜色连...
[斯坦纳树]BZOJ2595(Wc2008)【游览计划】题解
题目概述在 $n\times m$ 的网格上有 $k$ 个景点，选取每个网格都有代价，求最小代价使得景点之间全部连通。解题报告感觉这个东西好mogical啊……定义 $f_{i,j,s}$ 表示...
[期望的线性性+概率DP]TopCoder【RockPaperScissors】题解
题目概述有 $n$ 个骰子，每个骰子投出剪刀、石头、布的概率已知。现在每次随机拿出剩余骰子中的一个进行投掷（并不知道这个骰子的概率分布），投完后扔掉。你要出 $n$ 次剪刀石头布，赢了得 $3$...
[离线+后缀数组+STL乱搞]LOJ6041(雅礼集训 2017 Day7)【事情的相似度】题解
题目概述有长度为 $n$ 的 $01$ 串 $s$ 和 $m$ 个询问，每次询问 $[L,R]$ 表示 $s$ 的 $[L,R]$ 这些前缀之间的最大公共后缀。解题报告SAM+LCT什么的好大啊...
[霍尔定理+主席树+复杂度分析+DP]HHHOJ197【古明地】题解
解题报告题解里有个很厉害的 $O((n+s)log_2n)$ 做法，但是我不会……我只会这种比较好想的做法。首先这明显是一个二分图完全匹配问题，我们可以把每项工作 $K_i$ 看成 $K_i$...
[单调栈+DP]Codeforces1131G【Most Dangerous Shark】题解
题目概述有 $n$ 个骨牌，每个骨牌有高度和推倒代价，骨牌可以往左往右推倒，如果两个骨牌的距离小于推倒骨牌高度那么就会向同一个方向倒下，求最小代价使得所有骨牌都倒下。解题报告不难想到 $O(n^...
