Hướng dẫn giải của [Free Contest 05] BANDYTA


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Hướng dẫn giải

Yêu cầu: có ~3~ trống, mỗi trống là hoán vị của ~1..N~. Chọn cách quay để số dòng có cả 3 biểu tượng giống nhau là lớn nhất.

Sub 1: Thử mọi cách quay — ~O(N^3)~, dùng khi ~N \le 100~

Cố định trống 1, thử mọi độ lệch ~d_2, d_3~ của hai trống còn lại. Với mỗi dòng kiểm tra ba biểu tượng và đếm.

Nếu chỉ nộp sub này: đúng 9/23 test.

Sub 2: Đếm theo độ lệch — ~O(N \log N)~

Biểu tượng ~v~ nằm cùng một dòng khi ~d_2 - d_1 = p_2(v) - p_1(v)~ và ~d_3 - d_2 = p_3(v) - p_2(v)~ (mod ~N~). Mỗi biểu tượng cho đúng một dòng khác nhau, nên đáp án là tần suất lớn nhất của cặp khoá này. Sắp xếp rồi đếm.

Nếu chỉ nộp sub này: đúng 23/23 test.

Chương trình hoàn chỉnh

Với ~N \le 100~ gọi sub 1, còn lại gọi sub 2. Sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.

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

int N;
vector<int> a1, a2, a3;   // a_j[i]: biểu tượng ở vị trí i (0-based) của trống j

// Sub 1: thử mọi cách quay O(N^3) — dùng khi N <= 100
// Quay trống 1 cố định (d1 = 0), thử mọi d2, d3; đếm số dòng có cả 3 biểu tượng giống nhau.
void sub1() {
    int best = 0;
    for (int d2 = 0; d2 < N; d2++)
        for (int d3 = 0; d3 < N; d3++) {
            int cnt = 0;
            for (int r = 0; r < N; r++) {
                int x = a1[r], y = a2[(r + d2) % N], z = a3[(r + d3) % N];
                if (x == y && y == z) cnt++;
            }
            best = max(best, cnt);
        }
    cout << best << "\n";
}

// Sub 2: đếm theo "độ lệch" O(N log N) — lời giải đầy đủ
// Biểu tượng v nằm cùng một dòng khi d2 - d1 = p2(v) - p1(v) và d3 - d2 = p3(v) - p2(v) (mod N).
// Mỗi biểu tượng cho một dòng khác nhau, nên đáp án là tần suất lớn nhất của khoá (độ lệch).
void sub2() {
    vector<int> p1(N + 1), p2(N + 1), p3(N + 1);
    for (int i = 0; i < N; i++) {
        p1[a1[i]] = i;
        p2[a2[i]] = i;
        p3[a3[i]] = i;
    }
    vector<long long> key(N);
    for (int v = 1; v <= N; v++) {
        long long x = ((p2[v] - p1[v]) % N + N) % N;
        long long y = ((p3[v] - p2[v]) % N + N) % N;
        key[v - 1] = x * N + y;
    }
    sort(key.begin(), key.end());
    int best = 0;
    for (int i = 0; i < N;) {
        int j = i;
        while (j < N && key[j] == key[i]) j++;
        best = max(best, j - i);
        i = j;
    }
    cout << best << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    a1.resize(N);
    a2.resize(N);
    a3.resize(N);
    for (auto &v : a1) cin >> v;
    for (auto &v : a2) cin >> v;
    for (auto &v : a3) cin >> v;
    if (N <= 100) sub1();
    else sub2();
    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.