Hướng dẫn giải của [VTT Q4 Contest 14] Bài 4: Karate [KARATE]
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
Với mỗi vận động viên ~i~, ta xét những người cùng giới đứng trước từ gần đến xa; số người thắng là độ dài dãy liên tiếp (chỉ tính người cùng giới) có sức mạnh nhỏ hơn ~a_i~, dừng ở người đầu tiên có sức mạnh ~\ge a_i~.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 5000~
Với mỗi ~i~, lùi dần ~j = i-1, i-2, \ldots~, bỏ qua người khác giới, đếm khi ~a_i > a_j~ và dừng ngay khi gặp ~a_i \le a_j~. Nếu chỉ nộp sub này: đúng 20/20 test trên máy chấm cục bộ (máy thật có thể quá giờ ở các test ~n~ lớn).
Sub 2: Ngăn xếp đơn điệu — ~O(n)~
Mỗi giới giữ một ngăn xếp các phần tử có sức mạnh giảm dần, mỗi phần tử kèm một số ~w~ là số người cùng giới liên tiếp ngay trước nó mà nó "che" (tính cả chính nó). Khi xét người ~i~, lần lượt lấy ra các phần tử đỉnh có sức mạnh ~< a_i~ và cộng ~w~ của chúng; tổng đó chính là số người ~i~ thắng. Sau đó đẩy ~(a_i, \text{tổng} + 1)~ vào ngăn xếp. Mỗi phần tử vào và ra ngăn xếp đúng một lần nên tổng thời gian tuyến tính. Với ~n = 10^6~ cần đọc dữ liệu nhanh. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Chương trình đọc nhanh toàn bộ dữ liệu; nếu ~n \le 5000~ thì gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước. Chấm thử: chương trình đầy đủ đúng 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int n;
int a[1000005], g[1000005], kq[1000005];
void in_ket_qua() {
for (int i = 0; i < n; i++) printf("%d ", kq[i]);
printf("\n");
}
// Sub 1: với mỗi người, lùi dần về trước, bỏ qua người khác giới, dừng khi gặp người không yếu hơn — ~O(n^2)~
void sub1() {
for (int i = 0; i < n; i++) {
int w = 0;
for (int j = i - 1; j >= 0; j--) {
if (g[j] != g[i]) continue;
if (a[i] > a[j]) w++;
else break;
}
kq[i] = w;
}
in_ket_qua();
}
// Sub 2: mỗi giới giữ một ngăn xếp đơn điệu (sức mạnh giảm dần) — ~O(n)~.
void sub2() {
// ngăn xếp mỗi giới: (sức mạnh, số người cùng giới ngay trước nó mà nó "che" kể cả chính nó)
vector<pair<int,int>> st[2];
for (int i = 0; i < n; i++) {
auto &S = st[g[i]];
int tong = 0; // số người cùng giới liên tiếp phía trước có sức mạnh < a[i]
while (!S.empty() && S.back().first < a[i]) {
tong += S.back().second;
S.pop_back();
}
kq[i] = tong;
S.push_back({a[i], tong + 1});
}
in_ket_qua();
}
int main() {
freopen("KARATE.INP", "r", stdin);
freopen("KARATE.OUT", "w", stdout);
// đọc nhanh bằng fread vì n lên tới 10^6
static char buf[1 << 25];
size_t len = fread(buf, 1, sizeof(buf) - 1, stdin);
buf[len] = 0;
char *p = buf;
auto doc = [&]() {
while (*p && (*p < '0' || *p > '9')) p++;
int x = 0;
while (*p >= '0' && *p <= '9') x = x * 10 + (*p++ - '0');
return x;
};
n = doc();
for (int i = 0; i < n; i++) { a[i] = doc(); g[i] = doc(); }
if (n <= 5000) sub1();
else sub2();
}
Bình luận