题解 04

开学第一篇题解。

CF 1481 C Fence Painting

有一排长为 $n$ 的栅栏，每块木板上的颜色由 $a_i$ 给出。要把这排栅栏漆成另一个给定的的颜色序列 $b_i$。涂漆序列长度为 $m$，每个元素 $c_i$ 代表可以将任意一块木板漆成该颜色。涂漆序列的顺序不可变。
求能否完成任务，能则给出一种指派每个 $c_i$ 的方案。
$1\leq n, m\leq 10^5, 1\leq a_i, b_i, c_i\leq 10^5$

首先发现涂漆序列的最后一个元素（原题里是最后一个到的油漆工）是很重要的，如果它的颜色不在要求的结果序列 $b_i$ 里，那么后面将不会有覆盖它的颜色，则不可能完成任务。反之，它也可以覆盖那些不需要的颜色。我们可以先决定用它盖住某个位置，再把之前的、不需要的颜色都上到那里，而需要的颜色直接对应分配，就可以构造出答案。由于是针对涂漆序列的构造，需要检查一遍是否有漏涂之类的情况。

需要使用 map 来存放待修改的木板与颜色的关系，以减少查询时间。键值对可以是 <待修改的颜色, 对应颜色待修改的木板编号>。

CF 1491 B Minimal Cost

一个 $n$ 行 $10^6 + 2$ 列的点阵，每行恰有一个结点存在障碍，不可经过，且障碍不在第一列或最后一列。每个障碍可花费 $u$ 移动到上下邻近的点，或花费 $v$ 左右移动。对任意的障碍分布，显然存在移动障碍的方式，使得从第一行第一个结点出发，到达最后一行最后一个结点。
给出每行障碍结点的位置，求最小的移动代价。
$2\leq n\leq 100, 1\leq u, v\leq 10^9$

思维题。由于头尾两列保证畅通，可以横着看整个点阵，发现像是一面“墙”，只要有一个地方的障碍位置差大于 1，就可以不移动其他障碍地渗过去。这也是最小的情况，其他情况的转化目标。

对于必须移动的情况，有两种。

1. 障碍排成一列。至少动两步，则选最小代价即可。
2. 障碍凹凸有致，则随便移开一个位置就可以，取最小。

CF 1491 C Pekora and Trampoline

有一列共 $n$ 个跳台，每个跳台拥有一个弹力 $S_i$。Pekora 从任一个跳台 $i$ 起跳，可以跳到第 $i + S_i$ 个跳台，且原跳台的弹力减少 $1$。弹力不会小于 $1$，于是从任何跳台开始，Pekora 总能到达某个大于 $n$ 的位置，称之为一趟。Pekora 想让所有跳台的弹力都变成 $1$。
给定各跳台的弹力分布，求 Pekora 所需要的最小趟数。
$1\leq n \leq 5000, 1\leq S_i\leq 10^9$

模拟题。

对每个非 1 的跳台，如果前面的跳台都是 1，则必有若干趟以它开始，直到把它削成 1。开一个数组记录每个跳台被踩了多少次，或者直接在原数组上减，每趟一直做到末尾。

上面这个解法会超时。

观察一下可以发现，对于每一个要被削成 1 的跳台，无论从哪里到达它，下一步落到的区间是固定的，即从 $i + 2$ 到 $i + S_i$。那么，只需要记录当前跳台和后面一步的一段跳台即可，向后传递一次。

CF 1491 D Zookeeper and The Infinite Zoo

无穷多个结点，编号从 $1$ 开始。
从结点 $u$ 到 $u + v$ 存在一条有向边当且仅当 $u\& v = v$。$\&$ 为按位异或。
给定结点编号 $u$ 和 $v$，求 $u$ 到 $v$ 之间是否存在路。
$1\leq u, v\leq 2^30$

其实是 $v$ 的 1 位与 $u$ 对应位的重合关系，而且可以拆开，也就是把 $0111$ 变成 $1000$ 或者 $1101$ 这样的合并或者平移操作。有平移有合并，两个串里每个位置之前的 1 够多即可，是类似括号匹配的操作。

CF 1494 C 1D Sokoban

在一根整数数轴上玩推箱子。给出 $n$ 个箱子和 $m$ 个得分点的分布 $a_i$ 和 $b_i$，玩家从原点出发推动箱子。原点没有箱子。
求可以覆盖的最多得分点的个数。
$1\leq n, m\leq 2\cdot 10^5, -10^9\leq a_i, b_i\leq 10^9$

显然正负半轴只是两个一样的子问题。不妨考虑正半轴。

朴素的做法是把第一个箱子一步一步往绝对值大的方向推，记录遇到的箱子（即被推动的那些），然后数得分点。这个对于可能坐标比较大的情况显然会超时。

对于每个得分点上的箱子，如果它被推走了，一定会有箱子接着覆盖这得分点，直到第一个箱子经过它。那么，任何一个最优的方案都可以转化为第一个箱子恰好覆盖在一个得分点的情况。同时，这个性质使得问题可以通过双指针来解决。

那么我们可以枚举第一个箱子停下的位置，即所有的得分点。将所有箱子分成被推动的一段和未被推动的后缀考虑，用双指针维护前段的头尾，就能知道前段盖住了多少得分点；用 dp 事先维护每个箱子之后有多少个得分点被覆盖，两者相加取最大值即可。

核心代码如下：

long long seg(const vector<long long> &a,
              const vector<long long> &b) {
  // a: indices of boxes
  // b: indices of bonus locations
  // all in ascending order
  long long n, m;
  n = a.size(), m = b.size();
  vector<long long> suf(n + 1);
  // suf[i] = number of bonus boxes right of the i-th box
  long long r = m - 1;
  for (int i = n - 1; i >= 0; --i) {
    suf[i] = suf[i + 1];
    while (r >= 0 && b[r] > a[i]) --r;
    if (r >= 0 && b[r] == a[i]) ++suf[i];
  }
  long long ret, j;
  r = j = ret = 0;
  for (int l = 0; l < m; ++l) {
    // l: head INDEX of box segment
    //    also the 1st bonus location
    //    covered by the segment
    // r: tail INDEX of segment
    // j: first box INDEX after segment,
    //    (of the suffix)

    // count length of segment
    // as box segment is tight,
    // j is also the length
    while (j < n && a[j] <= b[l] + j) j++;
    // find the last bonus covered by the segment
    while (r < m && b[r] - b[l] < j) r++;
    ret = max(ret, r - l + suf[j]);
  }
  return ret;
}