这个题,以我的智商,一开始没有很好的理解他的题解。之后看代码就毁了,代码里第一重循环示意的方向是反的,虽然只要轮数对了就好,不过这样代码阻碍理解题解,我看了好久才反应过来。
代码倒数第三行
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)
。
树状数组可以支持高效地查询和修改数列的前缀和。不过如果加入区间修改,问题就变复杂了。显然不能对区间逐个修改。
考虑对于仅在一个区间 [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可以表示为
-(l * x)
当查询位置a越过了r时,我们还要撤销x的效果
-x
。 这样就撤销了位置相关的修改,但要在bit0上加上常量增量,之前已经增加过 -(l * x)
(实际上是减少的意思)
r * x
更一般地,如果操作得到的结果可以用i的n次多项式表示,那么就可以使用n + 1个树状数组来进行维护了。
这里还是不明白,i的1次多项式的实际意义可以是区间修改,那么i的更高次多项式又可以具有怎样的意义呢?
计算DAG的最短路不需要使用Dijkstra算法,可以简单地通过DP求解。
对于这句话我的理解如下:
考虑Dijkstra算法所能求解范围——边权为正的图,DAG与其的区别在于前者可以有环路。
Dijkstra算法处理环的方法是应用问题的贪心性,每次选取从起点出发最近抵达的点,这个点不可能有其它更短的路径了。
DAG因为不存在环路,只要求解了一个点的所有前驱(没有环才有这个定义)的最短路,自然就可以求解这个点最短路。
所以对点的选取顺序要求变弱,只要按照(任一)拓扑序选点求行了。
另外,根据上下文,这里可能想强调的是具有规则分层结构的DAG,对于这种DAG可以容易地写出动态规划算法。比如本题的图就很规则,按照集合的大小(递减)分出不同层次,逐层求解。