A. Dreamoon Likes Coloring
题目描述
有 \(n\) 个格子排成一行,每个格子初始没有颜色,进行 \(m\) 次操作,第 \(i\) 次操作有一个参数 \(l_i\),表示可以把 \([p_i, p_i + l_i - 1]\) 这个区间的格子染成颜色 \(i\),要求 \(p_i \geq 1, p_i + l_i - 1 \leq n\),如果一个格子被多次染色,以最后一次颜色为准。要求在最终序列中,每种颜色都出现过,并且每个格子都有颜色,试构造出 \(p\) 满足题目条件,无解输出 \(-1\)。
题解
我们有两个基本观察,如下:
- \(\sum_{i=1}^ml_i \geq n\),否则填不满所有格子。
- \(i + l_i - 1 \leq n\),这个是因为如果 \(i + l_i - 1 > n\),那么一个空序列在放入一个长度为 \(l_i\) 的区间之后,剩下的空格子不足 \(i - 1\),也就是不可能放下前面的 \(i - 1\) 种颜色。
在这两种情况都输出 -1 之后,我们可以构造地说明是一定有解的。
一些观察:上面的第一种情况其实对应着区间不相交的方案,而下面则对应 \(p_i = i\) 的方案,感性理解这两种是恰好相反的,只要结合起来就能构造出答案。
具体如下,我们先令 \(suf\) 表示 \(l\) 的后缀和,令 \(p_i = n - suf_i + 1\),也就是说从 n 倒着放,并且区间之间没有相交。
显然,这种方法存在问题,但是我们可以调整,具体的,找到第一个 \(i\) 使得 \(p_i \geq i\),对于 \(j < i\), 令 \(p_j = j\),剩下的不变,则满足条件。
证明分两方面,第一方面,我们证明每种颜色都是出现过的,这比较显然,因为对于颜色 \(j < i\),它必然在 \(j\) 这个位置上出现过,而后面的则由于区间两两不交,每个颜色显然出现过至少一次。
第二方面,我们证明每个格子都有颜色,由于在 \(i + 1\) 以及之后的部分是恰好把格子占满了,我们只需要证明在 \(p_i\) 和之前没有 “空白” 即可。
形式化地,就是要证明下式。
\begin{align}\label{eq1}
\max_{1 \leq j \leq i - 1} (j + l_j - 1) \geq n - suf_i + 1
\end{align}
左边就是说在满足 \(j \in [1, i - 1]\),都有 \(p_j = j\) 的情况下最右边的点,而右边就是 \(p_i\)。
当然,我们有一些条件,例如 \(n - suf_i + 1 \geq i\)。
但是这并不是重点,重点是说,对于任意的 \(j \in [1, i - 1]\),有 \(n - suf_j + 1 < j\)。
这是因为 \(i\) 是找到的第一个满足 \(n - suf_i + 1 \geq i\) 的位置,则它之前的自然不满足这个约束。
一个直接的想法是说我们直接考察位置 \(i - 1\)。
那么带入到 \((1)\) 式中,就是要证明
\begin{align}\label{eq2}
i - 3 \geq n - suf_{i - 1}
\end{align}
带入到条件中,我们有 \(n - suf_{i - 1} + 1 < i - 1\),即 \(n - suf_{i - 1} < i - 2\),则 \((2)\) 式显然成立,证毕。
标签:suf,geq,颜色,格子,题解,align,1329,CF,leq From: https://www.cnblogs.com/chengchunhao/p/16611368.html