Solution Set【2024.1.13】-526互联

B. 山河入梦来

不难发现所求的其实就是该矩阵的行列式，考虑对矩阵进行高斯消元后求解。

我们考虑高斯消元的过程：从左到右枚举列，对于当前枚举的列，我们需要找到一个非零的行，使得该行的当前列的值为1，并且通过消元使得该列的其他行的值为0。

不难发现对于所有从当前列开始的连续的 \(1\) 中，取最短的一个即可，因此可以使用堆来维护连续的 \(1\)，每次需要取的时候取最短的即可，对于其他的行，我们模拟高斯消元的过程即可。

Code

%:pragma GCC optimize("Ofast")
%:pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/tree_policy.hpp>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::pair<valueType, valueType> ValuePair;
typedef std::vector<ValuePair> PairVector;
//typedef __gnu_pbds::priority_queue<ValuePair, std::greater<>, __gnu_pbds::pairing_heap_tag> PairQueue;
typedef std::priority_queue<ValuePair, std::vector<ValuePair>, std::greater<>> PairQueue;
typedef std::vector<PairQueue> QueueVector;

namespace IO {
    constexpr valueType SIZE = (1 << 25);
    char ibuf[SIZE], *pi = ibuf;

    inline valueType rnt() {
        valueType x = 0;
        char c = *pi++;
        while (!isdigit(c))
            c = *pi++;
        while (isdigit(c))
            x = (x << 3) + (x << 1) + (c ^ 48), c = *pi++;
        return x;
    }

    char obuf[SIZE >> 10], *po = obuf;

    inline void wnt(valueType x) {
        static valueType sta[35];
        valueType top = 0;
        do {
            sta[top++] = x % 10, x /= 10;
        } while (x);
        while (top)
            *po++ = sta[--top] + '0';
    }

    inline void wts(char const *s) {
        while (*s)
            *po++ = *s++;

        *po++ = '\n';
    }

}// namespace IO

template<typename T, class Operator = std::plus<>>
class TreeArray {
private:
    T N;
    std::vector<T> tree;
    Operator op;

    static T lowbit(T x) {
        return x & (-x);
    }

public:
    TreeArray() = default;

    explicit TreeArray(T n, T initValue = 0) : N(n), tree(n + 1, initValue) {}

    void insert(T pos, T value) {
#ifdef _UU_DEBUG
        if (pos <= 0 || pos > N)
            throw std::out_of_range("TreeArray::insert() : pos out of range");
#endif

        while (pos <= N) {
            tree[pos] = op(tree[pos], value);

            pos += lowbit(pos);
        }
    }

    T query(T pos) {
#ifdef _UU_DEBUG
        if (pos <= 0 || pos > N)
            throw std::out_of_range("TreeArray::query() : pos out of range");
#endif

        T result = 0;

        while (pos > 0) {
            result = op(result, tree[pos]);

            pos -= lowbit(pos);
        }

        return result;
    }
};

valueType GetInverseCount(valueType N, ValueVector const &P) {
    valueType result = 0;
    TreeArray<valueType> tree(N);

    for (valueType i = 1; i <= N; i++) {
        result += i - 1 - tree.query(P[i]);

        tree.insert(P[i], 1);
    }

    return result;
}

valueType Inverse(valueType N, ValueVector const &P) {// Computes the reverse logarithm of a permutation of order N
    __gnu_pbds::tree<valueType, __gnu_pbds::null_type, std::greater<>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> T;

    valueType result = 0;

    for (valueType i = 1; i <= N; ++i) {
        result += (valueType) T.order_of_key(P[i]);

        T.insert(P[i]);
    }

    return result;
}

std::pair<bool, ValueVector> solve(valueType N, PairVector const &A) {
    ValueVector P(N + 2, 0);

    QueueVector Q(N + 2);

    for (valueType i = 1; i <= N; ++i)
        Q[A[i].first].push(ValuePair(A[i].second, i));

    for (valueType i = 1; i <= N; ++i) {
        if (Q[i].empty())
            return std::make_pair(false, ValueVector(N + 1, 0));

        auto const [r, id] = Q[i].top();

        Q[i].pop();

        P[id] = i;

        if (!Q[i].empty() && Q[i].top().first == r)
            return std::make_pair(false, ValueVector(N + 1, 0));

        if (Q[r + 1].size() < Q[i].size())
            std::swap(Q[r + 1], Q[i]);

        while (!Q[i].empty()) {
            Q[r + 1].push(Q[i].top());
            Q[i].pop();
        }
    }

    return std::make_pair(true, P);
}

void solve() {
    // auto begin = std::chrono::steady_clock::now();

    valueType N;

    // std::cin >> N;
    N = IO::rnt();

    PairVector Y(N + 1);

    for (valueType i = 1; i <= N; ++i) {
        // std::cin >> Y[i].first >> Y[i].second;

        Y[i].first = IO::rnt();
        Y[i].second = IO::rnt();
    }

    auto const [ok, P] = solve(N, Y);

    // std::cerr << "solve: " << std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - begin).count() << std::endl;

    if (!ok) {
        // std::cout << "tie" << std::endl;
        IO::wts("tie");

        return;
    }

    valueType const Inv = GetInverseCount(N, P);

    // std::cerr << "solve Inverse : " << std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - begin).count() << std::endl;

    // std::cout << (Inv & 1 ? "xx" : "pp") << std::endl;
    IO::wts((Inv & 1 ? "xx" : "pp"));
}

int main() {
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(nullptr);
    // std::cout.tie(nullptr);

#ifndef LOCAL_STDIO
    freopen("river.in", "r", stdin);
    freopen("river.out", "w", stdout);
#endif

    fread(IO::ibuf, 1, IO::SIZE, stdin);

    valueType T;

    // std::cin >> T;
    T = IO::rnt();

    for (valueType testcase = 0; testcase < T; ++testcase)
        solve();

    fwrite(IO::obuf, 1, IO::po - IO::obuf, stdout);

    return 0;
}

发现除 \(x\) 外，每种地图可以使用的赛车类型数量均为 \(2\)，不难转化为 2-sat 问题，具体的，对于限制 \(\left(i, h_i, j, h_j\right)\)，设 \(h_i^{\prime}\) 表示第 \(i\) 场除 \(h_i\) 外可以使用的赛车类型，\(h_j^{\prime}\) 同理，那么我们可按 \(h_i\) 和 \(h_j\) 是否可以使用来处理限制：

若第 \(i\) 场不能使用 \(h_i\)，那么该限制无需处理。
若第 \(j\) 场不能使用 \(h_j\)，那么这也就意味着第 \(i\) 场不能使用 \(h_i\)。因此建边 \(h_i \rightarrow h_i^{\prime}\)。
否则意味着第 \(i\) 场可以使用 \(h_i\)，且第 \(j\) 场可以使用 \(h_j\)，那么建边 \(h_i \rightarrow h_j\)，\(h_j^{\prime} \rightarrow h_i^{\prime}\)。

考虑如何处理 \(x\)，考虑对于每个 \(x\)，为其制定一种地图。不妨假设最终的赛车方案是确定的，那么可以每种赛车对应了两张可以使用的地图，因此若我们随机确定 \(x\) 的地图类型，有解的概率为 \(\dfrac{2^d}{3^d}\)，因为有 \(d \le 8\)，因此正确率不低于 \(3 \%\)，多次随机即可通过。

description solution gdkoi 2024

禁忌solution魔法set

526互联

Solution Set【2024.1.13】

B. 山河入梦来

[NOI2017] 游戏