Link livestream lời giải: Bài 1 Chuyên tin (path) Bài 1 Không chuyên (string): Bài 2,3 Không chuyên, bài 4 là bài 1 CT: Đố vui - string Đề bài: Cho một xâu $s$, tạo xâu $t = s + s$ sau đó chèn thêm một kí tự vào $t$ (ở vị trí bất kỳ) để tạo nên xâu $z$. Cho xâu $z$, tìm xâu $s$, hoặc thông báo là (vô nghiệm, nhiều hơn 1 $s$ thỏa mãn)

Cày trâu: $O(n \log)$ Toán: Ý tưởng: mỗi chữ số đóng góp bao nhiêu lần vào kết quả cuối cùng VD: $n = 273$, nếu cày trâu thì cần chạy for $i$ từ $1$ tới $n$ để lấy ra các chữ số Toán: Xét chữ số $1$:Hàng đơn vị: $1$: $28$ số (phần $$ chạy từ $0..27$) Hàng chục: $1:$ $30$ số (phần $**$ chạy từ $0..29$)

Hai bài contest GRID và hai bài từ OLP sinh viên https://lqdoj.edu.vn/problem/dhbbspell https://lqdoj.edu.vn/problem/labudovi https://oj.vnoi.info/problem/olp_kc22_smartshop https://oj.vnoi.info/problem/olp_ct22_roadimpro SPELL BFS theo 3 chiều. Đặt $d(x,y,z) = t:$ tới ô $(x,y)$, đã viết được $z$ kí tự của xâu thì cần tối thiểu là $t$ bước LABUDOVI

Đề 2016 Bài 1 (khối 10): quân mã BFS, tuy nhiên ở trên bảng 2 chiều chứ ko phải đồ thị thường. Coi mỗi ô như một "đỉnh", còn cách di chuyển của quân mã là "cạnh". Bài 2 (k10): tải trọng Đề yêu cầu tìm đường đi "sao cho tải trọng cho phép của xe lưu thông trên hành trình đó là lớn nhất có thể" Nói cách khác, để $\min$ trọng số cạnh đạt $\max$. Những bài có đề như thế này có thể TKNP trên đáp án.

Bài toán: Tìm đoạn con dài nhất/ ngắn nhất thỏa mãn tính chất A Tổng liên tiếp https://lqdoj.edu.vn/problem/sumconset Tính chất tăng dần: Do $a>0$ nên ... Trâu Hai con trỏ

Chưa chắc là tôi đã đủ trình nghĩ & code được những điều này trong phòng thi. - Lê Tăng Phú Quý Tham khảo thêm lời giải chất lượng từ VNOI Bài 1: Chuỗi ADN Đề bài Điền vào các vị trí ? để đạt được độ đa dạng lớn nhất. Độ đa dạng: Số lượng xâu con "phức tạp" Xâu con phức tạp: xâu con chứa $\ge$ hai loại kí tự khác nhau

LA Bờ le Tìm các TPLT mạnh, đồng thời đếm xem mỗi TP có bao nhiêu đỉnh (mảng cnt). Đếm số đường đi chính là QHĐ trên DAG: Lấy ra thứ tự topo và chạy một vòng for để cập nhật từ đỉnh đã tính tới đỉnh sau đó (f[v] += f[u]) Hoặc gọi đệ quy theo cung ngược Trường hợp $\infty$ ? Nếu cnt[u] > 1 và $f_u > 0$ thì gán ngay $f_u = \infty$ FOODS

Không dễ nghĩ ra hướng làm ngay, cần thử trâu. $n \le 10$ Mỗi cách trồng lại cây là một hoán vị $\rightarrow$ duyệt qua toàn bộ $n!$ hoán vị. Backtrack/ next_permutation $O(n^2)$ Tiếp cận Dễ thấy trường hợp đặc biệt, khi vị trí bị cố định nằm "đúng chỗ" thì đáp án là hiệu giữa $\max$ và $\min$. "Đúng chỗ" tức là, nếu gọi $a'$ là mảng chứa các giá trị của $a$ được sắp xếp tăng, thì $a_k = a'_k$

