Viết bài: Trần Gia Huy Dưới đây là một số bài toán sử dụng phương pháp Quy hoạch động cơ bản mà mình đã hoặc đã từng làm, sol có thể còn sai sót mong nhận được sự thông cảm từ bạn đọc. $-arigatou$ $gozaimasu-$ Bài 1: LIS - Dãy con tăng dài nhất (bản dễ). Link chấm bài: https://oj.vnoi.info/problem/liq Cho mảng số nguyên $A$ gồm $n$ phần tử, hãy tìm dãy con (có thể không liên tiếp) tăng dài nhất của mảng $A$. Ví dụ: $A = 4, 3, 6, 7$ thì ta có độ dài dãy con tăng dài nhất là $3$.

Viết bài: Trần Gia Huy. A. Mocha and Hiking Link [https://codeforces.com/problemset/problem/1559/C]. Đề bài Thành phố mà Mocha sống được gọi là Zhijiang. Có tổng cộng $n+1$ ngôi làng và $2n-1$ con đường chỉ hướng trong thành phố này. Có hai loại đường: $n-1$ con đường từ ngôi làng thứ $i$ đến ngôi làng thứ $i+1$, cho tất cả các giá trị $1 \leq i \leq n-1$.

Giới thiệu: Disjoint Set Union (DSU) là một cấu trúc dữ liệu có thể quản lí một cách hiệu quả một tập hợp của các tập hợp. Bài toán: Cho một đồ thị có $n$ đỉnh, ban đầu không có cạnh nào. Có hai loại truy vấn như sau: $union~u~v$ - Thêm một cạnh giữa đỉnh $u$ và đỉnh $v$ trong đồ thị. $get ~u~v$ - Kiểm tra xem đỉnh $u$ và $v$ có cùng thuộc một thành phần liên thông hay không. Nếu có in ra "YES", ngược lại in "NO" (không có dấu ngoặc kép). Ý tưởng:

Bài 1: PolandBall and Forest Nguồn: https://codeforces.com/problemset/problem/755/C Tóm tắt: đếm số thành phần liên thông. Code: int n, cnt, vis[10005]; vector<int> adj[10005]; void dfs(int u) {

1. Cộng 2 số nguyên lớn Bước 1: Chuẩn hóa 2 xâu a và b để 2 xâu có độ dài bằng nhau. Xâu nào ngắn hơn thì ta thêm ký tự ‘0’ vào đầu xâu đó cho đến khi 2 xâu có độ dài bằng nhau thì dừng. Bước 2: Duyệt từ cuối xâu về đầu xâu: Khởi tạo 1 biến lưu kết quả ans. Xét từng ký tự chuyển sang kiểu int xong cộng lại và lưu vào biến sum, đồng thời khởi tạo biến carry để nhớ 1 (trong trường hợp hai số cộng lại lớn hơn 9). Tổng quát:

Lịch sử thuật toán Thuật toán Euclid là một trong những thuật toán cổ nhất được biết đến, từ khi nó xuất hiện trong cuốn Euclid’s Elements khoảng năm 300 trước công nguyên. Euclid khởi đầu đã trình bày rõ ràng vấn đề về phương diện hình học, như vấn đề tìm ra một thước đo chung cho độ dài hai đường thẳng, và thuật toán của ông đã xử lý bằng cách lặp lại phép trừ đoạn dài hơn cho đoạn ngắn hơn. Tuy nhiên, thuật toán đã hầu như không được phát hiện ra bởi Euclid và nó đã có thể được biết đến sớm hơn 200 năm. Nó cũng đã được biết đến bởi Eudoxus of Cnidus (khoảng năm 375 trước công nguyên) và Aristotle (khoảng năm 330 trước công nguyên). Thuật toán Euclid mở rộng Phương trình diophantine: $ax + by = c$ $(1)$. Định lý Bézout (Bézout’s indentify): Cho hai số nguyên $a$, $b$ khi đó luôn tồn tại hai số $x$, $y$ sao cho $ax + by = gcd(a, b)$. Xét hai số nguyên $a$, $b$ nguyên tố cùng nhau và phương trình $ax + by = 1$. Ta có thể tiến hành tìm nghiệm $x$, $y$ của bài toán. Áp dụng thuật toán tìm ước chung lớn nhất.

# Chặt tam phân (Ternary search)

(Toán rời rạc) Các khái niệm cơ bản về lý thuyết đồ thị Đồ thị gồm đỉnh và cạnh (khác với đại số chúng ta thường học trên trường) 1. Đơn đồ thị vô hướng Thông thường đồ thị hay được kí hiệu bằng chữ G (viết tắt cho chữ Graph) Người ta hay cho G = <V,E> trong đó V là tập hợp các đỉnh có trên đồ thị và E là tập hợp các cạnh. Đơn : giữa 2 đỉnh chỉ tồn tại tối đa là 1 cạnh Vô hướng : không có hướng, không có thứ tự. Bạn cứ tưởng tượng như đây là độ lớn của AB chứ không bao gồm hướng của AB.

Kiến thức cần biết DFS (Depth first search) BFS (Breadth first search) Quy hoạch động (Dynamic Programming) 1. Lý thuyết về cây Cây là đồ thị vô hướng đặc biệt có tính chất sau: Là đồ thị liên thông và không có chu trình. Luôn có 1 đường đi giữa 2 đỉnh bất kì.

Bài toán: Cho một xâu, nhiệm vụ của bạn là sắp xếp lại các ký tự của nó sao cho xâu đó trở thành một xâu đối xứng (xâu đối xứng là xâu khi đọc xuôi hoặc ngược đều như nhau). Input: Một dòng duy nhất gồm một xâu có độ dài $n$ chỉ có các ký tự chữ cái in hoa A - Z. Ràng buộc: $1 ≤ n ≤ 10^6$