[Codeforces1204D] Kirk and a Binary String

题解

update: 感觉我做麻烦了,题解做法好简单。这篇 blog 就丢这吧…..感觉没什么错误。

如果只把 \(0\) 变成 \(1\) 而不把 \(1\) 变成 \(0\),会导致 \(0\) 的个数减少,还不如不改变原序列。

如果既出现把 \(0\) 变成 \(1\) 也出现把 \(1\) 变成 \(0\),设某一个把 \(0\) 变成 \(1\) 的位置为 \(p_1\),某一个把 \(1\) 变成 \(0\) 的位置为 \(p_2\)

不妨设 \(p_1 < p_2\)。(如果 \(p_1 > p_2\),交换原序列和新序列就和一种 \(p_1 < p_2\) 的情况等价了)

\(f[l,r]\) 表示原序列上 \([l,r]\) 中最长不降子序列长度,\(g[l,r]\) 表示新序列上 \([l,r]\) 中最长不降子序列长度。

定义 \(f[l,r] = g[l,r] = 0(l > r)\)

那么 \(f[p_1,p_2] = f[p_1+1, p_2-1]+2 \Rightarrow g[p_1,p_2] = g[p_1+1,p_2-1]+2\)

因此新序列上 \([p_1,p_2]\) 中的最长不降子序列必然要包含 \(p_1\)\(p_2\),但是新序列上 \(p_1\) 位置为 \(1\)\(p_2\) 位置为 \(0\),这是不可能的。

因此,只会出现把 \(1\) 变成 \(0\) 的位置,不会出现把 \(0\) 变成 \(1\) 的位置。

考虑把一个位置在原序列左端或左边不为 \(1\)\(1\) 变成 \(0\),不对任意区间内的最长不降子序列产生影响的条件。

假设这个位置是 \(p\)。分两种情况讨论:

  1. \(p < n\) 且位置 \(p+1\) 上的是 \(1\).
  2. \(p = n\) 或位置 \(p+1\) 上的是 \(0\).

先看第一种情况。把位置 \(p\) 上的 \(1\) 变成 \(0\) 看作新序列(用 \(g[l,r]\) 描述新序列上的最长不降子序列)。对于任意的 \(i < p\)\(f[i,p] = f[i,p-1] + 1 \Rightarrow g[i,p] = g[i,p-1] + 1\),而新序列上位置 \(p\) 上的是 \(0\),这说明 \([i,p-1]\) 存在结尾为 \(0\) 的最长不降子序列,即 \([i,p-1]\) 的最长不降子序列等于 \([i, p-1]\)\(0\) 的个数。可以证明这个条件对任意的 \(i < p\) 都成立的充要条件为对于任意的 \(i < p\)\([i,p-1]\)\(0\) 的个数不少于 \(1\) 的个数:必要性是显然的,只需证充分性,假设 \([i, p-1]\) 的最长不降子序列大于 \(0\) 的个数,任取一个 \([i,p-1]\) 的最长不降子序列,它必然包含一个 \(1\),设第一个 \(1\) 位置为 \(k\),那么这个子序列 \(k\) 之前的元素再拼上 \([k,p-1]\) 中所有的 \(0\) 必然是一个全 \(0\) 的不会更短的子序列(因为 \([k,p-1]\)\(0\) 的个数不少于 \(1\) 的个数),这与不存在全为 \(0\) 的不降子序列矛盾。不难验证这也是第一种情况中能把 \(p\) 上的数变为 \(0\) 的充要条件。

第二种情况显然也必须要满足第一种情况的条件。除此之外,由于位置 \(p+1\) 上的是 \(0\),还需满足对于任意的 \(i > p\)\([p+1,i]\)\(1\) 的个数不少于 \(0\) 的个数(与第一种情况的证明类似,详细过程就不写了)。

从左往右贪心,对于一个位置,如果它是 \(1\),且能够保持任意区间最长不降子序列长度不变地变为 \(0\),就把它变成 \(0\)。不难证明这种贪心是正确的,详细证明这里不写了。(提示:考虑最优解中 \(1\rightarrow0\) 的最小位置)

判断是否存在前缀 / 后缀 \(0\) 的个数多于 / 少于 \(1\) 的个数,可以通过计算每个前缀中 \(0\) 的个数减 \(1\) 的个数很容易地处理。