【ZROI】普转提Day7题解

发表于

【ZROI】普转提Day7题解

A

注意到 $k_i \leq 100$，因此询问的区间长度若超过 $100$ 则一定有解，否则可以前缀和之后暴力检查是否有解。

B

枚举 $g$，$g$ 合法需要满足至少 $n-f$ 个位置合法。

而对于$a_i$ 合法，需要满足 $a_i \bmod g \leq k$。

  • 若 $g + 1\leq k$ 则不等式一定被满足。
  • 对于 $g+1 > k$，可以枚举 $g$ 的倍数 $pg$然后求有多少 $a_i$ 在 $[pg, pg+k]$，对其求和即可求出合法的 $a_i$ 的数量。

第二种情况可以用前缀和优化，且 $pg$ 的总和是 $O(n \log n)$ 级别的，因此可以通过本题。

C

因为交换的两个矩形一定不交，因此可以使用链表维护向左向右的下一个位置，修改的时候只需要修改上下和左右四条边界，时间复杂度为 $O(q(n+m))$。

D

考虑一个暴力 $dp$ 的做法：

设 $f_{s}$ 表示已经放下去 $s$ 这个集合的数是否合法，转移的时候枚举 $s$，考虑把 $i$ 放到当前序列的最左边或者最右边，在 $i$ 放下去的时候再考虑 $i$ 在两边的三元组的限制是否满足。

可以从上面的暴力做法得到一些启发：

  • 若从中间往两边塞数，则只关心中间已经有了哪些数。

再考虑三元组的限制如何满足。

设当前添加的数为 $x$，则与 $x$ 有关三元组可以分成两类（这里只考虑 $a, b$ 都已经出现的那些三元组）：

  • $(x, a, b)$ 或 $(a, b, x)$；
  • $(a, x, b)$。

对于第一类，记 $pos_i$ 表示 $i$ 的位置。若 $pos_a < pos_b$ 的三元组比 $pos_b < pos_a$ 的三元组更多，则 $x$ 放在左边即可；反之亦然。

可以发现如果没有第二类三元组，那么一定可以满足 $\lceil \frac{m}2 \rceil$ 条限制。

使得没有第二类三元组，即要求 $x$ 在 $a$ 或者 $b$ 之前加入序列，因为原排列存在，所以这个可以通过拓扑排序解决。