TIOJ 1151：6.下棋問題

TIOJ 1151：6.下棋問題

題目大意：兩個人輪流下棋，每次下在 $(x,y)$，下一次棋可以得到的分數是滿足 $i<j$，$(x_i,y_i)$ 和 $(x_j,y_j)$ 中間沒有任何棋子的 $(i,j)$ 數量。問兩人最後總分。

解法：首先我有參考這一篇。可以知道，如果以現在的棋子當原點，那四個象限的答案，只可能是 $x$ 座標遞增或遞減，$y$ 座標對應遞增或遞減，那麼每次可以先以 $x$ 座標排列好，再對 $y$ 座標掃過去，就可以求得在這一步棋多出來的對數。但是有可能把棋子下到其他兩顆棋子中間了，就必須扣除答案，所以可以另外紀錄目前有哪些數對是滿足答案的，對一三、二四象限掃，移除一些答案，回傳值再扣掉移除的數目。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 5005;
const int INF = 2e9;

struct Point {
    int x, y, id;
} p[SIZE];

int n;
long long A, B, sum;
bool is[SIZE][SIZE];
vector<int> id[5];

int cal (int x, int y, int siz, int pos) {
    fill (id, id + 5, vector<int>());
    int mx = -INF, mn = INF, re;
    FOR (i, pos + 1, siz) {
        if (p[i].y > y && p[i].y < mn) {
            id[1].pb (p[i].id);
            mn = p[i].y;
            is[p[i].id][siz] = is[siz][p[i].id] = 1;
        }
        if (p[i].y < y && p[i].y > mx) {
            id[4].pb (p[i].id);
            mx = p[i].y;
            is[p[i].id][siz] = is[siz][p[i].id] = 1;
        }
    }
    mx = -INF, mn = INF;
    for (int i = pos - 1; i >= 1; i--) {
        if (p[i].y > y && p[i].y < mn) {
            id[2].pb (p[i].id);
            mn = p[i].y;
            is[p[i].id][siz] = is[siz][p[i].id] = 1;
        }
        if (p[i].y < y && p[i].y > mx) {
            id[3].pb (p[i].id);
            mx = p[i].y;
            is[p[i].id][siz] = is[siz][p[i].id] = 1;
        }
    }
    re = id[1].size() + id[2].size() + id[3].size() + id[4].size();
    for (int a : id[1]) {
        for (int b : id[3]) {
            if (is[a][b]) {
                re--;
                is[a][b] = is[b][a] = 0;
            }
        }
    }
    for (int a : id[2]) {
        for (int b : id[4]) {
            if (is[a][b]) {
                re--;
                is[a][b] = is[b][a] = 0;
            }
        }
    }
    return re;
}

void solve() {
    cin >> n;
    FOR (i, 1, n) {
        int x, y, pos = i;
        cin >> x >> y;
        FOR (j, 1, i - 1) {
            if (p[j].x > x) {
                pos = j;
                break;
            }
        }
        for (int j = i; j > pos; j--) {
            p[j] = p[j - 1];
        }
        p[pos] = {x, y, i};
        sum += cal (x, y, i, pos);
        if (i & 1) {
            A += sum;
        } else {
            B += sum;
        }
    }
    cout << A << ' ' << B << '\n';
}

int main() {
    Waimai;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！