Hướng dẫn cho LQDOJ CUP 2022 - Final Round - TRINET
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:
Xử lý dữ liệu đầu vào:
Từ công thức \(C_{i,j} = A_{i,j} \times 5000 + B_{i,j}\), ta dễ dàng tính lại được hai giá trị \(A_{i,j}\) và \(B_{i,j}\),
\(A_{i,j} = \left\lfloor C_{i,j} / 5000 \right\rfloor\)
\(B_{i,j} = C_{i,j} \texttt{ mod } 5000\)
Ý tưởng chung của bài toán đó là tìm ô tiếp theo sẽ nhảy đến khi đang đứng ở một ô nào đó. Sau đó sử dụng kĩ thuật quy hoạch động để tính điểm của lần chơi xuất phát từ ô \((i,j)\).
Subtask \(1\) (\(20\%\) số điểm): \(B_{i,j} \leq 2\) với mọi \((i, j)\).
Tutorial
Vì kích thước tối đa của tam giác là \(2\), ta chỉ cần xét tối đa \(2\) ô kề dưới ô đang đứng và tìm ra ô có giá trị lớn nhất.
Độ phức tạp: \(\mathcal{O}(n^2)\)
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2005;
const int BASE = 5000;
int n;
int a[MAX_N][MAX_N], b[MAX_N][MAX_N];
long long dp[MAX_N][MAX_N], result;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("TRINET.inp", "r", stdin);
freopen("TRINET.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
long long tmp;
cin >> tmp;
a[i][j] = tmp / BASE;
b[i][j] = tmp % BASE;
}
}
for (int i = n; i >= 1; i--) {
long long sum = 0;
for (int j = 1; j <= i; j++) {
if (b[i][j] == 2) {
if (a[i + 1][j] < a[i + 1][j + 1]) {
dp[i][j] = a[i][j] + dp[i + 1][j + 1];
} else {
dp[i][j] = a[i][j] + dp[i + 1][j];
}
} else {
dp[i][j] = a[i][j];
}
sum += dp[i][j] ^ j;
}
result += sum ^ i;
}
cout << result;
return 0;
}
Subtask \(2\) (\(20\%\) số điểm): Các ô ở hàng dưới luôn có giá trị cao hơn các ô ở hàng trên.
Tutorial
Bởi vì các ô ở hàng dưới luôn có giá trị lớn hơn các ô ở hàng trên, vậy nên ta không cần xét hết tất cả các ô trong tam giác đều mà chỉ cần tìm ô có giá trị lớn nhất trong các ô ở đáy tam giác (các ô ở hàng dưới cùng trong tam giác). Để tìm được ô có giá trị lớn nhất, có thể sử dụng thuật toán Range Minimum Query (RMQ). Như vậy, ở mỗi hàng cần xây dựng một mảng thưa để lưu ô có giá trị lớn nhất ở từng đoạn liên tiếp.
Độ phức tạp: \(\mathcal{O}(n^2 \times \log(n))\)
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2005;
const int LOG = 11;
const int BASE = 5000;
int n;
int a[MAX_N][MAX_N], b[MAX_N][MAX_N];
pair<int, int> rmq[MAX_N][LOG][MAX_N];
long long dp[MAX_N][MAX_N], result;
pair<int, int> getMax(const pair<int, int> &x, const pair<int, int> &y) {
return a[x.first][x.second] > a[y.first][y.second] ? x : y;
}
void prepare() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
rmq[i][0][j] = make_pair(i, j);
}
for (int k = 1; k < LOG; k++) {
for (int j = 1; j + (1 << k) - 1 <= i; j++) {
rmq[i][k][j] = getMax(rmq[i][k - 1][j], rmq[i][k - 1][j + (1 << (k - 1))]);
}
}
}
}
pair<int, int> getRMQ(int row, int left, int right) {
int level = 31 - __builtin_clz(right - left + 1);
return getMax(rmq[row][level][left], rmq[row][level][right - (1 << level) + 1]);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("TRINET.inp", "r", stdin);
freopen("TRINET.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
long long tmp;
cin >> tmp;
a[i][j] = tmp / BASE;
b[i][j] = tmp % BASE;
}
}
prepare();
result = 0;
for (int i = n; i >= 1; i--) {
long long sum = 0;
for (int j = 1; j <= i; j++) {
if (b[i][j] > 1) {
pair<int, int> cell = getRMQ(i + b[i][j] - 1, j, j + b[i][j] - 1);
dp[i][j] = a[i][j] + dp[cell.first][cell.second];
} else {
dp[i][j] = a[i][j];
}
sum += dp[i][j] ^ j;
}
result += sum ^ i;
}
cout << result;
return 0;
}
Subtask \(3\) (\(20\%\) số điểm): \(n \leq 500\).
Tutorial
Ở subtask này, giá trị các ô là ngẫu nhiên, vậy nên không thể chỉ xét các ô ở đáy tam giác được. May mắn thay, ở subtask này \(n \leq 500\), tức là có tối đa \(n \leq 500\) hàng cần xét, ta sẽ duyệt từng hàng và tìm ô có giá trị lớn nhất thuộc hàng đó trong tam giác bằng RMQ. Ô có giá trị lớn nhất trong các ô tìm được là ô cần tìm.
Độ phức tạp: \(\mathcal{O}(n^2 \times \log(n) + n^3)\)
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2005;
const int LOG = 11;
const int BASE = 5000;
int n;
int a[MAX_N][MAX_N], b[MAX_N][MAX_N];
pair<int, int> rmq[MAX_N][LOG][MAX_N];
long long dp[MAX_N][MAX_N], result;
pair<int, int> getMax(const pair<int, int> &x, const pair<int, int> &y) {
return a[x.first][x.second] > a[y.first][y.second] ? x : y;
}
void prepare() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
rmq[i][0][j] = make_pair(i, j);
}
for (int k = 1; k < LOG; k++) {
for (int j = 1; j + (1 << k) - 1 <= i; j++) {
rmq[i][k][j] = getMax(rmq[i][k - 1][j], rmq[i][k - 1][j + (1 << (k - 1))]);
}
}
}
}
pair<int, int> getRMQ(int row, int left, int right) {
int level = 31 - __builtin_clz(right - left + 1);
return getMax(rmq[row][level][left], rmq[row][level][right - (1 << level) + 1]);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("TRINET.inp", "r", stdin);
freopen("TRINET.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
long long tmp;
cin >> tmp;
a[i][j] = tmp / BASE;
b[i][j] = tmp % BASE;
}
}
prepare();
result = 0;
for (int i = n; i >= 1; i--) {
long long sum = 0;
for (int j = 1; j <= i; j++) {
if (b[i][j] > 1) {
pair<int, int> cell(i + 1, j);
for (int k = i + 1; k < i + b[i][j]; k++) {
cell = getMax(cell, getRMQ(k, j, j + k - i));
}
dp[i][j] = a[i][j] + dp[cell.first][cell.second];
} else {
dp[i][j] = a[i][j];
}
sum += dp[i][j] ^ j;
}
result += sum ^ i;
}
cout << result;
return 0;
}
Subtask \(4\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.
Tutorial
Ở subtask này, ta sẽ cải tiến cấu trúc mảng thưa. Thay vì lưu ô có giá trị lớn nhất của các đoạn liên tiếp, ta sẽ lưu ô có giá trị lớn nhất trong một tam giác đều. ý tưởng là chia tam giác đều thành \(3\) tam giác đều có kích thước bằng nhau phủ được tam giác đó.
Xét trong một tam giác đều độ dài cạnh là \(d\), độ dài cạnh tam giác tối thiểu để phủ được tam giác lớn là \(\frac{2}{3}d = d / 1.5\)
Như vậy, ta cần xây dựng một mảng \(\texttt{pw}\) với công thức như sau:
Vì \(\texttt{pw}_{18} = 2397 > 2000\) nên chỉ cần lưu \(18\) giá trị đầu của \(\texttt{pw}\).
Nếu ta biết được ô có giá trị lớn nhất trong tất cả các tam giác đều kích thước \(\texttt{pw}_{i}\), ta sẽ tìm được ô có giá trị lớn nhất trong tất cả các tam giác đều kích thước \(\texttt{pw}_{i+1}\).
Khi tìm ô có giá trị lớn nhất trong tam giác đều kích thước \(d\), ta cần tìm ra kích thước tam giác đều lớn nhất không vượt quá \(d\) là \(\texttt{pw}_k\), sau đó tam giác thành \(3\) tam giác đều kích thước \(\texttt{pw}_k\). Biết rằng \(\left\lceil \texttt{pw}_k \times 1.5\right\rceil > d \Leftrightarrow \texttt{pw}_k > d / 1.5\), vậy nên \(3\) tam giác này sẽ phủ được tam giác lớn (lưu ý là các tam giác có thể chồng lên nhau).
Ví dụ: Xét tam giác kích thước \(d\) có ô trên cùng là ô \((x,y)\), \(k\) là chỉ số lớn nhất sao cho \(\texttt{pw}_k \leq d\), khi đó ta sẽ chia tam giác thành \(3\) tam giác đều có kích thước \(\texttt{pw}_k\) với \(3\) ô trên cùng là \((x,y)\), \((x+d-\texttt{pw}_k, y)\), và \((x+d-\texttt{pw}_k, y+d-\texttt{pw}_k)\). \(3\) ô có giá trị lớn nhất trong \(3\) tam giác vừa chia đã được tính trước đó nên ta có thể tìm ra được ô cần tìm một cách nhanh chóng.
Độ phức tạp: \(\mathcal{O}O(n^2 \times \log{n})\)
Solution
#include <bits/stdc++.h>
using namespace std;
const int BASE = 5000;
const int MAX_N = 2005;
const int LOG = 20;
int n, a[MAX_N][MAX_N], b[MAX_N][MAX_N];
int pw[LOG], lg[MAX_N];
pair<int, int> rmq[LOG][MAX_N * MAX_N / 2];
long long dp[MAX_N][MAX_N], result;
int getIdx(int x, int y) {
return (x - 1) * x / 2 + y;
}
pair<int, int> &refRMQ(int lg, int x, int y) {
return rmq[lg][getIdx(x, y)];
}
pair<int, int> getMax(const pair<int, int> &x, const pair<int, int> &y) {
return a[x.first][x.second] > a[y.first][y.second] ? x : y;
}
void prepare() {
pw[0] = 1;
for (int i = 1; i < LOG; i++) {
pw[i] = (pw[i - 1] * 3 + 1) / 2;
}
for (int i = 0; i < LOG; i++) {
for (int j = pw[i]; j < MAX_N && j < pw[i + 1]; ++j) {
lg[j] = i;
}
}
for (int x = 1; x <= n; x++) {
for (int y = 1; y <= n; y++) {
refRMQ(0, x, y) = make_pair(x, y);
}
}
for (int i = 1; i < LOG; i++) {
for (int x = 1; x + pw[i] - 1 <= n; x++) {
for (int y = 1; y <= x; y++) {
refRMQ(i, x, y) = getMax(
refRMQ(i - 1, x, y),
getMax(
refRMQ(i - 1, x + pw[i] - pw[i - 1], y),
refRMQ(i - 1, x + pw[i] - pw[i - 1], y + pw[i] - pw[i - 1])));
}
}
}
}
inline pair<int, int> getRMQ(int d, int x, int y) {
int k = lg[d];
return getMax(refRMQ(k, x, y),
getMax(
refRMQ(k, x + d - pw[k], y),
refRMQ(k, x + d - pw[k], y + d - pw[k])));
}
inline pair<int, int> getMaxPos(int x, int y) {
return getMax(getRMQ(b[x][y] - 1, x + 1, y), getRMQ(b[x][y] - 1, x + 1, y + 1));
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("TRINET.inp", "r", stdin);
freopen("TRINET.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
long long tmp;
cin >> tmp;
a[i][j] = tmp / BASE;
b[i][j] = tmp % BASE;
}
}
prepare();
for (int i = n; i >= 1; i--) {
long long sum = 0;
for (int j = 1; j <= i; j++) {
if (b[i][j] > 1) {
pair<int, int> mxPos = getMaxPos(i, j);
dp[i][j] = a[i][j] + dp[mxPos.first][mxPos.second];
} else {
dp[i][j] = a[i][j];
}
sum += dp[i][j] ^ j;
}
result += sum ^ i;
}
cout << result;
return 0;
}
Bình luận
Bài này em làm 1 cách khác. Thay vì tạo sparse table lưu giá trị của các tam giác kích thước \(1.5^x\) em làm kích thước \(2^x\). Cách trên thay vì nối 3 tam giác ta cần nối 6 tam giác, nhưng bộ nhớ sẽ giảm so với cách trên. Có thể xem hình như sau:
Hình em hơi thiếu kinh phí ạ!