Chọn ĐT HSG QG Đà Nẵng 2026–2027 Ngày 1

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 Chọn cứ điểm 6 (p) 1.0s 256M
2 Đếm hậu tố 7 (p) 1.0s 256M
3 Tổng trọng số 7 (p) 1.0s 256M

1. Chọn cứ điểm

Điểm: 6 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: PHAOBINH.INP Output: PHAOBINH.OUT

Trong chiến dịch Điện Biên Phủ, ngày 30 tháng 3 năm 1954 quân ta đồng loạt tấn công các cứ điểm phía Đông phân khu trung tâm như đồi E1, D1, C1, C2, A1... Ta chiếm phần lớn các cứ điểm của địch, tạo điều kiện để bao vây, chia cắt và khống chế địch. Sau đợt này, Mỹ khẩn cấp viện trợ cho Pháp tăng cường lực lượng để tái chiếm. Trước tình hình khẩn cấp, ban chỉ huy chiến dịch đã lên kế hoạch phòng thủ bằng cách đưa pháo lên các cứ điểm cao...

Sau giờ học, Tý say sưa trong bài giảng môn Lịch sử nên nghĩ ra bài toán nhờ các bạn tìm lời giải như sau:

Cho \(n\) cứ điểm được đánh số từ \(1\) đến \(n\), cứ điểm thứ \(i\) có độ cao \(h_i\). Tý muốn chọn \(3\) cứ điểm \(x, y, z\) và đặt pháo tại đỉnh cứ điểm \(y\) sao cho \(1 \le x < y < z \le n\) và \(h_x < h_y > h_z\). Tý muốn đặt pháo tại cứ điểm \(y\) cao hơn hai bên để có thể phòng thủ được hai cứ điểm \(x\) và \(z\) thấp hơn.

Yêu cầu: Hãy đếm có bao nhiêu cách chọn bộ cứ điểm \((x, y, z)\) thỏa mãn điều kiện trên.

Input — PHAOBINH.INP

  • Dòng đầu tiên ghi số \(n\) (\(3 \le n \le 3 \cdot 10^5\)) là số cứ điểm.
  • Dòng tiếp theo chứa \(n\) số nguyên không âm \(h_1, h_2, \dots, h_n\) (\(0 \le h_i \le 10^{18}\)) lần lượt là độ cao của cứ điểm thứ \(i\).

Output — PHAOBINH.OUT

  • Ghi ra một số nguyên duy nhất là số lượng cách chọn bộ cứ điểm \((x, y, z)\) thỏa mãn.

Example

Test 1

Input 
5
10 18 18 10 18
Output 
2
Note

Các bộ cứ điểm: \((1, 2, 4)\) và \((1, 3, 4)\).

Test 2

Input 
6
15 2 60 0 60 7
Output 
7
Note

Các bộ cứ điểm: \((1, 3, 4)\), \((1, 3, 6)\), \((1, 5, 6)\), \((2, 3, 4)\), \((2, 3, 6)\), \((2, 5, 6)\) và \((4, 5, 6)\).

Scoring

  • Có \(15\%\) số điểm với \(h_i\) không giảm, tức là \(h_i \le h_{i+1}\) với mọi \(1 \le i < n\).
  • Có \(35\%\) số điểm với \(n \le 500\).
  • Có \(30\%\) số điểm với \(n \le 10^4\).
  • Có \(20\%\) số điểm còn lại không có ràng buộc gì thêm.

2. Đếm hậu tố

Điểm: 7 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: HAUTO.INP Output: HAUTO.OUT

Cho \(n\) xâu \(s_1, s_2, s_3, \dots, s_n\) khác rỗng. Mỗi xâu chỉ gồm các chữ cái tiếng Anh in thường từ a...z. Các xâu trong danh sách có thể giống nhau.

Có \(q\) truy vấn, mỗi truy vấn gồm một xâu \(p\) khác rỗng và một số nguyên dương \(k\), xét tất cả các xâu \(s_i\) thỏa mãn:

  • \(p\) là tiền tố của \(s_i\), một xâu được coi là tiền tố của chính nó;
  • \(|s_i| \ge k\).

Từ mỗi xâu thỏa mãn, lấy đúng \(k\) ký tự cuối và đếm số lượng hậu tố phân biệt thu được.