Đề HSG HN Triển lãm Giả sử chọn các bức tranh có: kích thước nhỏ nhất là $A$ lớn nhất là $B$ (chữ $A,B$ khác mảng $a,b$ của đề) thì nên lấy luôn tất cả bức tranh có kích thước $\ge A$ và $\le B$ (vì tranh nào cũng có giá $b_i > 0$, chọn các tranh này không làm tăng chênh lệch $a_{\max} - a_{\min}$)

sau Tết Mô hình chung while (l <= r) { mid = (l+r) / 2 check(mid); } Cái khó của mỗi bài nằm ở hàm check Tài liệu

Subtask 1: $n = 1$ Chỉ cần tính diện tích của tam giác. Giải trong $O(1)$. Không nên dùng công thức Heron vì sai số lớn, nên sử dụng tích chéo. ??? success "Code mẫu" ```cpp #include<bits/stdc++.h> using namespace std; #define all(v) (v).begin(), (v).end()

Nhận thấy: Vì $n$ rất lớn nên không thể nào duyệt qua $n!$ hoán vị và kiểm tra được. Ta buộc phải suy luận ra tập các hoán vị thỏa mãn từ dãy $s$ đã cho. Subtask 1: $k = 2, \Sigma n \leq 5000$ Nếu biết được $p_1$ thì sẽ có $p_2 = s_1-p_1$. Từ đó có $p_3 = s_2-p_2$. Cứ như vậy sẽ tính được toàn bộ $p$ bằng công thức $p_{i+1} = s_i - p_i$. Ta duyệt qua $O(n)$ giá trị của $p_1$, sau đó lại tốn $O(n)$ phép tính để tính các giá trị của $p$. Lọc ra được tối đa $n$ hoán vị thỏa mãn (có các giá trị nằm trong phạm vi $[1,n]$). Vì tất cả đều có $p_1$ khác nhau nên chi phí so sánh là $O(1)$ và ta dễ xác định được hoán vị thứ $x$ Độ phức tạp $O(n^2)$ Subtask 2: $k = 2, \Sigma n \leq 10^5$

Một cấp số cộng được xác định khi ta biết số đầu tiên ($a$), và công bội ($d$). Subtask 1: Duyệt qua $O(n)$ giá trị của $a$ và $O(n)$ giá trị của $d$. Nhận thấy độ dài dãy tối đa là: $t = \left\lfloor\frac{N-a}{d}\right\rfloor + 1$ vì các giá trị nằm trong đoạn $[0,N]$ Vậy, với cặp $(a,d)$ bất kì, ta cộng vào đáp án một lượng $t$ (có $t$ dãy cấp số cộng với độ dài lần lượt là $1,2,3,\dots,t$) ĐPT: $O(n^2)$

Note: Subtask còn khủng hơn cả thuật full. Subtask 1 $n \le 5$ nên ta có thể cày trâu. Ta có hàm đệ_quy(vector<int> a), $a$ là danh sách các chỉ số chưa bị xóa. Giả sử mảng $a$ có $k (1 < k \le n)$ phần tử. Tại đây ta xét qua mọi khả năng như đề bài đã chỉ ra : Duyệt qua $k \cdot (k-1) / 2$ cặp lá bài, với mỗi cặp chọn xóa đi một trong hai lá bài nên có $2$ khả năng. (đương nhiên ta sẽ chọn số nhỏ hơn trong hai số $R[i] \oplus B[j]$ và $R[j] \oplus B[i]$ để tính vào chi phí). Từ một hàm đệ_quy(vector<int> a) ta gọi đệ quy tới $k(k-1)$ hàm khác. Phân tích độ phức tạp: Mỗi hàm đệ quy với $a$ có $k$ phần tử sẽ gọi đệ quy tới $k(k-1)$ hàm đệ quy, với những dãy $a'$ có $k-1$ phần tử. Số lần gọi hàm khác nhau là $n(n-1) \times (n-1)(n-2) \times \dots = n!(n-1)!$. Với mỗi cặp lá bài được chọn, tốn chi phí $O(n)$ để xóa đi một lá bài