转载

笔记:《挑战程序设计竞赛(第2版)》(2)

Page 134 : Millionaire

这个题,以我的智商,一开始没有很好的理解他的题解。之后看代码就毁了,代码里第一重循环示意的方向是反的,虽然只要轮数对了就好,不过这样代码阻碍理解题解,我看了好久才反应过来。

代码倒数第三行

int i = (ll)X * n / 100000; 

中的

X * n / 10000000 

其实是

X / (1000000 / n) 

也就是将100000分成`n + 1(n = 2 ^ m)`份,就可以得出X在其中是哪一份(的索引)。

接下来的一个细节问题是搜索的边界,代码里有

int jub = min(i, n - i) 

这里jub就代表了当前钱数的投注(搜索)区间 [i - jub, i + jub]

取i和 n - i 中的小值。

前一个很好理解:不能投注比自己当前钱数还多的钱。

不过后一个就不太明显了。

首先知道动态规划数组(prv,nxt)的右边界(即下标n)代表了钱数超出1000000的所有部分。

逻辑上,此时 i + jub == n 对应多个 i - jub ,即可以投注多种钱数区间,赢了以后都转移到下标n,而输了则转移到对应区间。

所以右边界乍看上去似乎不太合适,没有枚举所有可能的输钱区间(对应于 i + jub > n 的jub)。

这里给出一个解释:

容易理解,整个动态规划数组是单调非严格递增的(持有的钱多更容易赢)。

所以对于刚才所说的多个 i - jub 对应一个 i + jub == n

prv[i + jub] 此时是定值。

其实只需要看最大的一个 prv[i - jub] 。当jub取 n - i 时,有n关于i的对称点(即 i - jub 的最大值) i - (n - i)

Page 181 : 树状数组的区间操作

树状数组可以支持高效地查询和修改数列的前缀和。不过如果加入区间修改,问题就变复杂了。显然不能对区间逐个修改。

考虑对于仅在一个区间 [l, r) 上做了修改(增加x)的情况,此时,可以发现,对于l之前的部分,前缀和不变。对于r之后的部分,前缀和增加了一个常数 (r - l) * x

关键是对于 [l, r) 之间的部分,前缀和的增加量是x的函数,对于 l <= j < r ,有 (j - l) * x

拓展到多个区间时,我们有多个xi分别对应 [li, ri) 区间。

让我们化简一下问题,既然对于查询在 [li, ri) 之外的部分,我们都可以用常数表示其增量。

那么我们就关注对于特定的位置a,查询 [0, a) 的和,我们只关注那些使 li <= a < ri[li, ri)

现在的问题是如何高效地表示

(a - li) * xi 

如果我们将所有的li向左延伸到0(对应地,需要减去常量 li * xi ),就有

a * xi 

问题变成了如何高效地求解 ∑xi

答案可以是另一个树状数组。

整理一下

有一个树状数组bit0, 我们希望对其实施区间修改操作。

为此,需要引入另一个树状数组bit1。

对bit0上一个区间 [l, r) 增加x可以表示为

  • 在bit0的l处增加 -(l * x)
  • 在bit1的l处增加x。

当查询位置a越过了r时,我们还要撤销x的效果

  • 在bit1的r处增加一个 -x

这样就撤销了位置相关的修改,但要在bit0上加上常量增量,之前已经增加过 -(l * x) (实际上是减少的意思)

  • 在bit0的r处增加一个 r * x

更一般地,如果操作得到的结果可以用i的n次多项式表示,那么就可以使用n + 1个树状数组来进行维护了。

这里还是不明白,i的1次多项式的实际意义可以是区间修改,那么i的更高次多项式又可以具有怎样的意义呢?

Page 194 : 计算DAG的最短路

计算DAG的最短路不需要使用Dijkstra算法,可以简单地通过DP求解。

对于这句话我的理解如下:

考虑Dijkstra算法所能求解范围——边权为正的图,DAG与其的区别在于前者可以有环路。

Dijkstra算法处理环的方法是应用问题的贪心性,每次选取从起点出发最近抵达的点,这个点不可能有其它更短的路径了。

DAG因为不存在环路,只要求解了一个点的所有前驱(没有环才有这个定义)的最短路,自然就可以求解这个点最短路。

所以对点的选取顺序要求变弱,只要按照(任一)拓扑序选点求行了。

另外,根据上下文,这里可能想强调的是具有规则分层结构的DAG,对于这种DAG可以容易地写出动态规划算法。比如本题的图就很规则,按照集合的大小(递减)分出不同层次,逐层求解。

正文到此结束
Loading...