UOJ Logo kczno1的博客

博客

[Usaco2005 Oct]Allowance 贪心的正确性证明

2018-11-01 20:25:35 By kczno1

题目链接:

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

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

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

贪心做法:

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

每次选择方法:

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

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

证明:

假设 v1..n 递增。

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

设第一步中选择的 i..n 的物品的体积和为 kvi1..i1 的和为 z

由第一步的定义得 kvi+z<C

因为第一步枚举到 i 的时候没有多选一个 i ,所以 (k+1)viC

因此体积和是否 C 跟物品 1..i1 无关,可以把他们都丢掉,即只考虑物品 i..n

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

然后,将所有 vi 变成 viv1,并将 C 变成 Cv1 ,这样操作就使得 v1=1

于是可以发现,第一步选的物品体积和恰为 C1 ,第二步之后物品体积和恰为 C

f1..n 来描述一个物品集合,表示这个集合中物品 ifi 个。

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

p=max{i|figi}

情况 1: gp<fp

因为 i=1nfivi=C,i=1ngiviC ,所以 i=1ngivii=1nfivi

所以 i=1pgivii=1pfivi ,又因为 gp<fp ,所以 i=1p1givii=1p1fivi+vp

所以 i=1p1givivp

那么就一定能选出一个 g1..p1 的子集 s 满足和为 vp ,归纳一下就可以证明。

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

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

情况 2: gp>fp

由第一步 p 没有多选一个知 i=pnfivi+vpC

那么不妨令 g1..p1=0,gp=fp+1 ,因为由 g 为反例可以推出这样操作后的 g 为反例。

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

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

因此就证完了。

「网络流 24 题」魔术球 贪心的正确性证明

2018-10-17 08:25:11 By kczno1

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

首先考虑证明贪心法每次的决策是唯一的,即每次能选的柱子只有 01 个。

定义 h(x)=min{a|a22x+1} ,那么第一个能放在 x 上面的数就是 h(x)2x

显然,h(x)2x 互不相同 (xN) 和原命题等价。

考虑单调性, h(x)2x 并不单调。

h(x) 是单调的,对于固定的 h(x),对应的 x 是一个区间,因此 h(x)2x 也是一个区间,考虑证明这些区间单调,不相交。

也就是说第 x 个区间的左端点 >x1 个区间的右端点,即 x2max{ix|h(ix)=x}>(x1)2min{ix1|h(ix1)=x1}

定义 g(x)=x212 ,即 max{y|h(y)=x}

则上式等价于 x2g(x)>(x1)2(g(x2)+1)

化简得 0>2

注意到这里用到了 g(x2) ,所以 x=2 要特判:3>0

所以得证。

同时可以发现每两个区间之间恰好隔着一个数,所以所有没柱子可选的数为 {x2g(x)1|x2}{1}

因此 f(n) 就是第 n+1 个没柱子可选的数1=((n+1)2g(n+1)1)1,化简得 n2+12+n1

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

【UER #6】逃跑的简单做法

2018-07-11 17:36:33 By kczno1

这是jhr优化得到的.

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

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

g很好算,fg容斥一下就可以算了.

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

x2=2(x2)+x,所以E(x2)转化为求E((x2)),然后就转化为x,yx,y都被经过的概率.

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

答案就是对h求和.

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

先考虑j<i,a,bf(j,a,b)×f(ij,x,y)

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

再减去j<ih(j,x,y)×f(ij,x,y)就好了.

时间O(n4)

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

【UER #7】套路的暴力做法

2018-07-09 11:26:48 By kczno1

sr(i)表示题面中的s(i,r)

注意到,对于一个r,sr(i)不会超过m

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

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

先令si=si1,然后对于每个j,si(1..j)都对abs(aiaj)min

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

因为考虑aj>ai的情况,假设所有可能的j从大到小是j1..m,则有2(ajk+1ai)<ajkai.

时间O(nlog2)+O(nmlognm))

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

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

UTR2的题解怎么没了

2018-07-05 22:09:01 By kczno1
kczno1 Avatar