GDCPC集训D1补题

这套题是2024湖北icpc省赛题，五月一号集训没时间写，现在慢慢补。

B. Nana Likes Polygons

题意：在平面上有n个给定的点，求出最小的合法凸多边形面积。

已知三角形是凸多边形，所以显然可以得出最小的合法凸多边形一定是某个三角形。

#include <bits/stdc++.h>
using namespace std;

typedef pair<double, double> pdd;
pair<double, double> p[5010];

double area(pdd a, pdd b, pdd c) {
    pdd ab = make_pair(b.first - a.first, b.second - a.second);
    pdd ac = make_pair(c.first - a.first, c.second - a.second);
    if (ab.first * ac.second == ab.second * ac.first) return -1;
    return 0.5 * fabs(ab.first * ac.second - ab.second * ac.first);
}

void work() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> p[i].first >> p[i].second;
    double ans = 1e10;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            for (int k = j + 1; k <= n; k++) {
                double are = area(p[i], p[j], p[k]);
                if (are == -1) continue;
                ans = min(ans, are);
            }
        }
    }
    if (ans == 1e10) cout << "-1\n";
    else cout << ans << '\n';
}

int main() {
    int T = 1;
    cin >> T;
    while (T--)
        work();
    return 0;
}

L. LCMs

题意：规定两个整数间的距离为$lcm(x,y)$，给定$a$，$b$，求$a$到$b$的最短距离。（不能经过$1$）

进行分类讨论：

1. $a=b$，此时距离为$0$
2. $b$是$a$的倍数，此时距离为$b$
3. $a$和$b$互质，此时必然存在路径经过某个质数，为了距离最短，分别取$a$，$b$的最小质因数和$2$进行完全图建图，然后跑一遍最短路即可

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 10000000;
ll a, b;
bool noprime[N + 10];
vector<int> p;

void init() {
    for (int i = 2; i <= N; i++) {
        if (!noprime[i])
            p.emplace_back(i);
        for (auto x: p) {
            if (x * i > N) break;
            noprime[x * i] = 1;
            if (i % x == 0) break;
        }
    }
}

ll find(int x) {
    if (!noprime[x]) return x;
    for (auto prime: p)
        if (x % prime == 0)
            return prime;
    return -1;
}

void work() {
    cin >> a >> b;
    if (a == b) cout << "0\n";
    else if (b % a == 0) cout << b << '\n';
    else if (__gcd(a, b) != 1) cout << a + b << '\n';
    else {
        // gcd(a, b) == 1
        /*
        1 -> a
        2 -> ap
        3 -> 2
        4 -> bp
        5 -> b
        */
        ll dis[6][6];
        memset(dis, 0x3f, sizeof dis);
        ll ap = find(a), bp = find(b);
        dis[1][1] = a;
        dis[2][2] = ap;
        dis[3][3] = 2;
        dis[4][4] = bp;
        dis[5][5] = b;
        dis[1][2] = dis[2][1] = (a == ap) ? 0: a;
        dis[1][3] = dis[3][1] = (a == 2) ? 0: (a * 2 / __gcd(2ll, a));
        dis[1][4] = dis[4][1] = a * bp;
        dis[1][5] = dis[5][1] = a * b;
        dis[2][3] = dis[3][2] = (ap == 2) ? 0: 2 * ap;
        dis[2][4] = dis[4][2] = ap * bp;
        dis[2][5] = dis[5][2] = ap * b;
        dis[3][4] = dis[4][3] = (bp == 2) ? 0: 2 * bp;
        dis[3][5] = dis[5][3] = (b == 2) ? 0: (b * 2 / __gcd(2ll, b));
        dis[4][5] = dis[5][4] = (b == bp) ? 0: b;
        for (int i = 1; i <= 5; i++) {
            for (int j = 1; j <= 5; j++) {
                if (i == j) continue;
                for (int k = 1; k <= 5; k++) {
                    if (k == j || k == i) continue;
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
                }
            }
        }
        cout << dis[1][5] << '\n';
    }
    return ;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    init();
    int T = 1;
    cin >> T;
    while (T--)
        work();
    return 0;
}

G. Genshin Impact Startup Forbidden II

题意：下围棋，到谁下先计算谁，求每一步提了多少黑棋和白棋。

直接爆算即可，我写的bfs常数太大了，换dfs才行（不知道为什么）

