[HNOI 2013] 旅行 (数学)

感觉此题难啊,数学还是太渣了,看了半天的题解才算明白了点儿。

题目大意

给一个长度为n且仅由1和-1组成的序列ai, i = 1, 2, ..., n,每个位置都有另一个值vi,要求用某种方案将序列划分为m(0 < m < n)个非空连续子序列,使得所有子序列中和的最大绝对值最小,并且在所有满足上述条件的方案中划分位置的v[i]序列字典序最小。

猜想及证明

[HNOI 2013] 旅行 (数学)[HNOI 2013] 旅行 (数学)

记题目中说的和的最大绝对值的最小值为[HNOI 2013] 旅行 (数学)

有如下几个结论

  1. [HNOI 2013] 旅行 (数学)并且[HNOI 2013] 旅行 (数学),则[HNOI 2013] 旅行 (数学)
  2. [HNOI 2013] 旅行 (数学)并且[HNOI 2013] 旅行 (数学),则[HNOI 2013] 旅行 (数学)
  3. [HNOI 2013] 旅行 (数学),则[HNOI 2013] 旅行 (数学)

证明:

  • 第一条结论是显然的
  • 对于第二条结论,首先可以肯定[HNOI 2013] 旅行 (数学),所以[HNOI 2013] 旅行 (数学)。我们要证明对于和为零长度为n的序列,始终存在方案将其划分为i段(i = 1, 2,..., n),且每一段的和都是-1, 0, 1中一个(即[HNOI 2013] 旅行 (数学))。这样我们就能得到[HNOI 2013] 旅行 (数学)。证明方法如下:
    • 考虑将序列划分为n段,显然这是满足条件的,因为每一段的和都为1或-1
    • 现在考虑将这n段中相邻的进行合并,由于整个序列的和为0,故一定能找到一对相邻的段,它们一个的和为-1,另一个为1,令它们合并后,新的段和为0,得到划分为n - 1段的方案
    • 继续执行合并。由于整个序列和为0,每一段的和都为-1, 0, 1,所以只要序列中存在1,就一定存在-1,且始终存在相邻或中间仅隔着0的1和-1,且0可以任意合并,所以可以一直合并下去,直到最后仅剩下一个0,即为合并成一段的方案
  • 对于第三条结论,如果[HNOI 2013] 旅行 (数学),我们可以肯定的是[HNOI 2013] 旅行 (数学)。原因是如果每一段的和的绝对值都小于[HNOI 2013] 旅行 (数学),整个序列的和不可能为[HNOI 2013] 旅行 (数学)。下面我们证明可以构造出[HNOI 2013] 旅行 (数学)的方案。
    • 如果[HNOI 2013] 旅行 (数学),相当于把一堆大小为[HNOI 2013] 旅行 (数学)的物品分成[HNOI 2013] 旅行 (数学)堆,只要保证尽量平均即可
    • 如果[HNOI 2013] 旅行 (数学),由于需要保证每一段非空,我们要换一种方式考虑。考虑先取出[HNOI 2013] 旅行 (数学)个位置,可以做到每一段和的绝对值都为1,也就是说,每一段中可一取出一个数使得剩余部分和为0,这就又变成上面的问题,已经证明对这些部分继续划分[HNOI 2013] 旅行 (数学),所以[HNOI 2013] 旅行 (数学)

计算方案

这题思维难度很大,就算上面的结论猜到了,敢用了,想不出下面计算字典序最小的方案的算法也是没有用的。

对于[HNOI 2013] 旅行 (数学)并且[HNOI 2013] 旅行 (数学)的情况,由于有且仅有前缀和为0的位置可选,我们仅需要维护一个单调队列,对第i个划分位置入队直到后面的前缀和为0的位置不足时为止,然后取出队中最小的即可。

对于其他情形,我们当前选择的位置受上一个位置限制。假设第[HNOI 2013] 旅行 (数学)个位置为[HNOI 2013] 旅行 (数学),给定另一个位置[HNOI 2013] 旅行 (数学)[HNOI 2013] 旅行 (数学)可以作为第[HNOI 2013] 旅行 (数学)个位置当且仅当

  [HNOI 2013] 旅行 (数学)

这个就有些难。我们对每个S值维护一个单调队列,得到第[HNOI 2013] 旅行 (数学)个位置[HNOI 2013] 旅行 (数学)后,我们访问所有S值在[HNOI 2013] 旅行 (数学)中的单调队列。

看起来是不是很暴力?似乎又要MLE又要TLE的样子?让我们仔细分析空间和时间复杂度,由于我们所有位置都最多入队一次,故空间复杂度为[HNOI 2013] 旅行 (数学)。因为[HNOI 2013] 旅行 (数学),总共选m次,故总的时间复杂度为[HNOI 2013] 旅行 (数学)

[HNOI 2013] 旅行 (数学)

上一篇:成绩转换


下一篇:[转】:HTTP请求流程(一)----流程简介