Đề thi chọn ĐT HSG QG Đà Nẵng 2022 - Ngày 1

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\).

Example

2
acbd
acbd
fosfos
fos

4 1
3 1

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(1 \leq |S|,|T| \leq 20\)
• Subtask \(2\) (\(30\%\) số điểm): \(1 \leq |S|,|T| \leq 200\)
• Subtask \(3\) (\(20\%\) số điểm): \(1 \leq |S|,|T| \leq 1000\)

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, \ldots, 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}, \ldots, p_r\).

nếu \(l \le 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 \le n, q \le 10^6\)) — kích thước của hoán vị \(p\) 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, \ldots, p_n\) (\(1 \le p_i \le n\), \(p_i \ne p_j\ \forall i \ne j\)) — hoán vị \(p\).
• Dòng thứ ba chứa \(q\) số nguyên \(l_1, l_2, \ldots, 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, \ldots, r_q\) — giá trị \(r\) của các truy vấn.
• Đầu vào đảm bảo rằng \(1 \le l_i \le r_i \le 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.

Example

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

1 6 8 5 1

Scoring

• Subtask \(1\) (\(40\%\)): \(1 \le n, q \le 500\)
• Subtask \(2\) (\(30\%\)): \(1 \le n, q \le 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

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\) đến \(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, \ldots, 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 \(n\) 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.

Example

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

1
2
3
3
3
3
3

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

1
1
1
1
1
1
4
4

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

1
1
1
1
1

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

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

Scoring

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

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