[随机化+线段树维护凸包+最小圆覆盖]2022“杭电杯”中国大学生算法设计超级联赛（3）1006【Dusk Moon】题解
题目概述HDU7167解题报告被队内计算几何选手演了😡，本来写个最小圆覆盖就过了。首先很显然 $n$ 个点的最小圆覆盖和这个 $n$ 个点求完凸包之后的最小圆覆盖是一样的。而且数据保证随机，那么...
[模拟退火]BZOJ2428(HAOI2006)【均分数据】题解
题目概述把 $n$ 个数分成 $m$ 份，求最小的均方差 $\sqrt{\sum_{i=1}^m(sum_i-ave)\over m}$ ，其中 $ave={\sum_{i=1}^{n}a_i\...
[模拟退火]BZOJ3680【吊打XXX】题解
题目概述有 $n$ 个砝码，第 $i$ 个砝码在 $x_i,y_i$ ，重量为 $w_i$ 。现在把所有砝码绑在一起，求绳结平衡在哪个位置。解题报告玄学大法模拟退火……调参调到吐血。来Orz X...
[二分+随机+斯坦纳树+思维]LOJ2977(THUSCH 2017)【巧克力】题解
题目概述给出一个 $n\times m$ 的巧克力，每个位置有形状和美味值，求一个个数最小的连通块满足形状数 $\ge K$ ，且在个数最小的前提下，美味值的中位数也要最小。解题报告人类智慧题Q...
[斯坦纳树+随机]HHHOJ200【稗田的梦中之梦】题解
解题报告题目里要我们找出的实际上是一个满足条件的连通块，又因为数据范围这么小，所以想到斯坦纳树来做这种连通块最小值问题。令 $f_{i,j,s}$ 表示 $i,j$ 这个点与 $s$ 这些颜色连...
[扫描线+笛卡尔树+随机]BZOJ2658(Zjoi2012)【小蓝的好友(mrx)】题解
题目概述有一个 $R\times C$ 的网格，其中 $n$ 个格子有资源点，问至少有一个资源点的子网格个数。解题报告万年神坑。先补集转化，那么就是用总方案数减去一个资源点都没有的子网格个数，把...
[随机+差分]Codeforces799F【Beautiful fountains rows】题解
题目概述有 $m\times n$ 的矩阵，第 $i$ 行的 $[L_i,R_i]$ 是好的。现在要选出 $[A,B]$ 使得在所有行中要么没有好的元素要么有奇数个好的元素，求所有合法 $[A,...
[二分+随机]Codeforces1040D【Subway Pursuit】题解
题目概述交互题，现在要猜一个数 $x$ ，可以询问 $x$ 是不是 $l\le x\le r$ ，但是每次询问完成后 $x$ 会移动一个到距离 $\le K$ 的点。如果一次询问 $(l,l)$...
[随机+Trie]LOJ2313(HAOI2017)【供给侧改革】题解
题目概述给出一个 $n$ 位随机 $01$ 串，定义 $data(L,R)=max\{LCP(Suf_i,Suf_j)|i\not=j,L\le i,j\le R\}$ 。给出 $m$ 个询问 ...
[随机+主席树二分]BZOJ5361(Lydsy1805月赛)【对称数】题解
题目概述给出一棵 $n$ 个节点的树，每个节点有权值，一条路径上的对称数定义为最小的出现次数为偶数（包括 $0$ ）的数，现在给出 $m$ 个询问 $(x,y)$ 表示询问 $(x,y)...
