Hướng dẫn cho Thám hiểm khảo cổ
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:
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
#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
#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
#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
#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
ủa rứa làm subtask5 j cho mệt
Subtask 5 hơi ảo