Đề thi chọn ĐT HSG QG Đà Nẵng

Bài toán dãy con chung dài nhất (LCS) là một bài toán nổi tiếng trong khoa học máy tính. Mọi sinh viên khoa học máy tính ở LQDOJ đều biết bài toán này. FOS cũng vậy.

Nhớ lại rằng một dãy con của một xâu \(S\) có được bằng cách xóa một số ký tự khỏi \(S\). Cho hai xâu \(S\) và \(T\), bài toán LCS là tìm xâu dài nhất là xâu con của cả \(S\) và \(T\).

FOS thích việc tìm ra những vấn đề khó hơn từ một vấn đề quen thuộc. Lần này, dựa trên vấn đề LCS, anh ấy đã nghĩ ra vấn đề sau:

Cho hai xâu \(S\) và \(T\), có bao nhiêu LCS phân biệt của \(S\) và \(T\)?. Viết một chương trình để giúp FOS giải quyết vấn đề này. Vì kết quả có thể rất lớn, bạn chỉ cần in phần còn lại của kết quả khi chia cho \(20030101\).

Input

• Dòng đầu tiên chứa số nguyên \(t\ (1 \leq t \leq 10)\), số lượng test case. Sau đó, có \(t\) nhóm dòng, mỗi nhóm dòng chứa 1 test case.
• Mỗi test case bao gồm hai dòng
  • dòng đầu tiên chứa xâu \(S\)
  • dòng thứ hai chứa xâu \(T\).
• Hai xâu chỉ bao gồm các ký tự viết thường và độ dài của mỗi xâu có tối đa \(1000\) ký tự.

Output

• Đối với mỗi trường hợp thử nghiệm, in một dòng duy nhất chứa hai số là độ dài của LCS và phần còn lại của số lượng LCS phân biệt của \(S\) và \(T\) khi chia lấy dư cho \(20030101\).

Scoring

• Subtask 1 (50%): \(1 \leq |S|,|T| \leq 20\)
• Subtask 2 (30%): \(1 \leq |S|,|T| \leq 200\)
• Subtask 3 (20%): \(1 \leq |S|,|T| \leq 1000\)

Example

Sample input

2
acbd
acbd
fosfos
fos

Sample output

4 1
3 1

Nguồn: Bài 1 ngày 1 đề chọn ĐT HSG QG TP.ĐN 2022-2023

Cho một hoán vị \(p_1,p_2,…,p_n\). Bạn cần trả lời \(q\) truy vấn. Truy vấn thứ \(i\) là một cặp số nguyên (\(l_i,r_i\) ), bạn cần tính \(f(l_i,r_i )\).

Gọi \(m_{l,r}\) là vị trí của phần tử lớn nhất trong đoạn \(p_l,p_{l+1},…,p_r\)

\(f(l,r)=(r-l+1)+f(l,m_{l,r}-1)+f(m_{l,r}+1,r)\) nếu \(l \leq r\) và bằng 0 trong trường hợp ngược lại .

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1 \leq n, q \leq 10^6\)) - kích thước của hoán vị \(𝑝\) và số lượng truy vấn.
• Dòng thứ hai chứa \(n\) các số nguyên đôi một phân biệt \(p_1,p_2,…,p_n\) \((1 \leq p_i \leq n, p_i \neq p_j \forall i \neq j)\) - hoán vị \(p\).
• Dòng thứ ba chứa \(q\) số nguyên \(l_1,l_2,…,l_q\) – giá trị \(l\) của các truy vấn.
• Dòng thứ tư chứa \(q\) số nguyên \(r_1,r_2,…,r_q\) – giá trị \(r\) của các truy vấn.
• Đầu vào đảm bảo rằng \(1 \leq l_i \leq r_i \leq n\) cho tất cả các truy vấn.

Output

• In \(q\) số nguyên - các giá trị \(f(l_i,r_i )\) cho các truy vấn tương ứng.

Scoring

• Subtask 1 (40%): \(1 \leq n, q \leq 500\)
• Subtask 2 (30%): \(1 \leq n, q \leq 5000\)
• Subtask 3 (20%): Hoán vị được sắp xếp tăng dần hoặc giảm dần
• Subtask 4 (10%): Giới hạn gốc

Example

Sample input

4 5
3 1 4 2
2 1 1 2 1
2 3 4 4 1

Sample output

1 6 8 5 1

