AtCoder Beginner Contest 296-JZTXT

E Transition Game

拓扑跑环。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }
    vector<int> deg(n);
    vector<vector<int>> g(n);
    for (int i = 0; i < n; i++) {
        g[i].push_back(a[i]);
        g[a[i]].push_back(i);
        deg[a[i]]++;
        deg[i]++;
    }
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (deg[i] == 1) {
            q.push(i);
        }
    }
    int ans = n;
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        ans--;
        for (auto nex : g[cur]) {
            if (--deg[nex] == 1) {
                q.push(nex);
            }
        }
    }
    cout << ans << '\n';

    return 0;   
}

F Simultaneous Swap

graph TD; A[1 2 3 4 5 6 7 8 7 8 5 6 4 3 1 2]--操作一次-->B[6 2 3 4 5 1 7 8 7 8 5 3 4 6 1 2]

graph TD; A[6 2 3 4 5 1 7 8 7 8 5 3 4 6 1 2]--操作一次-->B[1 2 3 4 5 6 7 8 7 8 5 3 4 2 1 6]

graph TD; A[1 2 3 4 5 6 7 8 7 8 5 6 4 3 1 2]--操作两次-->B[1 2 3 4 5 6 7 8 7 8 5 3 4 2 1 6]

操作两次相当于选择 \(i,j,k\) \((i<j<k)\)，令 \(b_{i},b_{j},b_{k}=b_{j},b_{k},b_{i}\)。

那么：

graph TD; A[7 8 5 6 4 3 1 2]--操作两次-->B[7 8 5 3 4 2 1 6]

graph TD; A[7 8 5 3 4 2 1 6]--操作两次-->B[7 3 5 2 4 8 1 6]

graph TD; A[7 8 5 6 4 3 1 2]--操作四次-->B[7 3 5 2 4 8 1 6]

可以发现操作四次就是选择 \(i,j,x,y\) \((i<j<x<y)\)，令 \(b_{i},b_{j}=b_{j},b_{i}\)，\(b_{x},b_{y}=b_{y},b_{x}\)。

我们可以发现若 \(b\) 中存在两个元素相同，那么我们就可以通过四次操作交换 \(b\) 任意两个位置的元素。
并且当 \(a,b\) 逆序对数量同奇偶则一定 Yes，并且最后把 \(a,b\) 都还原成正序。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

template <typename T>
struct Fenwick {
    int n;
    vector<T> a;
    Fenwick(const int n = 0) : n(n), a(n, T()) {}
    void modify(int p, T x) {
        for (p += 1; p <= n; p += p & -p) {
            a[p - 1] += x;
        }
    }
    T get(int p) {
        T res = T();
        for ( ; p > 0; p -= p & -p) {
            res += a[p - 1];
        }
        return res;
    }
    T sum(int l, int r) { // [l, r)
        return get(r) - get(l);
    }
};

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

    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        b[i]--;
    } 

    auto c = a; 
    auto d = b; 
    sort(c.begin(), c.end());
    sort(d.begin(), d.end());

    if (c != d) {
        cout << "No\n";
        return 0;
    }

    for (int i = 0; i < n - 1; i++) {
        if (c[i] == c[i + 1]) {
            cout << "Yes\n";
            return 0;
        }
    }
    
    auto get = [&](const vector<int> &a) {
        Fenwick<i64> f(n);
        i64 res = 0;
        for (int i = 0; i < n; i++) {
            res += f.get(a[i]);
            f.modify(a[i], 1);
        }
        return res;
    };

    if (get(a) % 2 == get(b) % 2) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }

    return 0;   
}

G Polygon and Points

计算几何，\(O(\log n)\) 求点与多边形位置关系。

C++ Code

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

using Real = i64;
using Point = complex<Real>;

#define x real
#define y imag

constexpr Real eps = 0;

int sign(const Real &x) {
    return x < -eps ? -1 : x > eps ? 1 : 0;
}

Real cross(const Point &a, const Point &b) {
    return (conj(a) * b).y();
}

Real dot(const Point &a, const Point &b) {
    return (conj(a) * b).x();
}

struct Line {
    Point a, b;
    Line(const Point &a, const Point &b) : a(a), b(b) {}
};

struct Segment : Line {
    Segment() = default;
    using Line::Line;
    Real len() const {
        return abs(a - b);
    }
};

bool onSegment(const Point &p, const Segment &s) {
    return sign(cross(p - s.a, s.b - s.a)) == 0 && sign(dot(p - s.a, p - s.b)) <= 0;
}

using Polygon = vector<Point>;

// left ： 1, right : -1
int onLeft(const Point &p, const Line &l) {
    return sign(cross(l.b - l.a, p - l.a));
}

// ON : -1, OUT : 0, IN : 1
int contains(const Point &p, const Polygon &g) {
    if (g.size() == 1) {
        return p == g[0] ? -1 : 0;
    }
    if (g.size() == 2) {
        return onSegment(p, Segment(g[0], g[1]));
    }
    if (p == g[0]) {
        return -1;
    }
    if (onLeft(p, Segment(g[0], g[1])) == -1 || onLeft(p, Segment(g[0], g.back())) == 1) {
        return 0;
    }
    const auto cmp = [&](const Point &u, const Point &v) { 
        return onLeft(v, Segment(g[0], u)) == 1; 
    };
    const size_t i = lower_bound(g.begin() + 1, g.end(), p, cmp) - g.begin();
    if (i == 1) {
        return onSegment(p, Segment(g[0], g[i])) ? -1 : 0;
    }
    if (i == g.size() - 1 && onSegment(p, Segment(g[0], g[i]))) {
        return -1;
    }
    if (onSegment(p, Segment(g[i - 1], g[i]))) {
        return -1;
    }
    return onLeft(p, Segment(g[i - 1], g[i])) > 0;
}

string ans[] = {"ON", "OUT", "IN"};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;

    Polygon a(n);
    for (int i = 0; i < n; i++) {
        i64 x, y;
        cin >> x >> y;
        a[i] = Point(x, y);
    }

    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        i64 x, y;
        cin >> x >> y;
        Point p(x, y);
        cout << ans[contains(p, a) + 1] << '\n';
    }

    return 0;
}