# Lời giải contest ITK23F1

## SUMN

~~Không biết nên ghi gì...~~
Thay vì nhập $N$ ở kiểu `int`, hãy nhập kiểu `string` rồi duyệt qua các chữ số của $N$ để cộng vào kết quả.
~~Dễ quá nên không có ý tưởng viết sol, chắc không cần code mẫu đâu he~~

## STRL

### Cách 1: ~~dành cho người lười~~
---
- Tạo 1 `set<char> se`.
- Duyệt qua xâu $S$, nhét hết các kí tự vào `se` (`se.insert(S[i])`).
- Kết quả là `se.size()`.

### Cách 2:
---
- Tạo một `vector<bool> check(256, false)` để kiểm tra kí tự $x$ có tồn tại trong xâu hay không.
- Duyệt qua tất cả các kí tự của xâu $S$, đặt `check[S[i]] = true`.
- Kết quả là số phần tử có giá trị `true` trong `check`.

## Chia kẹo
**quy ước $a < b < c < d$**
### với $k = 1$

kết quả đơn giản chỉ là $1$

### với $k = 2$

#### thuật 1 - $O(n)$
duyệt qua tất cả giá trị của $a$ khi đó $b = n - a$, nên chỉ cần kiểm tra thử $a < b$ không.

#### thuật 2 - O(1) - liên quan đến $k = 4$
gọi hàm $calc$ là cách tính số cặp có tông bằng $n$: `calc(n)`
- nếu $n \le 0$ thì kết quả là 0 (phục vụ $k = 4$)
- nếu $n$ chẳn thì $a \in [1..n/2-1]$ vì $a < b$ (n/2 - 1 vì để bỏ trường hợp $a = n/2 => b = n/2$) nên kết quả là $n/2 - 1$
- nếu $n$ lẻ thì sẽ không xuất hiện $a = b = n/2$ nên kết quả là $n/2$(làm tròn xuống)

### với $k = 3$
#### thuật $O(n^2)$
duyệt qua hết các trường hợp $a, b$ khi đó $c = n - a - b$, nên chỉ cần kiểm tra $b < c$

### với $k = 4$
#### thuật $O(n^2)$
- với biểu thức $a + b + c + d = n$, ta duyệt qua tất cả giá trị $a, b$
- biến đổi về $c + d = n - a - b$
- gọi $c = x + b, d = y + b$ để đảm bảo tính $c, d$ luôn lớn hơn $b$
- ta có biểu thức $x + b + y + b = n - a - b \Leftrightarrow x + y = n - a - 3 \times b$
- a, b đã được xác định bởi `2 for` lồng nhau $=> ans = ans + calc(n - a - 3 \times b)$
## Dãy con tăng dài nhất

### brute:
#### hướng
Gọi $dp[i]$ là độ dài của dãy con tăng dài nhất kết thúc tại vị trí $i$.
Ta có công thức truy hồi:
$$
\begin{align*}
dp[1] &= 1 \\
dp[i] &= 1 + \max(dp[j]); \forall j \in [1, i-1], a[j] < a[i]
\end{align*}
$$
#### độ phức tạp: $O(n^2)$

### full:
#### hướng
Trong công thức ở trên, nếu ta gán $B(dp(i)) = A(i)$ thì ta sẽ có mảng $B$ với ý nghĩa:

- $B(k)$ là giá trị kết thúc của dãy con tăng độ dài $k$ (tại thời điểm đang tính).

Có thể chứng minh rằng $B$ là dãy tăng. Giả sử đang duyệt đến vị trí $i$, đã tính được $dp(i) = k$. Ta gán $B(k) = A(i)$ như trên. Nếu có $B(k) \geq B(k + 1)$ thì ta đã tính $dp(i)$ sai, vì trước $A(i)$ có một phần tử $A(j) \leq A(i)$ mà lại có $dp(j)$ lớn hơn $dp(i)$. Tương tự, cũng có thể thấy $B(k - 1) \geq B(k)$ là điều vô lý.

Từ nhận xét $B$ là dãy tăng, ta sử dụng tìm kiếm nhị phân để tìm dãy con tăng dài nhất trong $O(N \log N)$ như sau:

1. Khởi tạo dãy $B$ có $N$ phần tử, với $B(0) = -\infty$, và các phần tử khác bằng $+\infty$.
2. Duyệt $i$ từ 1 đến $N$, mỗi lần duyệt ta tìm vị trí $k$ đầu tiên có $B(k) \geq A(i)$ (sử dụng tìm kiếm nhị phân), gán $B(k) = A(i)$ (và $dp(i) = k$ nếu cần).
3. Độ dài dãy con tăng dài nhất là vị trí $k$ cuối cùng mà $B(k) \neq +\infty$, hoặc cũng có thể lấy giá trị lớn nhất trong quá trình duyệt.

~~dài dòng là vậy chứ thằng viết dùng set~~

**có thể làm bằng fenwick tree hay segtree bằng công thức truy hồi khác**
#### độ phức tạp: $O(n.log(n))$
## ZERON
### hướng:

1. **Khởi Tạo:**
- Bạn cần kiểm tra tất cả các cách chèn các dấu `+`, `-`, và `!` vào giữa các số từ 1 đến $N$. Tổng số cách có thể là $3^{N-1}$.

2. **Tạo Các Kết Hợp Dấu:**
- Sử dụng phương pháp quay lui (backtracking) để thử tất cả các kết hợp của dấu:
- Bắt đầu từ vị trí đầu tiên và thử tất cả các dấu cho từng vị trí giữa các số.
- Đệ quy đến vị trí tiếp theo cho đến khi tất cả các vị trí đều đã được gán dấu.

3. **Xây Dựng Biểu Thức:**
- Sau khi chèn tất cả các dấu, xây dựng biểu thức từ mảng dấu đã tạo.
- Biểu thức sẽ được tạo thành bằng cách nối các số với các dấu đã chèn.

4. **Tính Giá Trị Biểu Thức:**
- Xử lý các dấu:
- Dấu `!` được sử dụng để kết hợp các số thành một số lớn hơn.
- Dấu `+` và `-` được sử dụng để thực hiện phép cộng và trừ.
- Tính tổng của biểu thức và kiểm tra nếu tổng bằng 0.

~~code của thằng viết~~

ll res = 0, tmp = 1, p = 1;
for (int i = 2; i <= n; ++i) 
    {
    if (v[i] == '!') 
    {
        tmp = tmp * 10 + i;
    } else 
    {
        res += p * tmp;
        tmp = i; 
        if (v[i] == '+') p = 1;
        else p = -1;
    }
}
res += p * tmp;

5. **Lưu Trữ Kết Quả:**
- Sử dụng một tập hợp để lưu các biểu thức đã tính để đảm bảo tính độc nhất.
- Nếu một biểu thức đã tồn tại trong tập hợp, không cần tính toán lại.

6. **Đếm và In Kết Quả:**
- Đếm số lượng các biểu thức thỏa mãn điều kiện tổng bằng 0.
- In tất cả các biểu thức đã tìm được.

~~cảm ơn chatgpt đã giúp vài chữ đơn giản của thằng viết thành 1 bài văn~~
### độ phức tạp: $O(3^{N-1})$