[二分]Codeforces1059D【Nature Reserve】题解
题目概述求一个半径最小的圆使得和 $x$ 轴相切，并且包含了所有给定的点。解题报告很明显可以二分 $r$ ，那么圆心就是 $(x,r)$ ，通过每个点就可以确定 $x$ 的范围，如果 $x$ 有...
[wqs二分+决策单调性]POJ1160【Post Office】题解
题目概述有 $n$ 个村庄，现在要建 $m$ 个邮局，一种方案的代价是每个村庄到最近的邮局的距离之和。解题报告我再来水一遍这道题……之前已经用了wqs二分去掉了一维状态，这时候DP的状态数，转移...
[二分+树状数组]Codeforces1058F【Putting Boxes Together】题解
题目概述有 $n$ 个物品，第 $i$ 个物品在 $a_i$ ，移动一格需要 $w_i$ 的代价。现在有两种操作：1.把 $w_x$ 变成 $y$ 。2.询问把 $[L,R]$ 的物品移动到 $...
[二分+DP]BZOJ1181(CROATIAN2009)【IZBROI选举】题解
题目概述有 $n$ 个组 $V$ 张票，假设 $i$ 组有 $V_i$ 的票。总共有 $m$ 个钦点机会，令 $S_i$ 表示目前 $i$ 组被钦点了几次，每次会钦点 $V_i\over{S_i...
[二分+随机]Codeforces1040D【Subway Pursuit】题解
题目概述交互题，现在要猜一个数 $x$ ，可以询问 $x$ 是不是 $l\le x\le r$ ，但是每次询问完成后 $x$ 会移动一个到距离 $\le K$ 的点。如果一次询问 $(l,l)$...
[几何+二分]Codeforces1016E【Rest In The Shades】题解
题目概述有一个光源按照 $(a\to b,s_y)$ 移动，还有 $n$ 个板 $(l_i,r_i)$ 。有 $q$ 个询问，问一个点 $(x,y)$ 被板挡住的总长度。解题报告斯波题，但是我不...
[二分]Codeforces1020D【The hat】题解
题目概述交互题，$n(n\le 10^5)$ 个人接成环，手上拿着一个数 $a_i$ 。$i$ 和 $i\ mod\ n+1$ 相邻，保证相邻人之间的数之差绝对值不超过 $1$ ，而 $i$ 和...
[离线+斜率优化+二分]BZOJ5380【Function】题解
题目概述$$
f(x,y)=\begin{cases}A_y&x=1\\f(x-1,y)+A_y&y=1\land x\not=1\\min\{f(x-1,y-1),f(x-1)...
[二分+后缀树+ST表+DFS序+主席树]LOJ2059(TJOI / HEOI2016)【字符串】题解
题目概述给出一个字符串 $S$ ，求 $max\{LCP(S_{[i,j]},S_{[c,d]})|a\le i\le j\le b\}$ 。解题报告先二分答案 $len$ ，然后只需要验证 $...
[二分+后缀树+ST表]BZOJ5405【platform】题解
题目概述给出一个长度为 $n$ 的字符串和一个长度为 $n$ 的序列 $\{a_n\}$，问有多少个子串 $s_{[L,R]}$ 满足 $Rank(s_{[L,R]})=\sum_{i=L}^{...
