[USACO24JAN] Cowmpetency S 题解

vegetable_king · 2024-02-05 16:50:15 · 题解

可能更好的阅读体验

一个不需要任何数据结构，代码好写，而且时间复杂度严格 O(n) 的解法！

下文中令 a 为题目中的 c 序列。

考虑一对限制 (x, y) 的本质是什么。根据题意得知，\max_{i = 1}^x a_i < a_y，且 a_k \le \max_{i = 1}^x a_i(x < k < y)，于是可以推出 \max_{i = 1}^{y - 1} a_i < a_y，也就是说。a_k(x < k < y) 一定不是严格前缀最大值，而 a_y 一定是严格前缀最大值。

于是我们可以 O(n) 求出数组 b，b_i = -1/0/1，表示 a_i 一定不是 / 不一定是 / 一定是 前缀最大值，或者推出矛盾（即一个位置同时应该是 -1, 1 的情况），判无解即可。

考虑构造。首先我们考虑 a 全都不确定的情况，此时是简单的，b_i = 1 时令 a_i = \max_{j = 1}^{i - 1} a_j + 1，否则令 a_i = 1 即可。

如果当前的 a_i 确定了，那我们考虑判断合不合法。

1. 如果 b_i = 1 且 a_i \le \max_{j = 1}^{i - 1} a_j 则一定无解，因为我们在最小化字典序的同时最小化了前缀 \max。
2. 如果 b_i = -1 且 a_i > \max_{j = 1}^{i - 1}，则我们考虑往前找到一个最大的 p 使得 a_p 未确定且 b_i \ne -1，令 a_p = a_i 来满足 a_i 的限制。如果找不到这样的 p 那么显然无解；调整后 a_p 可能会与 [p + 1, i - 1] 中的一些位置的限制冲突，此时也一定无解。因为冲突的位置 o 一定满足 a_o 确定了，且 b_o = 1，而这样的位置相当于给前缀 \max 设置了上界。

于是我们可以做到 O(n) 构造并且判定是否有解。代码在这里。