Nguồn: Bài 2 ngày 1 đề chọn ĐT HSG QG TP.ĐN 2022-2023

Có \(n\) bóng đèn trên một đường thẳng, được đánh số từ \(1\) đến \(n\). Mỗi bóng đèn có trạng thái ban đầu là tắt \((0)\) hoặc mở \((1)\).

Bạn đã cho \(k\) tập con \(A_1, \ldots, A_k\) là tập con của tập \({1, 2, \ldots, n}\), sao cho giao của ba tập hợp con bất kỳ là trống. Nói cách khác, với mọi \(1 \leq i_1 < i_2 < i_3 \leq k\) thì \(A_{i_1} \cap A_{i_2} \cap A_{i_3} = \emptyset\).

Trong một thao tác, bạn có thể chọn một trong số \(k\) tập hợp con và chuyển đổi trạng thái của tất cả các đèn trong đó. Đảm bảo rằng, với các tập hợp con đã cho, có thể làm cho tất cả các bóng đèn được bật đồng thời bằng các hoạt động này.

Gọi \(m_i\) là số thao tác tối thiểu bạn phải làm để \(i\) đèn đầu tiên được bật đồng thời. Lưu ý rằng không có điều kiện đối với trạng thái của các đèn khác (từ \(i + 1\) và \(n\)), chúng có thể tắt hoặc mở.

Bạn phải tính toán \(m_i\) cho tất cả \(1 \leq i \leq n\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\ (1 \leq n, k \leq 3 \cdot 10^5)\).
• Dòng thứ hai chứa một chuỗi nhị phân có độ dài \(n\), đại diện cho trạng thái ban đầu của mỗi đèn (đèn \(i\) tắt nếu \(s_i=0\), ngược lại nếu \(s_i=1\)).

• \(k\) nhóm dòng tiếp theo, mỗi nhóm dòng mô tả một tập hợp con theo, ở định dạng sau:

  • Dòng đầu tiên của mô tả chứa một số nguyên \(c\ (1 \leq c \leq n)\) - số phần tử trong tập hợp con.
  • Dòng thứ hai của mô tả chứa \(c\) các số nguyên riêng biệt \(x_1,…,x_c\ (1 \leq x_i \leq n)\) - các phần tử của tập hợp con.

• Dữ liệu được đảm bảo rằng:

  • Giao của ba tập hợp con bất kỳ là trống.
  • Có thể làm cho tất cả các đèn hoạt động đồng thời bằng một số hoạt động.

Output

• Bạn phải xuất \(𝑛\) dòng. dòng thứ \(i\) phải chứa một số nguyên duy nhất \(m_i\) - số lượng thao tác tối thiểu cần thiết để các bóng đèn từ 1 đến \(i\) được bật đồng thời.

Scoring

• Subtask 1 (40%) : \(1 \leq n,k \leq 20\)
• Subtask 2 (30%): \(c=2\)
• Subtask 3 (20%): \(1 \leq n,k \leq 5000\)
• Subtask 4 (10%): Giới hạn gốc

Example

Sample input 1

7 3
0011100
3
1 4 6
3
3 4 7
2
2 3

Sample output 1

1
2
3
3
3
3
3

Sample input 2

8 6
00110011
3
1 3 8
5
1 2 5 6 7
2
6 8
2
3 5
2
4 7
1
2

Sample output 2

1
1
1
1
1
1
4
4

Sample input 3

5 3
00011
3
1 2 3
1
4
3
3 4 5

Sample output 3

1
1
1
1
1

Sample input 4

19 5
1001001001100000110
2
2 3
2
5 6
2
8 9
5
12 13 14 15 16
1
19

Sample output 4

0
1
1
1
2
2
2
3
3
3
3
4
4
4
4
4
4
4
5

Nguồn: Bài 3 ngày 1 đề chọn ĐT HSG QG TP.ĐN 2022-2023

