# Solution Giao lưu Tin học trẻ Mở rộng 2023 Lần 1 - Bảng C (1&2)

## Bignum
Bài đơn giản nhưng cần lưu ý:
- Số $0$
- Không thể nhân hết $n$ số lại rồi mới `if`. Giả sử cho test max: $n = 10^5, a = 10^{18}$ thì tích rất lớn ($10^{18n}$), do đó các phép tính nhân chạy rất chậm
- Nếu dùng `C++`, để kiểm tra $ab > c$ với $a,b$ là 2 số `long long`, có thể chuyển thành phép chia.

## Đoạn đường nhàm chán
### Đề bài
Đếm số đoạn con có không quá $k$ giá trị phân biệt.
**Lưu ý** số $\theta$ có công dụng là cho biết đang giải subtask mấy

### Subtask 2
Để xác định một đoạn con, cần biết được hai chỉ số $l,r$. Vậy ta `for` $l,r$. Với mỗi $l$, ta có một mảng đếm phân phối để biết được giá trị nào đã được thêm vào. Khi $r$ tăng dần thì cộng dần vào mảng này.

theta = int(input())
n,k = map(int, input().split())
h = list(map(int, input().split()))

ans = 0
for i in range(n):
	dpp = [0]*(n+1)
	cnt = 0
	for j in range(i,n):
		dpp[h[j]] += 1 # thêm vào 1 lần xuất hiện của h[j]
		if dpp[h[j]] == 1: cnt += 1 # h[j] mới được thêm lần đầu!
		if cnt > k: break
		ans += 1

print(ans)

### Subtask 3: chiều cao khác nhau
Số giá trị = độ dài đoạn $\rightarrow$ bao nhiêu đoạn con độ dài $\le k?$

### Subtask 4: $k = 1$
Điều kiện $\Leftrightarrow$ đoạn con gồm các phần tử giống nhau
Một số hướng:
+ Tính $f[i]$ là vị trí xa $i$ nhất về bên trái mà từ $f[i]$ tới $i$ có giá trị như nhau
+ Lấy ra các đoạn liên tiếp giống nhau & tính

### Thuật chuẩn
Subtask 3,4 được dùng để vét thêm điểm nếu không nghĩ được thuật full.

Từ ý tưởng của subtask 2: chạy for $j$ để tìm vị trí xa nhất có thể.
Nhận thấy việc chạy như vậy là kém hiệu quả vì: khi $i$ tăng thì vị trí xa nhất có thể cũng phải tăng (vì sao?)
Minh họa:
i chạy thì "biên giới" cũng chạy theo
(vì bớt đi một số $a[i]$ nên mở ra nhiều khả năng cho những số phía sau hơn? ...)

Code tham khảo:

## Quý Mão 2023

### Đề bài
Đếm số đoạn con liên tiếp, các phần tử cách nhau $e$ đơn vị mà có tích là SNT.
Với subtask 1 và 2, $a \le 10^3$ nên có thể kiểm tra SNT trâu.
### Subtask 1: $n \le 200, a\le 1000$
Chạy trâu, duyệt qua $O(n^2)$ cặp số $(j,k)$ và kiểm tra.
Điều kiện đề bài cho tương ứng với: trong các số liên tiếp đó có **đúng một** số nguyên tố và các số còn lại đều bằng $1$
### Subtask 2: $e = 1, a \le 1000$
Bước nhảy $e = 1 \Rightarrow$ Chỉ xét những đoạn con liên tiếp mà có đúng 1 SNT.

Ta chỉ quan tâm những vị trí nào mà là số nguyên tố. Để tạo được một đoạn thỏa mãn, ta duyệt về phía bên trái & phải và thêm vào một vài số $1$ liên tiếp nhau.

Đặt $l(i)=j$ là vị trí xa nhất về bên trái, mà tất cả các số từ $j$ tới $i$ đều bằng $1$.
Tương tự có $r(i)$, cho bên phải.
Giả sử từ vị trí $i$ có $a[i]$ là SNT, bên trái có thể chọn tối đa $L$ số $1$ (trước khi tới tận cùng mảng hoặc gặp số khác $1$), bên phải có thể chọn tối đa $R$ số. Như vậy số đoạn con thỏa mãn là $L + R + LR$.

### Subtask 3:
$e$ không quan trọng vì cách tính hoàn toàn như trên. Phần này chỉ đòi hỏi phải sàng nguyên tố trước.

## Lướt sóng
### Subtask 1: $n \le 20$
Đệ quy quay lui, mỗi đợt có thể chọn/ không chọn. ĐPT $O(2^n)$ hoặc $O(n.2^n)$
### Subtask 2: $n \le 1000$
QHĐ: bài toán đếm/ tối ưu
Thử tiếp cận bằng cách đặt $f(i)$ : xét trong $i$ số đầu tiên, chọn được nhiều nhất là bao nhiêu số?
Tuy nhiên không viết được công thức (vì không quản lí được điều kiện tổng tạo được luôn $\ge 0$)
Vì cần biết tổng đang là bao nhiêu nên có thể đặt như sau:
$f(i,s) = x$ trong $i$ đợt đầu, tổng lợi nhuận đang là $s$ thì chọn được nhiều nhất là $x$.
Vì tổng quá lớn nên có thể đổi cách gọi hàm QHĐ thành như sau:
$f(i,x) = s$ giả sử trong $i$ số đầu tiên, chọn ra $x$ số (mà thỏa điều kiện) thì tổng cuối cùng lớn nhất là bao nhiêu?

### Subtask 3: $n \le 10^5$
Cứ "vào lệnh" liên tục, lúc nào âm tiền (tổng âm) thì quay ngược lại quá khứ và hủy lệnh trước đó (số bé nhất).
Một bài tương tự (gần đây), các bạn có thể tham khảo lời giải trên Blog CF
https://codeforces.com/contest/1779/submission/187766175

### Lưu ý: Vì chưa kịp viết, và mình mặc định những bạn hướng tới việc giải được các bài này khá giỏi nên mình viết khá gọn.
## Sắp xếp
Bạn cần làm subtask 1 trước. Từ đó sẽ thấy các thao tác tìm vị trí có thể tối ưu được bằng segment tree

## Trà sữa
Dùng thuật toán Tarjan để tìm cầu, từ đó nén thành một cây.
Nhận xét: Đáp án của bài toán trên đồ thị dạng cây là trọng số lớn nhất trong $n$ đỉnh.
Có nhiều cách để định chiều cạnh, trong đó một cách đơn giản là sử dụng các cạnh của dfs-tree (theo đúng thứ tự duyệt dfs)