or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing
xxxxxxxxxx
OLP MTTN 2023 - Sơ loại bảng Không chuyên
Bài 1 - THREE
Ta có: \(3 = 1+1+1 = 1+2\), tức có 3 cách tạo thành tổng bằng 3.
Tuy nhiên, cách sau tốn nhiều số hơn, mà muốn tạo thành nhiều tập thì phải ưu tiên tập có ít số hơn
\(\Rightarrow\) thứ tự ưu tiên tạo tập số: \(\{3\}, \{1, 2\}, \{1,1,1\}\).
Bài 2 - TRANSFORM
Với một số \(X\) bất kỳ:
\(\Rightarrow\) để tìm trạng thái liền trước của \(X\):
Vì thế, thay vì tìm cách tạo \(B\) từ \(A\), ta sẽ truy ngược từ \(B\) về \(A\).
Bài 3 - SWORD
Hướng nghĩ:
\(\Rightarrow\) các con boss sẽ được tiêu diệt theo thứ tự \(p_i\) tăng dần.
\(\Rightarrow\) sắp xếp các boss theo thứ tự \(p\) (nếu cùng \(p\) thì \(g\) như nào không quan trọng, vì cùng \(p\) sẽ cùng bị tiêu diệt một lần, chứ không có chuyện hai boss cùng \(p\) mà một con bị diệt một con thì không)
Bài 4 - COLORBOX
Lưu ý: Không nhất thiết phải giữ lại toàn bộ các màu (các giá trị khác nhau) có trong mảng, tức được phép mất đi một(vài) màu.
Ở đây giả sử ta bắt buộc phải xóa ít nhất một đoạn. Nếu các phần tử khác nhau đôi một, lập tức in ra \(0\) rồi kết thúc chuogw trình.
Subtask 1 - \(n \leq 10^2\)
Để kiểm tra điều kiện 2, ta sẽ tạo một mảng đếm phân phối
dpp[]
số lần xuất hiện của các màu, và một biếncnt
đếm số màu xuất hiện nhiều hơn một lần.dpp[màu]++
, nếudpp[màu] == 2
thìcnt++
.Độ phức tạp: \(\mathcal{O(n^3)}\); gồm cho \(\mathcal{O(n^2)}\) cho việc chọn cặp \((l,r)\) và \(\mathcal{O}(n)\) cho việc đánh dấu màu.
Subtask 2 - \(n \leq 10^3\)
Khi duyệt các cặp \((l, r)\), với \(l\) cố định thì mỗi lần chỉ thay đổi \(r\) đi \(1\) đơn vị \(\Rightarrow\) bỏ bớt một số ra khỏi tập các số còn lại đang xét.
\(\Rightarrow\) thay vì với mỗi cặp \((l, r)\) ta duyệt các số nằm ngoài đoạn, để lợi dụng sự thay đổi nhỏ này:
Ví dụ:
Giả sử \(n=4\)
Vì thế, ta cần hỗ trợ thêm phép xóa phần tử:
--dpp[màu]
, nếudpp[mau] == 1
thìcnt--
Độ phức tạp: \(\mathcal{O}(n^2)\)
Ta có thể cải tiến thuật toán bằng cách dừng \(r\) ngay khi
cnt == 0
, khi đó \(r\) là vị trí cuối đoạn tối thiểu để phần ngoài có các phần tử độc nhất, từ đó dựng lên các đoạn ngắn nhất. (*)Subtask 3+4 - \(n \leq 10^6\)
Nhận thấy: Với một đoạn \((l, r)\) bất kỳ:
Từ (*), khi ta thử tìm \(r\) nhỏ nhất thỏa mãn điều kiện của từng giá trị \(l\), ta thấy khi \(l\) tăng thì \(r\) cũng tăng
Vì khi \(l\) tăng thì bên ngoài thêm một phần tử:
Vì thế, cũng như lúc nãy, ta dựng
dpp[]
vàcnt
cho toàn mảng \(A\)cnt==0
A_1
vàodpp
và cập nhậtcnt
. Nếucnt!=0
thì ta tăng \(r\) (loại bỏ \(A_r\) rồi tăng \(r\) lên 1đv) cho tới khicnt==0