#include <bits/stdc++.h>
using namespace std;

// 1 ~ 19
const int N = 19;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
int board[20][20];

// 0 -> black
// 1 -> white
bool vis[20][20];
vector<pair<int, int>> trashbin;

int lib = 0, sum[2];
void dfs(const int &x, const int &y, const int &col) {
    if (vis[x][y]) return ;
    vis[x][y] = 1;
    trashbin.emplace_back(x, y);
    for (int i = 0, nxtx, nxty; i < 4; ++i) {
        nxtx = x + dx[i], nxty = y + dy[i];
        if (nxtx < 1 || nxtx > N || nxty < 1 || nxty > N || vis[nxtx][nxty]) continue;
        if (board[nxtx][nxty] == -1) ++lib;
        if (board[nxtx][nxty] == col)
            dfs(nxtx, nxty, col);
    }
    return ;
}

// 0 -> self
// 1 -> opp
void calc(const int &x, const int &y, const int &col) {
    lib = 0;
    trashbin.clear();
    dfs(x, y, col);
    if (!lib) {
        sum[col] += trashbin.size();
        for (auto [x, y]: trashbin)
            board[x][y] = -1;
    }
    return ;
}

void remove(const bool& who) {
    sum[0] = sum[1] = 0;
    memset(vis, 0, sizeof vis);
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            if (vis[i][j] || board[i][j] != (who ^ 1)) continue;
            calc(i, j, who ^ 1);
        }
    }
    memset(vis, 0, sizeof vis);
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            if (vis[i][j] || board[i][j] != who) continue;
            calc(i, j, who);
        }
    }
    cout << sum[0] << ' ' << sum[1] << '\n';
    return ;
}

void work() {
    int m, x, y;
    cin >> m;
    bool who = 0;
    // 0 -> black
    // 1 -> white
    memset(board, -1, sizeof board);
    while (m--) {
        cin >> x >> y;
        board[x][y] = who;
        remove(who);
        who ^= 1;
    }
    return ;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    while (T--)
        work();
    return 0;
}

H. Genshin Impact Startup Forbidden III

题意：有k个鱼塘，鱼塘里的鱼数$a \in {1,2,3}$，每次炸鱼可以炸一个格子数为5的十字，求最少次数。

观察到$k\le10,a\in{1,2,3}$，可以考虑四进制状压来进行bfs

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, ll> pil;
typedef pair<int, int> pii;

int n, m, k;
set<int> pos;

const int dx[] = {0, 1, -1, 0, 0};
const int dy[] = {0, 0, 0, 1, -1};

pair<int, int> decode(int id) {
    int y = (id % m == 0) ? m : id % m;
    int x = (id - y) / m + 1;
    return make_pair(x, y);
}

void insert(int x, int y) {
    for (int i = 0; i < 5; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
        pos.emplace((nx - 1) * m + ny);
    }
}
// 四进制来表示一个鱼塘的状态 0 ~ 3
int dp[5000000];
int x[20], y[20];
ll bsum[20];
bool vis[5000000];

void debug(int x) {
    for (int i = 1; i <= k; i++)
        cout << (x & 3) << ' ', x >>= 2;
    cout << '\n';
}

void work() {
    int s = 0;
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++) {
        cin >> x[i] >> y[i] >> bsum[i];
        insert(x[i], y[i]);
        s |= (bsum[i] << (2 * (i - 1)));
        // 打错看半天！！！
    }
    memset(dp, 0x3f, sizeof dp);
    dp[s] = 0;
    vis[s] = 1;
    queue<int> q;
    q.emplace(s);
    while (!q.empty()) {
        int status = q.front();
        // debug(status);
        q.pop();
        for (auto ID: pos) {
            auto p = decode(ID);
            int X = p.first, Y = p.second, nsta = status;
            for (int i = 1; i <= k; i++) {
                if (abs(X - x[i]) + abs(Y - y[i]) <= 1) {
                    if (nsta & (3 << (2 * (i - 1)))) {
                        nsta -= (1 << (2 * (i - 1)));
                    }
                }
            }
            if (!vis[nsta]) {
                vis[nsta] = 1;
                dp[nsta] = dp[status] + 1;
                q.emplace(nsta);
            }
        }
    }
    cout << dp[0] << '\n';
    return ;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        work();
    return 0;
}