[ARC104C] Fair Elevator 题解
User_Unauthorized
2023-11-02 21:33:24
## 题意
有 $N$ 个区间 $[a_i,b_i](a_i<b_i)$，都是 $[1,2n]$ 内的整数且互不相同（$a_i\ne b_j,a_i\ne a_j,b_i\ne b_j$）。
现在给定一些 $a$ 和 $b$ 的值，剩下不知道的用 $-1$ 表示。问是否存在一种替换掉 $-1$ 的方案，使得：若两个区间**有交**，那么它们**长度相等**。
即 $\forall i,j,[a_i,b_i]\cap[a_j,b_j]\ne \varnothing\Rightarrow b_i-a_i=b_j-a_j$。
$N\le 100$。
## 题解
首先特判掉一些一定无解的情况，例如 $\exist i \neq j, a_i = a_j$，$a_i \ge b_i$ 等等。
可以发现若存在区间 $[l, r]$，设 $L = r - l$，那么对于任意 $l \ge i < r$，一定有区间 $[i, i + L]$ 存在。即整个区间 $[l, r + L - 1]$ 内的子区间内的元素都会被钦定值并且合法。
可以发现考察一个区间 $[l, r]$ 能否合法存在的复杂度为 $\mathcal{O}(N)$ 的。由于 $N$ 很小，故我们可以以 $\mathcal{O}(N^3)$ 处理出所有可以被钦定合法的区间。
根据上述分析，可以发现被钦定合法的区间一定补交，因此若一个区间没有被钦定合法，我们可以枚举其中的一个断点并判断左右两个区间是否可以合法，进而实现转移，复杂度为 $\mathcal{O}(N^3)$。
## Code
```cpp
#include <bits/stdc++.h>
typedef int valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<bool> bitset;
typedef std::vector<bitset> BitMatrix;
bool check(valueType N, ValueVector A, ValueVector B) {
bitset exist(2 * N + 1, false);
for (valueType i = 1; i <= N; ++i) {
if (A[i] != -1 && B[i] != -1 && A[i] >= B[i])
return false;
if (A[i] != -1) {
if (exist[A[i]])
return false;
exist[A[i]] = true;
}
if (B[i] != -1) {
if (exist[B[i]])
return false;
exist[B[i]] = true;
}
}
return true;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
valueType N;
std::cin >> N;
valueType const M = 2 * N;
ValueVector A(N + 1), B(N + 1);
for (valueType i = 1; i <= N; ++i)
std::cin >> A[i] >> B[i];
if (!check(N, A, B)) {
std::cout << "No" << std::endl;
return 0;
}
ValueVector left(M + 1, -1), right(M + 1, -1), belong(M + 1, -1);
bitset exist(M + 1, false);
for (valueType i = 1; i <= N; ++i) {
if (A[i] != -1) {
right[A[i]] = B[i];
exist[A[i]] = true;
belong[A[i]] = i;
}
if (B[i] != -1) {
left[B[i]] = A[i];
exist[B[i]] = true;
belong[B[i]] = i;
}
}
BitMatrix F(M + 1, bitset(M + 1, false));
for (valueType l = 1; l <= M; ++l) {
for (valueType r = l + 1; r <= M; ++r) {
valueType len = r - l;
if (r + len - 1 > M)
continue;
bool ok = true;
for (valueType i = l; i < r && ok; ++i) {
if (right[i] != -1 && right[i] != i + len)
ok = false;
if (left[i + len] != -1 && left[i + len] != i)
ok = false;
if (exist[i] && exist[i + len] && belong[i] != belong[i + len])
ok = false;
}
if (ok)
F[l][r + len - 1] = true;
}
}
for (valueType len = 1; len <= M; ++len) {
for (valueType l = 1; l + len <= M; ++l) {
valueType const r = l + len;
for (valueType mid = l + 1; mid < r; ++mid) {
if (F[l][mid] && F[mid + 1][r]) {
F[l][r] = true;
break;
}
}
}
}
if (F[1][M])
std::cout << "Yes" << std::endl;
else
std::cout << "No" << std::endl;
}
```