22strb - THTB Sơn Trà 2022

Mắc đèn

Công thức

$8a$.

Các bạn thử lấy vở ô ly và vẽ test VD để hiểu

Bài 2

Ngày chia hết cho

$18$ là ngày cả 2 máy đều nghỉ

Bài 3

Subtask 1 (50%):

$O(n^3)$

Đề bảo chọn ra 3 vị trí –> Dùng 3 vòng lặp For

for (i từ 1 tới n-2) {
    for (j từ i+1 tới n-1) {
        for (k từ j+1 tới n) {
            kết quả = max(kết quả, a[i] + a[j] - a[k]);
        }
    }
}

Subtask 1.5:

$O(n^2)$ (thanks hoangtieuho)

kq = 0;

 for(int i = 1; i <= n-2; i++) {
    int min_aj = a[i+1];
    for(int k = i+2; k <= n; k++) {
        kq = max(kq, a[i] - min_aj + a[k]);
        min_aj = min(min_aj, a[k]);
    }

Subtask 2:

$O(n)$

Chỉ chạy một vòng lặp for j để cố định

$a_j$

Cần tìm (nhanh):

• $i$ là vị trí của phần tử lớn nhất TRƯỚC
  $j$
• $k$ là vị trí của phần tử lớn nhất SAU
  $j$

CTDL: Prefix-sum. Chi tiết: https://www.youtube.com/watch?v=gK4sTB4aznA&t=1650s

Bài 4:

Subtask 1

$a,n\le 1000$

Đặt L: mực nước

kq = 0;

for (L từ 1 tới max_a) {
    a[0] = -1
    a[n+1] = -1
    đếm_cô_đơn = 0
    for (i từ 1 tới n) {
        if (a[i] >= L) và (a[i-1] < L) và (a[i+1] < L) {
            đếm_cô_đơn += 1
        }
        kq = max(kq, đếm_cô_đơn)
    }
}

$O(n\times a_{max})$

Subtask 2

Mỗi tòa nhà sẽ có một khoảng thời gian liên tiếp mà nó bị cô độc.

pigbank - lqdoj
https://wiki.vnoi.info/vi/algo/data-structures/prefix-sum-and-difference-array

Subtask 3

$[1,300]$ và

$[50,400]$

$[1,3]$ và

$[2,4]$

Áp dụng kĩ thuật nén số: https://viblo.asia/p/roi-rac-hoa-nen-so-38X4E9QA4N2