Input — HAUTO.INP

  • Dòng đầu tiên chứa hai số nguyên \(n, q\) (\(1 \le n, q \le 2 \times 10^5\)).
  • Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa xâu \(s_i\) (tổng độ dài của tất cả các xâu \(s_i\) không vượt quá \(5 \times 10^5\)).
  • Trong \(q\) dòng tiếp theo, dòng thứ \(j\) chứa xâu \(p_j\) (tổng độ dài của tất cả các xâu \(p_j\) không vượt quá \(5 \times 10^5\)) và số nguyên \(k_j\) (\(1 \le k_j \le 5 \times 10^5\)).

Output — HAUTO.OUT

  • Ghi ra \(q\) dòng tương ứng với kết quả mỗi truy vấn là số lượng hậu tố phân biệt thu được.

Example

Test 1

Input 
6 6
abc
axbc
abca
abbc
bc
abc
a 2
ab 1
abc 3
b 2
z 1
a 5
Output 
2
2
2
1
0
0
Note
  • Với truy vấn a 2, có năm xâu phù hợp tạo ra các hậu tố bc, bc, ca, bc, bc. Có hai hậu tố phân biệt là bc và ca nên đáp án bằng \(2\).
  • Với truy vấn abc 3, có ba xâu phù hợp tạo ra các hậu tố abc, bca, abc. Có hai hậu tố phân biệt là abc và bca nên đáp án bằng \(2\).
  • Với truy vấn z 1, không có xâu nào bắt đầu bằng z nên đáp án bằng \(0\).
  • Với truy vấn a 5, không có xâu bắt đầu bằng a và dài ít nhất \(5\) nên đáp án bằng \(0\).

Ràng buộc

  • \(40\%\) số điểm với \(1 \le n, q \le 200\) và \(|s_i|, |p_j| \le 200\) với mọi \(i, j\).
  • \(15\%\) số điểm với \(k_j = 1\) với mọi \(1 \le j \le q\).
  • \(15\%\) số điểm với \(p_1 = p_2 = p_3 = \dots = p_q\).
  • \(15\%\) số điểm với \(k_1 = k_2 = k_3 = \dots = k_q\).
  • \(15\%\) số điểm còn lại không có ràng buộc nào thêm.

3. Tổng trọng số

Điểm: 7 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: TRONGSO.INP Output: TRONGSO.OUT

Cho một đồ thị dạng cây gồm có \(n\) đỉnh (đánh số từ \(0\) đến \(n - 1\)), được kết nối bởi \(n - 1\) cạnh, cạnh thứ \(i\) có trọng số \(w_i\). Lần lượt các cạnh được đánh số từ \(1\) đến \(n - 1\) theo thứ tự xuất hiện trong dữ liệu vào.

Thực hiện \(m\) thao tác thuộc một trong ba dạng sau:

  • C i x: Thay đổi trọng số của cạnh thứ \(i\) thành giá trị \(x\);
  • N u v: Đổi dấu trọng số trên tất cả các cạnh thuộc đường đi đơn từ đỉnh \(u\) đến đỉnh \(v\) (giá trị trọng số \(w\) đổi dấu từ \(w \to -w\) và ngược lại từ \(-w \to w\));
  • SUM u v: Tính tổng trọng số các cạnh trên đường đi từ đỉnh \(u\) đến đỉnh \(v\).

Input — TRONGSO.INP

  • Dòng đầu chứa số nguyên \(n\) (\(1 \le n \le 2 \times 10^4\)), là số lượng đỉnh của đồ thị;
  • \(n - 1\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(u_i, v_i, w_i\) (\(0 \le u_i, v_i < n\), \(|w_i| \le 1000\)) là cạnh thứ \(i\) nối giữa đỉnh \(u_i\) và đỉnh \(v_i\), có trọng số \(w_i\).
  • Dòng tiếp theo chứa số nguyên \(m\) (\(1 \le m \le 2 \times 10^4\)) là số thao tác thực hiện.
  • \(m\) dòng tiếp theo, mỗi dòng chứa thao tác thuộc một trong ba dạng: C i x; N u v; SUM u v.

Output — TRONGSO.OUT

  • Ghi ra tổng trọng số tính được của thao tác SUM, mỗi kết quả ghi trên một dòng.

Example

Test 1

Input 
3
0 1 1
1 2 -2
5
SUM 0 2
N 0 2
SUM 0 2
C 1 3
SUM 0 2
Output 
-1
1
5

Scoring

  • \(30\%\) số điểm với \(n, m \le 10^3\).
  • \(30\%\) số điểm với đồ thị có dạng đường thẳng.
  • \(40\%\) số điểm còn lại không có ràng buộc nào thêm.