# Contest Hà Nội - những bài khó

## Phương trình:
### Ăn 87,5% số test
Cày trâu, nhớ kiểm tra:
- chia hết
- dương

### Full
Giải [phương trình diophantine](https://cp-algorithms.com/algebra/linear-diophantine-equation.html) bằng Euclid mở rộng

#### Một cách khác
$2x+4y=20$
có các cặp nghiệm $(x, y)$ là:
$(2, 4); (4, 3); (6, 2); (8, 1)$

ta thấy, với mỗi cặp nghiệm, x tăng đều 2 đơn vị và y giảm đều 1 đơn vị

Để tổng quát, ta đặt $d = \gcd(a, b), a' = \dfrac{b}{d}, b' = \dfrac{a}{d}$.
Khi đó, nếu ta tìm được cặp nghiệm $(x, y)$ sao cho $ax + by = c$, thì cặp nghiệm $(x \pm a', y \mp b')$ cũng thỏa mãn. Nôm na là một bên tăng thêm $\dfrac{ab}{d}$, một bên giảm bớt để bù lại.

Vì vậy, ta tìm nghiệm $(x, y)$ với $x$ nhỏ nhất thỏa mãn phương trình trên, sau đó đếm xem có bao nhiêu cặp nghiệm nguyên dương $(x + ka', y - kb')$ thỏa mãn $(k \in \mathbb{N} = \{0, 1, 2, \dots\})$.
Đáp án có thể tính bằng cách đặt $k = \min(\dfrac{c - x}{a'}, \dfrac{y}{b'})$, đáp án là $k+1$.

Để tìm nghiệm $x$ nhỏ nhất, ta chỉ cần duyệt trâu. Lý do là:
- nếu vô nghiệm, đó là vì $c$ không chia hết cho $\gcd(a, b)$ (tính chất của phương trình Diophantine). ta chỉ cần thêm điều kiện này là xong
- ngược lại, nếu đặt $a > b$ thì tìm $x$ rất nhanh. vì sao nhanh?
- $a, b$ lớn thì duyệt ít
- $a, b$ nhỏ thì nghiệm $x$ nhỏ.

## Tìm xâu
### Tóm tắt đề
Lấy một xâu $x$ bất kì, "quay vòng tròn" nó ra được các xâu (VD `abab` quay vòng ra được `abab`, `baba`, `abab`, `baba`). Nhưng chỉ quan tâm những xâu khác nhau (tức là `abab` và `baba`). Sắp xếp tăng dần mấy xâu ni, hỏi xâu thứ $k$ là xâu nào?

### Cách giải
Từ việc hiểu rõ đề, cách làm cũng rõ ràng.
Vậy làm sao để lấy ra được các xâu **khác nhau**?
- Sau khi sắp xếp, những xâu giống nhau phải nằm liên tiếp
- `set`, `map`

## Di chuyển cây
Bước 1: đọc hiểu đề

## Tiếp cận
Tạo mảng đánh dấu `m[i][j] = true/false` tương ứng với việc ô $(i,j)$ có
thuộc một dãy dọc hoặc một dãy ngang nào không?
Sau đó thì xét từng dòng riêng, và two-pointer. (cột làm tương tự)

## Cụ thể
- Có thể xử lý riêng dòng và cột
- Xét riêng dòng $r$, bài toán đưa về: cho một mảng $a$, tìm độ dài các đoạn con liên tiếp.
- Bài toán con này giải được trong $O(n)$ bằng khá nhiều cách:
+ two-pointer
+ Đặt `f[i] = ` số lượng số liên tiếp, bằng với $a[i]$ (nằm ở bên trái nếu duyệt $i$ từ trái sang phải)

## Biến đổi xâu kí tự

Hình dung: bảng HCN có kích thước $n$ hàng, $d$ cột, mỗi ô chứa một kí tự.
Giả sử chọn xâu thứ $i$ làm "xâu gốc". Giữ lại một vài kí tự của xâu này, còn những vị trí khác lấy từ các xâu $j \neq i$ (bằng cách tráo).
Để dùng ít thao tác nhất thì: những vị trí nào trong xâu thứ $i$ **đã giống** xâu mẫu $s$ rồi thì không cần đổi.
Cần kiểm tra tại những vị trí (cột) còn lại, trên các xâu khác $i$ có chứa kí tự **cần tìm** không?

## Xây dựng đường băng
Đặt $a[i][j] = |h - a[i][j]|$ (chênh lệch độ cao)
Kích thước đường băng bằng đúng $d,r$.
Lưu ý có thể xoay theo hai chiều ngang/dọc, ($d$ dòng $r$ cột hoặc $r$ dòng $d$ cột).
Tổng tiền tố hai chiều.

## Trồng cây
Bài khó. Xem ở đây:
[Trồng cây (HSG9-2014, Hà Nội)](/ZHP9mjTRTWKZ0Dmk2nh8OA)