Hướng dẫn cho Thám hiểm khảo cổ

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: letangphuquy

Subtask \(1\) (\(27\) điểm): \(Q = 1, M = 10\).

Tutorial

Mô phỏng lại trạng thái của các viên thạch anh (ta gọi là viên đá) bằng cách duyệt. Tại thời điểm \(x\) bất kì, viên đá \(i\) có trạng thái là \(t^{'}_i = (t_i + x) \mod r_i\). Với mỗi viên đá \(i\), ta duyệt qua \(O((t^{'}_i)^{2})\) ô lân cận và đánh dấu vào bảng.
Độ phức tạp: \(\mathcal{O}(M \cdot (N^2 + K(2r)^2))\)

Solution

Lưu ý: Code sau chỉ chạy được từ C++ 17 trở đi

C++

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

const int N = 505;
int task, siz, numSteps;
struct Crystal {
    int x,y, r,t;
};
int numCrystals;
vector<Crystal> crystals;
typedef pair<int,int> Cell;

Cell sta, fin;
void inpCell(Cell& c) { cin >> c.first >> c.second; }

void getInput(void) {
    cin >> task >> siz >> numCrystals >> numSteps;
    crystals.resize(numCrystals);
    for (auto &[x,y,r,t] : crystals)
        cin >> x >> y >> r >> t;
    inpCell(sta);
    inpCell(fin);
}

int cnt[N][N];

int findMaxCover() {
    int answer = 0;
    for (int st = 0; st <= numSteps; st++) {
        int numCovered = 0;
        for (int x = 1; x <= siz; x++)
            for (int y = 1; y <= siz; y++) cnt[x][y] = 0;
        for (auto [u,v,r,t] : crystals) {
            (t += st) %= r;
            for (int x = max(1,u-t); x <= min(siz,u+t); x++) {
                for (int y = max(1,v-t); y <= min(siz,v+t); y++) {
                    int dist = abs(x-u) + abs(y-v);
                    if (dist <= t) ++cnt[x][y];
                }
            }
        }
        for (int x = 1; x <= siz; x++)
            for (int y = 1; y <= siz; y++)
                numCovered += (cnt[x][y] > 0);
        answer = max(answer, numCovered);
    }
    return answer;
}

void solve() 
{
    getInput();
    cout << findMaxCover();
}

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

    solve();
}

Subtask \(2\) (\(23\) điểm): \(Q = 1\).

Tutorial

Nhận thấy \(r_i \le 6\) là một giới hạn "khả nghi". Thử phân tích, ta thấy:

Giả sử \(r_i = r_1\) - chu kì mọi viên đá bằng nhau thì bảng chỉ có tối đa \(r\) trạng thái khác nhau.
Giả sử chỉ có hai viên đá có chu kì là \(r_1, r_2\) thì bảng có \(lcm(r_1,r_2)\) trạng thái
Một cách tổng quát, ta biết số trạng thái của bảng với \(k\) viên đá là \(lcm(r_1, r_2, r_3, \dots, r_k) \le lcm(1,2,3,4,5,6) = 60\)

Vậy có thể làm thuật toán như subtask 1 nhưng chỉ xét tối đa là \(60\) bước.
Độ phức tạp: \(\mathcal{O}(\min(60,M) \cdot (N^2 + K(2r)^2))\)

Solution

