Editorial for Chơi game
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Chơi game
Sub 1: ~H_1~ ~<~ ~H_2~ ~<~ ... ~<~ ~H_n~
- Gọi ~f[i] = 1~ nếu tòa tháp ~i~ thỏa mãn và ~f[i] = 0~ trong trường hợp còn lại. Ta có ~f[1] = 1~
- Xét tòa tháp thứ ~i~, ta cần tìm xem có tòa tháp thứ ~j~ sao cho ~j < i~, ~|h[i] - h[j]| \le k~ và ~f[j] = 1~. Tuy nhiên vì ~h~ là dãy tăng dần, ta chỉ cần xét vị trí ~i - 1~ vì nếu vị trí ~i - 1~ thỏa mãn thì vị trí ~i~ sẽ thỏa mãn. Nếu không giả sử tồn tại vị trí ~t~ thỏa mãn ~f[t] = 1~ và ~t < i - 1~, lúc này ~|h[i] - h[i - 1]| < |h[i] - h[t]|~ nên nếu không thể cập nhật vị trí ~i~ từ ~i - 1~ thì càng không thể sử dụng ~t~ để cập nhật cho ~i~.
- ĐPT: ~O(n)~
Sub 2: ~n \le 1000~
- Xét vị trí thứ ~i~, ta duyêt qua các vị trí ~j < i~.
- Nếu tồn tại vị trí ~j~ thỏa mãn ~f[j] = 1~ và ~|h[i] - h[j] \le k~ thì ~f[i] = 1~.
- ĐPT: ~O(n ^ 2)~
Sub 3 : Không có ràng buộc gì thêm
- Nhận xét rằng ~i~ độ cao có thể nhảy đến từ đỉnh ~1~ sẽ tạo thành 1 khoảng ~[l_i, r_i]~. Ta có ~l_1 = h[1] - k~ và ~r_1 = h[1] + k~.
- Vậy với mỗi vị trí ~i + 1~, nếu ~l_i \le h[i + 1] \le r_i~ thì ~f[i + 1] = 1~.
- Ta cập nhật khoảng ~[l_i, r_i]~ mỗi khi có độ cao thỏa mãn mới.
- DDPT: ~O(n)~
Code tham khảo
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 2;
int n, k, h[N];
int main() {
cin.tie(0) -> sync_with_stdio(0);
#define task "CHOIGAME"
if(fopen(task ".INP", "r")) {
freopen(task ".INP", "r", stdin);
freopen(task ".ANS", "w", stdout);
}
cin >> n >> k;
for (int i = 0; i < n; ++i) {
cin >> h[i];
}
int l = h[0], r = h[0];
cout << "1 ";
for (int i = 1; i < n; ++i) {
if (l - k <= h[i] && h[i] <= r + k) {
cout << "1 ";
l = min(l, h[i]);
r = max(r, h[i]);
} else cout << "0 ";
}
cout << "\n";
return 0;
}