CF 1329 题解

标签：suf geq 颜色 格子 题解 align 1329 CF leq

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\)。

题解

我们有两个基本观察，如下：

1. \(\sum_{i=1}^ml_i \geq n\)，否则填不满所有格子。
2. \(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)\) 式中，就是要证明

\[i - 2 + l_{i - 1} \geq n - suf_i + 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