Hướng dẫn giải của [2526 KS1 THCS] Bài 3: Tổng trên lướ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
Lưới ~N \times N~ được đánh số theo các đường chéo zigzag. Quân cờ đi theo ~K~ bước cho trước, cần tính tổng các ô đã đi qua.
Sub 1: Dựng cả lưới — ~O(N^2 + K)~, dùng khi ~N \le 1000~
Duyệt từng đường chéo ~r + c = d~. Trên đường chéo lẻ, số được đánh theo hàng ~r~ tăng dần, còn đường chéo chẵn thì theo hàng giảm dần. Ghi số vào mảng ~N \times N~ rồi mô phỏng quân cờ, cộng dồn giá trị từng ô.
Nếu chỉ nộp sub này: đúng 15/30 test.
Sub 2: Tính giá trị từng ô bằng công thức — ~O(K)~, dùng khi mọi trường hợp còn lại
Số ô nằm trên các đường chéo trước đường chéo ~d~ là ~d(d+1)/2~ nếu ~d \le N~. Nếu ~d > N~ thì đếm ngược từ góc dưới phải: còn ~M = 2N - 1 - d~ ô trên các đường chéo từ ~d~ trở đi, nên số ô trước là ~N^2 - M(M+1)/2~. Vị trí ô trong đường chéo cộng 1 là phần lẻ của giá trị. Mỗi bước tính trực tiếp được giá trị ô hiện tại, không cần lưu lưới (lưới có tới ~10^{10}~ ô).
Nếu chỉ nộp sub này: đúng 30/30 test.
Chương trình hoàn chỉnh
Subtask 1 (~N = 6~), subtask 2 (chuỗi chỉ có một loại bước), subtask 3 (~N < 1000~) và subtask 4 (không giới hạn thêm) đều được sub 2 xử lý đúng. Sub 1 chỉ dùng cho ~N \le 1000~ để dễ kiểm tra.
Chương trình đọc ~N, K~ và chuỗi bước đi. Nếu ~N \le 1000~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int N, K;
string moves;
// Sub 1: dung khi N <= 1000. Dien ca luoi N x N theo duong cheo zigzag (duyet tung duong cheo),
// roi mo phong quan co va cong gia tri cac o di qua.
void sub1() {
vector<vector<long long>> g(N, vector<long long>(N, 0));
long long cnt = 0;
for (int d = 0; d <= 2 * N - 2; d++) {
vector<int> rows; // cac hang r co o (r, d - r) trong luoi
for (int r = 0; r < N; r++) {
int c = d - r;
if (c >= 0 && c < N) rows.push_back(r);
}
if (d % 2 == 0) reverse(rows.begin(), rows.end()); // duong cheo chan: tu duoi len tren
for (size_t t = 0; t < rows.size(); t++) g[rows[t]][d - rows[t]] = ++cnt;
}
int r = 0, c = 0;
long long sum = g[0][0];
for (int i = 0; i < K; i++) {
char ch = moves[i];
if (ch == 'U') r--;
else if (ch == 'D') r++;
else if (ch == 'L') c--;
else c++;
sum += g[r][c];
}
cout << sum << "\n";
}
// Gia tri o (r, c) tinh truc tiep bang cong thuc (khong can luu luoi): O(1) moi o.
long long S(long long d) { // so o nam tren cac duong cheo truoc duong cheo d
if (d <= N) return d * (d + 1) / 2;
long long M = 2LL * N - 1 - d; // so o tren cac duong cheo tu d tro di, la M(M+1)/2
return 1LL * N * N - M * (M + 1) / 2;
}
long long valueAt(long long r, long long c) {
long long d = r + c;
long long rlo = max(0LL, d - (N - 1));
long long rhi = min(d, (long long)(N - 1));
long long idx = (d % 2 == 1) ? (r - rlo) : (rhi - r);
return S(d) + idx + 1;
}
// Sub 2: tinh truc tiep gia tri moi o bang cong thuc, O(K). Dung cho moi N
void sub2() {
long long r = 0, c = 0;
long long sum = valueAt(0, 0);
for (int i = 0; i < K; i++) {
char ch = moves[i];
if (ch == 'U') r--;
else if (ch == 'D') r++;
else if (ch == 'L') c--;
else c++;
sum += valueAt(r, c);
}
cout << sum << "\n";
}
int main() {
cin >> N >> K;
cin >> moves;
if (N <= 1000) sub1();
else sub2();
return 0;
}
Bình luận