[ARC104C] Fair Elevator 题解

题意

有 \(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

#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;
}