Giải Quyết Các Bài Toán Trong AtCoder Beginner Contest 395

A - Strictly Increasing?

#### Ý tưởng > Sử dụng mô phỏng. #### Mã nguồn
Xem mã nguồn
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 5;

vector<int> positions[MAXN];

void solve() {
    int n, ans = INT_MAX;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        positions[x].push_back(i);
    }
    bool found = false;
    for (int i = 0; i < MAXN; i++) {
        if (positions[i].size() <= 1) continue;
        found = true;
        for (int j = 1; j < positions[i].size(); j++) {
            ans = min(ans, positions[i][j] - positions[i][j - 1] + 1);
        }
    }
    cout << (found ? ans : -1) << endl;
}

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

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

C - Shortest Duplicate Subarray

#### Ý tưởng > Ghi lại vị trí xuất hiện của mỗi số, sau đó tính khoảng cách nhỏ nhất giữa các vị trí. #### Mã nguồn
Xem mã nguồn
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 5;

vector<int> positions[MAXN];

void solve() {
    int n, ans = INT_MAX;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        positions[x].push_back(i);
    }
    bool found = false;
    for (int i = 0; i < MAXN; i++) {
        if (positions[i].size() <= 1) continue;
        found = true;
        for (int j = 1; j < positions[i].size(); j++) {
            ans = min(ans, positions[i][j] - positions[i][j - 1] + 1);
        }
    }
    cout << (found ? ans : -1) << endl;
}

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

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

D - Pigeon Swap

#### Ý tưởng > Sử dụng mảng `p` để lưu vị trí của mỗi con chim, `v` để lưu vị trí của mỗi tổ, và `pv` để lưu vị trí của mỗi tổ chim. #### Mã nguồn
Xem mã nguồn
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 5;

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> p(n + 1), v(n + 1), pv(n + 1);
    iota(p.begin(), p.end(), 0);
    iota(pv.begin(), pv.end(), 0);
    iota(v.begin(), v.end(), 0);
    while (q--) {
        int op, a, b;
        cin >> op;
        if (op == 1) {
            cin >> a >> b;
            p[a] = pv[b];
        } else if (op == 2) {
            cin >> a >> b;
            swap(v[pv[a]], v[pv[b]]);
            swap(pv[a], pv[b]);
        } else {
            cin >> a;
            cout << v[p[a]] << endl;
        }
    }
}

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

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

E - Flip Edge

#### Ý tưởng > Tạo đồ thị chính và đồ thị ngược, với trọng số cạnh là 1. Kết nối các đỉnh tương ứng trong hai đồ thị bằng cạnh có trọng số `x`. Chạy thuật toán đường đi ngắn nhất từ đỉnh bắt đầu của đồ thị chính, và lấy kết quả nhỏ nhất từ đỉnh cuối của đồ thị chính và đồ thị ngược. #### Mã nguồn
Xem mã nguồn
#include <bits/stdc++.h>
using namespace std;

typedef pair pii;

const int MAXN = 2e5 + 5;

struct Edge {
    int to, weight;
    Edge(int to, int weight) : to(to), weight(weight) {}
};

void solve() {
    int n, m, x;
    cin >> n >> m >> x;
    vector g(2 * n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        g[u].emplace_back(v, 1);
        g[v + n].emplace_back(u + n, 1);
    }
    for (int u = 0; u < n; u++) {
        g[u].emplace_back(u + n, x);
        g[n + u].emplace_back(u, x);
    }
    priority_queue pq;
    vector<bool> vis(2 * n, false);
    vector<int> dist(2 * n, INT_MAX);
    dist[0] = 0;
    pq.push({dist[0], 0});
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto& e : g[u]) {
            if (dist[e.to] > dist[u] + e.weight) {
                dist[e.to] = dist[u] + e.weight;
                pq.push({dist[e.to], e.to});
            }
        }
    }
    cout << min(dist[n - 1], dist[2 * n - 1]) << endl;
}

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

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

F - Smooth Occlusion

#### Ý tưởng > Xử lý răng trên, sau đó lấy `h = min(U_i + D_i)`, kết quả là tổng độ dài răng trước khi xử lý trừ `n * h`. Có thể tính trong quá trình xử lý và cộng thêm chi phí xử lý răng dưới. #### Mã nguồn
Xem mã nguồn
#include <bits/stdc++.h>
using namespace std;

typedef pair pii;

const int MAXN = 2e5 + 5;

void solve() {
    int n, x, ans = 0;
    cin >> n >> x;
    vector<int> U(n), D(n);
    priority_queue pq;
    for (int i = 0; i < n; i++) {
        cin >> U[i] >> D[i];
        pq.push({U[i], i});
    }
    while (!pq.empty()) {
        int idx = pq.top().second;
        pq.pop();
        if (idx < n - 1 && U[idx + 1] - U[idx] > x) {
            ans += U[idx + 1] - (U[idx] + x);
            U[idx + 1] = U[idx] + x;
            pq.push({U[idx + 1], idx + 1});
        }
        if (idx && U[idx - 1] - U[idx] > x) {
            ans += U[idx - 1] - (U[idx] + x);
            U[idx - 1] = U[idx] + x;
            pq.push({U[idx - 1], idx - 1});
        }
    }
    int minn = INT_MAX;
    for (int i = 0; i < n; i++) {
        minn = min(minn, U[i] + D[i]);
    }
    for (int i = 0; i < n; i++) {
        ans += U[i] + D[i] - minn;
    }
    cout << ans << endl;
}

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

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

Thẻ: C++ STL Graph Algorithms Priority Queue Simulation

Đăng vào ngày 26 tháng 5 lúc 11:59

Thẻ Phổ Biến

©2026 Thành phố Cuồng loạn