题目链接：

http://poj.org/problem?id=3040

https://www.lydsy.com/JudgeOnline/problem.php?id=1685

某普及模拟赛搬了这题，题解是贪心，我不会证还找不到证明。于是想了挺久然后证出来了。

贪心做法：

每次选出一个体积和 $\ge C$ 的物品集合，直到剩下物品体积和不足 $<C$ 为止。

每次选择方法：

1.按 $v$ 从大到小枚举每个物品，在保证体积和 $<C$ 的情况下能选多少选多少。

2.将还存在的 $v$ 最小的物品加入选择的集合。显然加了之后体积和 $\ge C$ 。

证明：

假设 $v_{1..n}$ 递增。

首先，如果在第二步中选择的物品不是 $1$ ，设它为 $i$ 。

设第一步中选择的 $i..n$ 的物品的体积和为 $k{v}_i$ ， $1..i-1$ 的和为 $z$ 。

由第一步的定义得 $k{v}_i+z<C$ 。

因为第一步枚举到 $i$ 的时候没有多选一个 $i$ ，所以 $(k+1)v_i\ge C$ 。

因此体积和是否 $\ge C$ 跟物品 $1..i-1$ 无关，可以把他们都丢掉，即只考虑物品 $i..n$ 。

这样操作后第二步选择的物品就一定是 $1$ 了。

然后，将所有 $v_i$ 变成 ${\displaystyle \frac{v_i}{v_1}}$，并将 $C$ 变成 $\lceil {\displaystyle \frac{C}{v_1}\rceil }$ ，这样操作就使得 $v_1=1$ 。

于是可以发现，第一步选的物品体积和恰为 $C-1$ ，第二步之后物品体积和恰为 $C$ 。

用 $f_{1..n}$ 来描述一个物品集合，表示这个集合中物品 $i$ 有 $f_i$ 个。

假设贪心法得到的下一个选择为 $f$ ，但下一个选择为 $g$ 能得到更优的答案(称 $g$ 为反例)。

令 $p=max\{i|f_i\ne g_i\}$ 。

情况 $1:$ $g_p<f_p$

因为 $\sum _{i=1}^n{f}_i{v}_i=C$,$\sum _{i=1}^n{g}_i{v}_i\ge C$ ，所以 $\sum _{i=1}^n{g}_i{v}_i\ge \sum _{i=1}^n{f}_i{v}_i$

所以 $\sum _{i=1}^p{g}_i{v}_i\ge \sum _{i=1}^p{f}_i{v}_i$ ，又因为 $g_p<f_p$ ，所以 $\sum _{i=1}^{p-1}{g}_i{v}_i\ge \sum _{i=1}^{p-1}{f}_i{v}_i+v_p$ 。

所以 $\sum _{i=1}^{p-1}{g}_i{v}_i\ge v_p$ 。

那么就一定能选出一个 $g_{1..p-1}$ 的子集 $s$ 满足和为 $v_p$ ，归纳一下就可以证明。

显然不选 $s$ 而多选一个 $p$ 肯定更优。

那么由 $g$ 为反例就可以推出 $g-s+\{p\}$ 为反例。归纳证明即可。

情况 $2:$ $g_p>f_p$

由第一步 $p$ 没有多选一个知 $\sum _{i=p}^n{f}_i{v}_i+v_p\ge C$

那么不妨令 $g_{1..p-1}=0,g_p=f_p+1$ ，因为由 $g$ 为反例可以推出这样操作后的 $g$ 为反例。

那么既然现在 $1..p-1$ 都不用，那么不妨令以后也都不用了，不然就会得到一个最小非零元素更小的反例，归纳证明即可。

那么只用 $p..n$ 的话 $f$ 显然优于 $g$ ，因为少用了一个 $p$ 。

因此就证完了。

我曾经在 uoj blog 问过，非常幸运的有两个大神给了解答，但当时我对于 pengyihao's blog 中答案式子(即 $f(n)$ )的推导搞不懂(他自己也忘了)。最近有学弟问，于是证了一下。

首先考虑证明贪心法每次的决策是唯一的，即每次能选的柱子只有 $0$ 或 $1$ 个。

