UOJ NOI Round #10 Day1 A 和 B

A. 麦田

一个位置在第 \(k\) 次时被操作了，则它相邻的数至少有一个在 \(k-1\) 次时被操作，且每个数只会被操作 \(1\) 次。记录一下一个数在 \(l\le L,r\ge R\) 时会被操作。

B. 分披萨

Part 0

每段不同元素个数相同，假设为 \(D\)，对于不同的 \(D\) 计算合法序列数量。

考虑对分段方案计数，对于一个序列，将其贡献记在断点的字典序最小的分段方案上。

考虑对于一个段，我们把它分为 \(4\) 种类型：（当前段为 \(A\)，下一段为 \(B\)（若 \(A\) 为最后一段，则 \(B=\varnothing\)），\(A\) 中最后一个元素为 \(x\)）

  • 11 型：\(A\) 中有大于等于 \(2\) 个 \(x\)，\(B\) 中有 \(x\)。
  • 10 型：\(A\) 中有大于等于 \(2\) 个 \(x\)，\(B\) 中没有 \(x\)。
  • 01 型：\(A\) 中只有 \(1\) 个 \(x\)，\(B\) 中有 \(x\)。
  • 00 型：\(A\) 中只有 \(1\) 个 \(x\)，\(B\) 中没有 \(x\)。

显然地，11 型 是不能出现的，因为此时可以把分割 \(A,B\) 的断点往左移动一格。

Part 1

将序列的段分为两个部分（“部分一”和“部分二”），部分二的第一个段是整个序列第一个 10 型 的段。

对于部分一：显然已经是字典序最小的了。

对于部分二：

结论：部分二中只要没有 01 型的段，整个划分的断点的字典序就是最小的。

结论证明：

  • 必要性，如果段 \(A\) 是部分二中的第一个 01 型段，则可以将它之前的（包含它自己）部分二中的所有段的右端点，向左移动一格。

  • 充分性，容易发现将部分二中的某个点往左移后，之后的点都要往左移，不合法。

也即是说，任意一个合法的序列都可以唯一地划分为 一些 01 型和 00 型的段，拼上一些以 10 开头的 10 型段和 00 型段。

Part 2

直接 DP 即可，复杂度 \(O(n^4)\)。