笔记：《挑战程序设计竞赛（第2版）》（2）
Page 134 : Millionaire
这个题，以我的智商，一开始没有很好的理解他的题解。之后看代码就毁了，代码里第一重循环示意的方向是反的，虽然只要轮数对了就好，不过这样代码阻碍理解题解，我看了好久才反应过来。
代码倒数第三行
int i = (ll)X * n / 100000; 中的
X * n / 10000000 其实是
X / (1000000 / n) 也就是将100000分成｀n + 1(n = 2 ^ m)｀份，就可以得出Ｘ在其中是哪一份（的索引）。
接下来的一个细节问题是搜索的边界，代码里有
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可以容易地写出动态规划算法。比如本题的图就很规则，按照集合的大小（递减）分出不同层次，逐层求解。
正文到此结束
热门推荐
相关文章
近期评论
-
666
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
