nbhkdz.com冰点文库

杭州学军中学NOIP2011模拟赛DAY2-2011-10-5题解

时间:2012-11-25


NOIP2011 模拟赛题解
最大公约数
首先 可以排除所有 GCD(a,b)不等于 1 的数对 因为他们同除以公约数后 可以得到一样优的解 其次 可以排除在 辗转过程 中 出现 a<= b div 2 的情况 如果 b mod a =c 可以将 b 变成 a+c 可以得到一样优的解 并且 原来的 b 变小 则 可以将所有没被排除掉的数 表示成如下形式 a,b -> b-a,a ->….->1,x(经过 L 次) 对于 所有的 1,x 明显 x=2 得到的序列更优 所以只考虑这个序列 1,2 ->2,3 ->3,5 ->5,8 ->8,13…. 即 由 Fibonacci 数列 前后两项 所构成的序列 做法: 用高精度计算 fib 数列知道列尾数字大于 n 输出 倒数第二 和 倒数第三 项 即可

序列游戏
如果我们枚举 Gy,Nsk 翻转的位置,然后再进行计算,显然是 O(N^3)的。这个做法通过记录区间和能够非常容易的做到 O(N^2), 但如果要通过所有的测试数据还有一定困难。 因此我们接下来对这题 作一些研究。 显然的,假如 Gy 的决策已经确定了,Nsk 的决策是确定的。我 们猜想这之中有一定的单调性,但是显然 Nsk 的决策和 Gy 的决策构 不成单调关系。 事实上, 要处理原问题, 我们只需要解决下面的两个子问题即可。 1.Gy 和 Nsk 的选择集合严格不相交。 2.Gy 和 Nsk 的选择集合存在相交部分。 这两个子问题都是可以做的。我们先来考虑第一个子问题。如果 Gy 和 Nsk 的选择集合严格不相交的话怎么处理。显然这个问题可以 通过记录后缀最小值单调处理,时间复杂度 O(N)。 如果 Gy 和 Nsk 的选择集合存在相交部分, 假设 Gy 当前决策是 i, Nsk 相对的最优决策是 j(j<=i),我们记这样的决策为(i,j)。 显然 Nsk 的最优决策不会在[0,j-1],因为这与(i,j)为 Nsk 在 i 处 的最优决策相矛盾。同理最优决策不会在[j+1,i]。因此,当 Gy 的决 策由 i 变成 i+1 时,实际上 Nsk 下一步只有两种决策的可能 1.Nsk 的决策仍为 j; 2.Nsk 的决策变为 i+1。 我们只要求出这两种决策的最优值并记录下来即可, 可以在 O(N)

的时间内解决。这样一来,在 O(N)的时间内,我们可以求出两种情 况下 Nsk 的最优决策取 min 即可,然后再在全局取 max 即为答案, 完美解决了这个问题。 最终时间复杂度为 O(N), 空间复杂度为 O(N), C/C++选手可能需要读入优化才能通过此题。

纪念品
根据题目给的条件,我们首先可以算出一些块的总和。一个显而 易见的结论是,对于一个块,如果它没有任意一个节点被覆盖到, 花 费为 0;如果全部被覆盖到,花费为它的代价;否则花费最大值为它 的代价,最小值为 0。 对于每个询问的两个点 x 和 y,不妨设它们的 LCA 为 z。假如我 们能够预处理出每个点到根这条链上的权值,设第 i 个点的预处理权 值为 Si, i 个点所属块的价值为 Vi。 第 由于最大值和最小值是独立的, 我们可以分开来考虑。先考虑最大值。 (注意最大值和最小值对应的 Si 是不同的) 最大值的特点是: 只要一个块有一个元素被路径覆盖了, 这个块的权值就要加入答案中。可以发现,z 上方的点被重复算了 2 次,z 被多算了 1 次,因此答案就是 Sx+Sy-2*Sz+Vz。再考虑最小值。 最小值的特点是:只有一个块中所有元素都被路径覆盖,这个块的权 值才能加入答案中。我们进行分情况讨论: 1.z 所属的块不是一条链。显然答案即为 Sx+Sy-2*Sz。 2.z 所属块是一个点。此时答案为 Sx+Sy-2*Sz+Vz。 3.z 是链的端点。分三种情况讨论得到的答案均为 Sx+Sy-2*Sz。 4.z 是链的中间点。我们继续分情况讨论: (1)z 所在链两端点分别在 x 子树和 y 子树上并被 x 到 y 的路径 包含。此时答案为 Sx+Sy-2*Sz+Vz。 (2)z 所在链两端点分别在 x 子树和 y 子树上但不被 x 到 y 的路 径包含。此时答案为 Sx+Sy-2*Sz。

(3)z 所在链两端点一个在 x(或 y)子树上, 另一个在 z 的其它子 树上。此时答案为 Sx+Sy-2*Sz。 (4)z 所在链两端点一个在 x(或 y)子树上, 另一个在 z 到根的路 径上。此时答案为 Sx+Sy-2*Sz-Vz。 (5)z 所在链两端点均不在 x,y 子树上。答案为 Sx+Sy-2*Sz。

最后是刚才没有解决的预处理部分。 我们先处理出每个点在哪个 块内,记录块的大小信息,然后从根节点开始进行一遍 dfs,动态维 护每个块的大小信息来计算两个 S 数组即可。 总时间复杂度为 O(N)。 为了方便起见,标程的 LCA 使用了 O(NlogN)的写法。事实上上述分 类讨论仍然可以再简化。


赞助商链接