Hệ thống mạng trên hành tinh XYZ gồm \(n\) nút mạng và \(m\) dây cáp, mỗi dây cáp nối hai nút mạng và cho phép truyền tin theo cả hai chiều. Không có hai dây cáp nào nối cùng một cặp nút, và không có dây cáp nào nối một nút với chính nó. Hệ thống đảm bảo việc truyền tin giữa hai nút bất kỳ (trực tiếp hoặc qua một số nút trung gian), đây gọi là tính liên thông của mạng. Tuy nhiên nếu một dây cáp bị hỏng, mạng có thể không còn tính liên thông nữa. Để khắc phục điều này, ban quản lý sẽ thêm vào một số dây cáp, sao cho sau khi thêm thì việc một dây cáp bất kỳ bị hỏng cũng không làm mất tính liên thông của mạng, đồng thời số dây cáp cần thêm vào là nhỏ nhất có thể. Hãy giúp ban quản lý tính số dây cáp ít nhất cần thêm để mạng đảm bảo được tính liên thông ngay cả khi có một dây cáp bất kỳ bị hỏng.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, m\)
• \(m\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(u_i, v_i\) cho biết có một dây cáp nối giữa \(u_i\) và \(v_i\)

Output

• Ghi một số nguyên duy nhất là số dây cáp cần thêm.

Scoring

• Có 32% test với \(m=n-1\)
• Có 32% test với \(n,m≤1000\)
• Có 36% test với \(n,m≤10^5\)

Example

Sample input

6 7
1 2
2 3
3 1
4 5
5 6
6 4
1 4

Sample output

1

Sample input

3 3
1 2
2 3
3 1

Sample output

0

Nguồn: Bài 1 ngày 2 đề chọn ĐT HSG QG TP.ĐN 2022-2023

Trọng số của một số tự nhiên \(x\) được tính bằng cách biểu diễn \(x\) dưới dạng hệ cơ số 10 và tính tổng tất cả các số sinh ra từ các đoạn con của \(x\). Ví dụ trọng số của \(10034\) là \(1+10+100+1003+10034+0+00+003+0034+0+03+034+3+34+4=11263\). Hoài đang nghiên cứu các tính chất đặc biệt của số. Cô liệt kê tất cả các số nguyên dương có \(n\) chữ số, các chữ số đều bé hơn hoặc bằng 7 và không có số 0 đứng đầu. Cô muốn biết trong các số vừa liệt kê, có bao nhiêu bộ ba số (\(x,y,z\)) thoả mãn \(x<y<z\) và tổng trọng số của \(x,y,z\) chia hết cho \(k\).

Input

• Gồm hai số nguyên dương \(n, k\)

Output

• Ghi một số nguyên duy nhất là số bộ ba tìm được, chỉ cần in ra kết quả sau khi chia lấy dư cho \(10^9+7.\).

Scoring

• Có 8% test với \(n≤6;k≤10\)
• Có 20% test với \(n≤9;k≤100\)
• Có 28% test với \(n≤100;k≤100\)
• Có 44% test với \(n≤1000;k≤1000\)

Example

Sample input

1 10

Sample output

4

2 100

Sample output

273

Nguồn: Bài 2 ngày 2 đề chọn ĐT HSG QG TP.ĐN 2022-2023

Cho một tập các hình chữ nhật và một điểm \(A\). Cần kẻ một số đường thẳng qua \(A\) sao cho mỗi hình chữ nhật đều có điểm chung với ít nhất một đường thẳng đã kẻ, và số đường thẳng cần kẻ là ít nhất có thể. Lưu ý là đường thẳng được phép kéo dài tới vô tận theo cả hai hướng.

Input

• Dòng đầu tiên chứa ba số nguyên \(n, x, y\) với \(n\) là số lượng hình chữ nhật và (\(x,y\)) là toạ độ điểm \(A\)
• Dòng thứ \(i\) trong số \(n\) dòng tiếp theo chứa \(l_i, d_i, r_i, u_i\) mô tả hình chữ nhật thứ \(i\), với toạ độ của góc trái dưới là (\(l_i,d_i\)) và góc phải trên là (\(r_i,u_i\)). (\(l_i<r_i; d_i<u_i\))

Output

• Ghi số đường thẳng cần kẻ.

Scoring

• Trong tất cả các test: \(n≤10^5;0≤x,y,l_i,d_i,r_i,u_i≤10^9\);
• Có 16% test với \(n≤20\)
• Có 20% test với \(n≤1000\) và \(y=10^9; d_i=0,u_i=1\) với mọi \(i\)
• Có 28% test với \(y=10^9; d_i=0,u_i=1\) với mọi \(i\)
• Có 36% test với ràng buộc gốc

Example

Sample input

3 4 4
2 1 5 2
5 3 8 4
1 6 3 9

Sample output

2

Nguồn: Bài 3 ngày 2 đề chọn ĐT HSG QG TP.ĐN 2022-2023