Tại dòng \(29\) của code subtask 1, hãy sửa: for (int st = 0; st <= numSteps; st++) { thành for (int st = 0; st <= min(numSteps, 60); st++) {

Subtask \(3\) (\(17\) điểm): \(Q = 2\) và \(r_i = 1 \,\, \forall i\).

Tutorial

\(r = 1 \Rightarrow t = 0\), tức các viên đá là các "ô cấm". Dùng BFS. Nhận thấy trong trường hợp này ta luôn di chuyển mà không dừng lại.
Độ phức tạp: \(\mathcal{O}(N^2 + K)\)

Solution

C++

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

const int N = 505;
int task, siz, numSteps;
struct Crystal {
    int x,y, r,t;
};
int numCrystals;
vector<Crystal> crystals;
typedef pair<int,int> Cell;

Cell sta, fin;
void inpCell(Cell& c) { cin >> c.first >> c.second; }

bool mark[N][N];

void getInput(void) {
    cin >> task >> siz >> numCrystals >> numSteps;
    crystals.resize(numCrystals);
    for (auto &[x,y,r,t] : crystals) {
        cin >> x >> y >> r >> t;
        mark[x][y] = true;
    }
    inpCell(sta);
    inpCell(fin);
}

int label[N][N];
queue<Cell> bfs;
#define x first
#define y second

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

int findShortestPath(void) {
    while (!bfs.empty()) bfs.pop();
    memset(label, -1, sizeof(label));
    label[sta.x][sta.y] = 0;
    bfs.push(sta);
    while (!bfs.empty()) {
        auto [x,y] = bfs.front(); bfs.pop();
        if (x == fin.x && y == fin.y)
            return label[x][y];
        for (int dir = 0; dir < 5; dir++) {
            int u = x + dx[dir], v = y + dy[dir];
            if (min(u,v) < 1 or max(u,v) > siz or mark[u][v]) continue;
            if (label[u][v] == -1) {
                label[u][v] = label[x][y] + 1;
                bfs.push(Cell(u,v));
            }
        }
    }
    return -1;
}

void solve() {
    getInput();
    cout << findShortestPath();
}

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

    solve();
}

Subtask \(4\) (\(13\) điểm): \(Q = 2, N = 7\) và \(r_i \le 3\).

Tutorial

Vẫn BFS. Tuy nhiên, vì có thể cần phải đứng yên tại ô nào đó, ta đặt mảng \(\texttt{ok[x][y][z]}\) với ý nghĩa là có đi tới được ô \((x,y)\) vào thời điểm \(z\) hay không?
Vậy thì \(z \max = ?\). Nhận thấy nếu đứng yên tại một ô nào đó thì cũng chỉ tốn thời gian tối đa là \(lcm(r_1, \dots, r_n) \le lcm(1,2,3) = 6\) bước. Và số ô đi qua nhiều nhất cho tới khi đến đích cũng \(\le N^2\). Do đó \(z \max \le 6N^2\)
Việc kiểm tra ô có an toàn hay không có thể tiền xử lý hoặc chạy trực tiếp trong lúc BFS đều được.
Độ phức tạp: \(\mathcal{O}(z \cdot N^2 \cdot r^2)\)

Solution

C++

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

const int N = 505;
int task, siz, numSteps;
struct Crystal {
    int r,t;
};
int numCrystals;
vector<Crystal> crystalsAt[N][N];
typedef pair<int,int> Cell;

Cell sta, fin;
void inpCell(Cell& c) { cin >> c.first >> c.second; }

void getInput(void) {
    cin >> task >> siz >> numCrystals >> numSteps;
    for (int i = 0; i < numCrystals; i++) {
        int x,y,r,t; 
        cin >> x >> y >> r >> t;
        crystalsAt[x][y].push_back({r,t});
    }
    inpCell(sta);
    inpCell(fin);
}

const int N1 = 7;
const int S = N1 * N1 * 6 + 100;
bool reach[N1+1][N1+1][S];
struct State {
    int x,y,t;
};
queue<State> bfs;
void add(int x, int y, int d) {
    if (!reach[x][y][d]) {
        reach[x][y][d] = true;
        bfs.push({x,y,d});
    }
}

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

bool isOkay(int x, int y, int d) {
    // cerr << "Checking (" << x << ',' << y << ',' << " at " << d << ")\n";
    for (int u = max(1,x-3); u <= min(siz, x+3); u++)
        for (int v = max(1,y-3); v <= min(siz,y+3); v++) {
            int dist = abs(u-x) + abs(v-y);
            if (dist > 3) continue;
            for (auto [r,t] : crystalsAt[u][v]) {
                t = (t + d) % r;
                if (dist <= t) return false;
            }
        }

    return true;
}

int findShortestPath(void) {
    while (!bfs.empty()) bfs.pop();
    add(sta.first, sta.second, 0);
    while (!bfs.empty()) {
        auto [x,y,d] = bfs.front(); bfs.pop();
        if (x == fin.first && y == fin.second)
            return d;
        for (int dir = 0; dir < 5; dir++) {
            int u = x + dx[dir], v = y + dy[dir];
            if (min(u,v) < 1 or max(u,v) > siz) continue;
            if (isOkay(u,v, d+1)) add(u,v, d+1);
        }
    }
    return -1;
}

void solve() {
    getInput();
    cout << findShortestPath();
}

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

    solve();
}

