Hướng dẫn cho LQDOJ Cup 2023 - Round 2 - Castle
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\)
Tutorial
Vì \(n, m\) rất nhỏ nên bạn có thể sử dụng bất kỳ thuật trâu nào. Cách làm chung là duyệt qua từng hình chữ nhật và kiểm tra xem các ô có giá trị bằng nhau hay không.
Độ phức tạp: \(O(n^3m^3)\) hay \(O(n^2m^2)\) tuỳ vào cách cài đặt.
Subtask \(2\)
Tutorial
Có nhiều cách để xử lý subtask này. Một trong số cách đó là duyệt qua hai hàng trên và dưới của hình chữ nhật. Sau đó với mỗi cột bên phải \(r\) của hình chữ nhật đang xét (đảm bảo cột chỉ chứa những giá trị giống nhau), bạn tìm cột bên trái xa nhất \(l\) sao cho hình chữ nhật này chỉ chứa những giá trị giống nhau và cập nhật đáp án với \(r - l + 1\).
Độ phức tạp: \(O(n^2m)\).
Subtask \(3\)
Tutorial
Với giá trị \(h_{i, j}\) rất nhỏ. Bạn có thể duyệt qua từng giá trị \(v\) từ \(1\) đến \(\max h_{i, j}\) và tạo thành một bảng mới. Những ô \((i, j)\) có \(h_{i, j} = v\) sẽ là \(1\), còn lại là \(0\). Lúc này bài toán trở hành tìm số hình chữ nhật toàn \(1\) trong bảng.
Đề giải bài toán này, đầu tiên bạn có mảng \(f[i][j]\) là giá trị lớn nhất \(x\) mà \(h[i - y + 1][j] = 1\) với mọi \(1 \leq y \leq x\). Sau đó với mỗi hàng \(i\), bạn sử dụng ngăn xếp để lưu lại những vị trí \(j\) mà giá trị \(f[i][j]\) tại đó giảm dần và tính toán dựa trên đó. Chi tiết hơn, bạn có thể đọc ở đây.
Độ phức tạp: \(O(\max h_{i, j} \times n m)\).
Subtask \(4\)
Tutorial
Bạn vẫn có thể sử dụng kỹ thuật trên những phải biến đổi một chút, chằng hạn như \(f[i][j]\) sẽ lưu giá trị lớn nhất \(x\) mà những giá trị \(h\) bằng nhau hay khi duyệt qua một giá trị khác, bạn sẽ xoá hết mọi phần tử trong ngăn xếp đi.
Độ phức tạp: \(O(nm)\).
Solution
#include <bits/stdc++.h>
/// kitsune
using namespace std;
#define fi first
#define se second
#define mp make_pair
//#define int long long
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = (int)(l); i <= (int)(r); i++)
#define per(i, r, l) for (int i = (int)(r); i >= (int)(l); i--)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<typename _Tp> bool minimize(_Tp &__a, const _Tp &__b) { if (__a > __b) { __a = __b; return true; } return false; }
template<typename _Tp> bool maximize(_Tp &__a, const _Tp &__b) { if (__a < __b) { __a = __b; return true; } return false; }
const int siz = 2e3 + 2;
const int SIZ = 1e6 + 2;
const int mod = 1e9 + 7;
const int maxx = 2e9;
const ll MAXX = 1e18;
const string file = "castle";
int a[siz][siz];
int h[siz];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
freopen((file + ".inp").c_str(), "r", stdin);
freopen((file + ".out").c_str(), "w", stdout);
int n, m;
cin >> n >> m;
rep (i, 1, n) rep (j, 1, m) {
cin >> a[i][j];
}
ll ans = 0;
rep (i, 1, n) {
rep (j, 1, m) {
if (i == 1 || a[i][j] == a[i - 1][j]) {
h[j]++;
} else {
h[j] = 1;
}
}
vector<int> st;
ll cur = 0;
rep (j, 1, m) {
if (a[i][j] != a[i][j - 1]) {
st.assign(1, j - 1);
cur = 0;
}
while (sz(st) > 1 && h[st.back()] >= h[j]) {
cur -= (st.back() - st[sz(st) - 2]) * h[st.back()];
st.pop_back();
}
st.push_back(j);
cur += (st.back() - st[sz(st) - 2]) * h[st.back()];
ans += cur;
}
}
cout << ans << "\n";
// cerr << "Time: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";
return 0;
}
Bình luận