定义 $h(x)=min\{a|a^2\ge 2x+1\}$ ，那么第一个能放在 $x$ 上面的数就是 $h(x{)}^2-x$ 。

显然，$h(x{)}^2-x$ 互不相同 $(x\in N^{\ast })$ 和原命题等价。

考虑单调性， $h(x{)}^2-x$ 并不单调。

但 $h(x)$ 是单调的，对于固定的 $h(x)$，对应的 $x$ 是一个区间，因此 $h(x{)}^2-x$ 也是一个区间，考虑证明这些区间单调，不相交。

也就是说第 $x$ 个区间的左端点 $>$ 第 $x-1$ 个区间的右端点，即 $x^2-max\{i_x|h(i_x)=x\}>(x-1{)}^2-min\{i_{x-1}|h(i_{x-1})=x-1\}$ 。

定义 $g(x)=\lfloor \frac{x^2-1}{2}\rfloor$ ，即 $max\{y|h(y)=x\}$ 。

则上式等价于 $x^2-g(x)>(x-1{)}^2-(g(x-2)+1)$ 。

化简得 $0>-2$ 。

注意到这里用到了 $g(x-2)$ ，所以 $x=2$ 要特判：$3>0$。

所以得证。

同时可以发现每两个区间之间恰好隔着一个数，所以所有没柱子可选的数为 $\{x^2-g(x)-1|x\ge 2\}\bigcup \{1\}$ 。

因此 $f(n)$ 就是第 $n+1$ 个没柱子可选的数$-1=((n+1{)}^2-g(n+1)-1)-1$，化简得 $\lfloor \frac{n^2+1}{2}\rfloor +n-1$ 。

求出 $f(n)$ 以后需要证明 $f(n)+1$ 是不可行的，注意到最大的 $n+1$ 个数两两无法得到完全平方数即可。

这是$jhr$优化得到的.

首先把求方差转化为求$E(x)$和$E(x^2)$($x$表示某个方案经过的不同位置数,$E$表示期望)

定义$f(i,x,y)$表示第$i$天第一次到达$(x,y)$的概率,$g(i,x,y)$表示第$i$天到达$(x,y)$的概率.

$g$很好算,$f$用$g$容斥一下就可以算了.

$E(x)$只用对$f$求和就好了.

$x^2=2(\genfrac{}{}{0ex}{}{x}{2})+x$,所以$E(x^2)$转化为求$E((\genfrac{}{}{0ex}{}{x}{2}))$,然后就转化为$\sum _{x,y}x,y$都被经过的概率.

定义$h(i,x,y)$表示第$i$天第一次到达了一个点$(a,b)$,且之前经过了$(a-x,b-y)$的所有情况的概率和.

答案就是对$h$求和.

怎么计算$h(i,x,y)$呢?

先考虑$\sum _{j<i,a,b}f(j,a,b)\times f(i-j,x,y)$

它多算的情况就是,在经过$(a,b)$之前就已经经过了$(a+x,b+y)$

再减去$\sum _{j<i}h(j,-x,-y)\times f(i-j,x,y)$就好了.

时间$O(n^4)$

代码http://uoj.ac/submission/265113

令$s_r(i)$表示题面中的$s(i,r)$

注意到,对于一个$r$,$s_r(i)$不会超过$\sqrt{m}$种

从左到右枚举$r$,线段树维护$s_r$,然后再在线段树上$dfs$计算以$r$右端点的答案,就是当一个区间的$s_r(i)$一样时直接$check$一下区间左端点然后返回.

具体怎么维护线段树,就是枚举到$i$的时候

先令$s_i=s_{i-1}$,然后对于每个$j$,$s_i(1..j)$都对$abs(a_i-a_j)$取$min$

但实际上有可能更新的$j$只有$log(m)$个

因为考虑$a_j>a_i$的情况,假设所有可能的$j$从大到小是$j_{1..m}$,则有$2(a_{j_{k+1}}-a_i)<a_{j_k}-a_i$.

时间$O(nlo{g}^2)+O(n\sqrt{m}log\frac{n}{\sqrt{m}}))$

后面这个东西虽然带$log$但常数比较小(把线段树换成平衡树好像就不带$log$了)

代码:http://uoj.ac/submission/264123

http://uoj.ac/contest/36