Subtask \(5\) (\(11\) điểm): \(Q = 2\) và \(t_i = 0\)

Tutorial

BGK không có thuật gì đặc biệt dành riêng cho subtask này (giải bằng thuật của subtask cuối).

Solution

Xem ở subtask 6

Subtask \(6\) (\(9\) điểm): \(Q = 2\)

Tutorial

Nhận xét "bảng chỉ có \(\le 60\) trạng thái phân biệt" từ subtask 2 có thể giúp ta giải luôn subtask này.
Trước tiên, duyệt qua các thời điểm từ \(0\) tới \(59\) để đánh dấu xem ô bất kì trong bảng có đi vào được hay không? Có thể dùng lại code subtask 2.
Giả sử có thể đi tới được ô \((x,y)\) vào thời điểm \(z\), mà \(z \mod 60 = r\). Nhận thấy trạng thái của bảng vào các thời điểm \(z + 60, z + 2 \times 60, z + 3 \times 60, \dots\) hoàn toàn giống vậy, nên chiến thuật đi tối ưu cũng không đổi. Vì thế ta chỉ cần quan tâm thời điểm đầu tiên.
Đặt \(\texttt{f[x][y][r]}\) là số bước để tới được \(x,y\) vào thời điểm chia \(60\) dư \(r\)
Vẫn cài đặt BFS như trên.
Độ phức tạp: \(\mathcal{O}(M \cdot (N^2 + K(2r)^2))\)

Solution

C++

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

bool umin(int& var, int val) {
    if (val < var) return var = val, true;
    return false;
}

const int N = 505;
int task, siz, numSteps;
struct Crystal {
    int x,y, r,t;
};
int numCrystals;
vector<Crystal> crystals;
typedef pair<int,int> Cell;

Cell sta, fin;
void inpCell(Cell& c) { cin >> c.first >> c.second; }

void getInput(void) {
    cin >> task >> siz >> numCrystals >> numSteps;
    crystals.resize(numCrystals);
    for (auto &[x,y,r,t] : crystals)
        cin >> x >> y >> r >> t;
    inpCell(sta);
    inpCell(fin);
}

int cnt[N][N];
bool mark[60][N][N];

int findMaxCover(bool getConf = false) {
    int answer = 0;
    for (int st = 0; st <= min(getConf ? 59 : numSteps, 60); st++) {
        int numCovered = 0;
        for (int x = 1; x <= siz; x++)
            for (int y = 1; y <= siz; y++) cnt[x][y] = 0;
        for (auto [u,v,r,t] : crystals) {
            (t += st) %= r;
            for (int x = max(1,u-t); x <= min(siz,u+t); x++) {
                for (int y = max(1,v-t); y <= min(siz,v+t); y++) {
                    int dist = abs(x-u) + abs(y-v);
                    if (dist <= t) ++cnt[x][y];
                }
            }
        }
        for (int x = 1; x <= siz; x++)
            for (int y = 1; y <= siz; y++) {
                numCovered += (cnt[x][y] > 0);
                if (getConf) 
                    mark[st][x][y] = (cnt[x][y] > 0);
            }
        answer = max(answer, numCovered);
    }
    return answer;
}

int dp[N][N][60];
struct State {
    int x,y,r;
};
queue<State> bfs;
void add(int x, int y, int d) {
    int r;
    if (umin(dp[x][y][r = (d % 60)], d))
        bfs.push({x,y,r});
}

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

int findShortestPath(void) {
    int j4f = findMaxCover(true);
    memset(dp, 0x3f, sizeof(dp));
    while (!bfs.empty()) bfs.pop();
    add(sta.first, sta.second, 0);
    while (!bfs.empty()) {
        auto [x,y,r] = bfs.front(); bfs.pop();
        if (x == fin.first && y == fin.second)
            return dp[x][y][r];
        int rel = dp[x][y][r] + 1;
        for (int dir = 0; dir < 5; dir++) {
            int u = x + dx[dir], v = y + dy[dir];
            if (min(u,v) < 1 or max(u,v) > siz) continue;
            if (!mark[rel%60][u][v])
                add(u,v, rel);
        }
    }
    return -1;
}

void solve() {
    getInput();
    cout << ((task == 1) ? findMaxCover() : findShortestPath());
}

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

    solve();
}

Bình luận

Không có bình luận nào.