TST 2017
Table of contents
Đề bài
Ngày 1
Bài 1
Cho hai dãy $A$ và $B$ gồm $N$ phần tử và số $M$.
Có các loại thao tác sau:
- Nhân cả dãy lên cùng với một số (tùy ý mình) từ $1$ đến $M$
- Trừ một phần tử nào đó đi $1$.
Tìm số thao tác tối thiểu để biến dãy $A$ thành dãy $B$.
Giới hạn: $N \leq 5000$ Các phần tử của hai dãy và số $M \leq 1000$.
Bài 2
Cho 3 xâu $X, Y, Z$ độ dài $N$ gồm các chữ cái thường. Tìm 3 xâu $A, B, C$ sao cho:
- $X$ có dạng $* + A + * + B + *$ ( kí tự $*$ có thể rỗng hoặc là một xâu)
- $Y$ có dạng $* + B + * + C + *$
- $Z$ có dạng $* + C + * + A + *$
- $|A| + |B| + |C|$ (tổng độ dài 3 xâu) đạt max.
Giới hạn: $N \leq 5000$.
Bài 3
Có $t$ test, mỗi test gồm ba số $n$, $m$, $k$ và bạn cần phải tạo ra một bảng kích thước $n \cdot m$, gồm các kí tự “.” và “”, mà có đúng $k$ cặp L-tromino tạo bởi kí tự “”. Nếu không tạo được thì in -1.
Giới hạn:
- $t \leq 100$
- Tổng của các $n \cdot m$ trong cùng một input không quá $10^5$.
Bài 4
Cho cây $N$ đỉnh, gốc là $1$. Đỉnh $v$ gọi là con bậc $k$ của $u$ nếu $u$ là tổ tiên của $v$ và từ $u$ đi đến $v$ phải đi qua $k-1$ đỉnh khác. Có $Q$ truy vấn:
- “I u k val” : Cộng các con từ bậc $1$ đến bậc $k$ của $u$ một lượng là $val$
- “Q u” : In ra giá trị của $u$ hiện tại.
Giới hạn: $N, Q \leq 10^5$
Ngày 2
Bài 5
Cho bảng $N$ hàng $M$ cột, mỗi ô của bảng được tô bởi một trong $2 \times M$ màu (đảm bảo có cả $2 \times M$ màu).
Độ đa sắc của một cột là số màu khác nhau có trong cột đó.
Độ đa sắc của cả bảng là max độ đa sắc của các cột.
Có thể tráo màu của hai ô mà là góc đối nhau của một hình chữ nhật $2 \times 3$ (như quân mã trong bàn cờ). Hãy tráo màu các ô trong bảng sao cho độ đa sắc của bảng là nhỏ nhất có thể.
Cần phải truy vết.
Giới hạn: $4 \leq N, M \leq 50$
Bài 6
Có $N$ đoạn thẳng song song với trục tọa độ trên mặt phẳng. Một lần đặt bút vẽ là một lần di bút mà không nhấc bút.
Tìm cách vẽ sao cho số lần đặt bút là min và mình chỉ di bút trên các đoạn thẳng đã cho.
Có truy vết.
Giới hạn: $N \leq 1000$
Tọa độ các điểm là số nguyên là có giá trị tuyệt đối $\leq 1000$.
Bài 7
Bạn có một dãy $a$ gồm $n$ phần tử và một hàm sort như sau:
void bubble_sort(int *a, int n) {
int i, j;
for (i = 0; i < n - 1; ++i) {
for (j = 0; j < n - 1; ++j) {
if (a[j] > a[j + 1]) {
/* 3 dòng sau tương ứng với một lần swap*/
int x = a[j];
a[j] = a[j + 1];
a[j + 1] = x;
}
}
}
}
Tìm cách swap hai phần tử của $a$ (không nhất thiết liên tiếp) sao cho số lần swap của bubble_sort là ít nhất.
Giới hạn: $n \leq 10^5$, các phần tử là số nguyên dương $\leq 10^9$
Bài 8
Đây là bài interactive. Cho một dãy số gồm $N$ phần tử phân biệt. Mình không biết phần tử nào cả.
Có thể hỏi $(i, j)$ và trình chấm sẽ trả về số lớn hơn. Tìm số lớn thứ $k$ của dãy.
Giới hạn:
- Sub $1$: $k = 1$, không cho biết giới hạn số câu hỏi.
- Sub $2$: $k = 2$, không cho biết giới hạn số câu hỏi.
- Sub $3$: $k = 3$, không hỏi quá $1017$ câu.
Lời giải
Ngày 1
Bài 1
Thay vì biến dãy $A$ thành dãy $B$, ta biến dãy $B$ thành dãy $A$. Thao tác bây giờ là chia cả dãy và cộng một số. Xét sub bé, $M = 2$. Ta nhận thấy là luôn chia 2 mọi lúc có thể (dễ dàng chứng minh).
Vậy thuật toán là while tồn tại một phần tử của dãy $B > A$, tăng cả dãy $B$ thành bội của 2 nhỏ nhất mà $\geq$ nó, sau đó chia 2 cả dãy.
Quay lại sub lớn.
Ta thấy có nhiều cách chọn chia cả dãy nên tạo ra nhiều điều kiện khó xử lý. Nhưng thực ra, thực hiện các phép chia theo thứ tự nào cũng cho ra một kết quả như nhau.
Vậy ta backtrack các phép chia.
(còn sol khác).
Bài 2
DP sử dụng Knuth Optimization.
Bài 3
Sub bé backtrack sub lớn tham.
Bài 4
Chia căn.
Ngày 2
Bài 5
Dưới điều kiện đã cho, dễ thấy có thể swap 2 ô tùy ý.
Gọi $a_i$ là số ô có màu $i$.
Nếu tồn tại cách ghép các $a_i$ thành $M$ cặp sao cho tổng của mỗi cặp $= N$ thì đáp án là 2.
Ngược lại, đáp án là 3. (có thể chỉ ra một cách tham).
Bài 6
Dựng cạnh ảo sau đó chạy thuật toán tìm chu trình Euler.
Bài 7
Tịnh tiến Segment tree (?)
Bài 8
Xây cây segment tree , các nút lưu max của range.