Bedao Mini Contest 24
Points: 100
Một xâu được gọi là xâu đối xứng nếu như xâu đó được viết từ phải sang trái thì xâu đó không thay đổi.
Cho một xâu ~S~. Hãy tìm độ dài của xâu con dài nhất mà xâu đó không phải là xâu đối xứng.
Input
Dòng đầu gồm số nguyên dương ~N~ — độ dài xâu ~S~ (~1 \le N \le 5 \cdot 10^{4}~).
Dòng thứ hai gồm xâu ~S~ có độ dài ~N~ gồm toàn chữ cái tiếng Anh in thường.
Output
- Một dòng duy nhất gồm độ dài xâu con thỏa mãn đề bài.
Scoring
Subtask | Điểm | Giới hạn |
---|---|---|
~1~ | ~20~ | ~N \le 20~ |
~2~ | ~80~ | ~N \le 5 \cdot 10^{4}~ |
Sample Input 1
3
aba
Sample Output 1
2
Sample Input 2
3
aab
Sample Output 2
3
Points: 100
Robot của ~A~ đang đứng tại ô (~x_s, y_s~) trong một bảng hai chiều rộng vô hạn và bạn được ~A~ cho một dãy chỉ dẫn ~S~ gồm ~n~ lệnh L, R, U, D, I để di chuyển robot đến đích (~x_e, y_e~). Ý nghĩa của các lệnh này như sau:
L: Robot từ ô (~x, y~) di chuyển sang ô (~x - 1, y~);
R: Robot từ ô (~x, y~) di chuyển sang ô (~x + 1, y~);
U: Robot từ ô (~x, y~) di chuyển sang ô (~x, y - 1~);
D: Robot từ ô (~x, y~) di chuyển sang ô (~x, y + 1~);
I: Robot đứng yên tại ô (~x, y~).
Tuy nhiên, dãy chỉ dẫn này có một vài sai số, dẫn đến việc robot có thể không tới được đích. Vì vậy, ~A~ cho bạn được quyền thay đổi một đoạn tối đa ~k~ kí tự liên tiếp để đưa robot đi đến ô đích theo đúng kế hoạch. Nói cách khác, bạn được chọn một đoạn (~l, r~) với ~1 \le l \le r \le n, r - l + 1 \le k~ và gán lại một lệnh bất kỳ cho các chỉ dẫn ~S_l, S_{l + 1}, \dots, S_r~.
Yêu cầu: Hãy cho biết bạn có thể đưa robot đến đích sau khi thực hiện thay đổi trên hay không.
Input
Dòng đầu tiên gồm một số nguyên dương ~t~ (~1 \le t \le 10^4~) là số bộ test. Tiếp theo là ~t~ bộ test có cấu trúc như sau:
Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~k~ (~1 \le k \le n \le 10^5~).
Dòng thứ hai gồm bốn số nguyên ~x_s, y_s, x_e, y_e~ (~-10^9 \le x_s, y_s, x_e, y_e \le 10^9~).
Dòng thứ ba là dãy ~S~ gồm ~n~ ký tự L, R, U, D, I — tương ứng với việc đi sang trái, sang phải, lên trên, xuống dưới hoặc đứng yên.
Đầu vào đảm bảo ~\Sigma n \le 10^5~.
Output
- Với mỗi bộ test, in ra "YES" nếu có thể đưa robot đến đích sau khi thay đổi chỉ dẫn, ngược lại in ra "NO".
Scoring
Subtask | Điểm | Giới hạn |
---|---|---|
1 | ~20\%~ | ~k = 1~ |
2 | ~20\%~ | ~\Sigma n \le 10^3~ |
3 | ~60\%~ | Không có ràng buộc gì thêm |
Sample Input 1
1
3 1
1 1 2 2
RDL
Sample Output 1
YES
Sample Input 2
1
5 2
0 0 5 0
LLLLL
Sample Output 2
NO
Notes
Ở ví dụ đầu tiên, ta thay đổi ~S_3~ thành "I". Với dãy chỉ dẫn "RDI", robot sẽ đi từ (~1, 1~) đến (~2, 2~).
Ở ví dụ thứ hai, ta không có cách nào để đưa robot từ (~0, 0~) đến (~5, 0~) mà chỉ thay đổi tối đa ~2~ chỉ dẫn.
Points: 100
Có một hàng đợi ban đầu trống. Bạn cần xử lý ~q~ truy vấn có dạng sau:
Thêm 1 phần tử ~x~ vào cuối hàng
Tăng giá trị các phần tử hiện tại trong hàng lên ~v~
Xóa các phần tử có giá trị là ~x~ tại thời điểm hiện tại
Input
Dòng đầu tiên gồm số nguyên dương ~q~ là số truy vấn (~1 \le q \le 10^5~).
~q~ dòng tiếp theo mỗi dòng là một truy vấn có dạng như sau:
~1~ ~x~: Thêm 1 phần tử ~x~ vào cuối hàng (~1 \le x \le 10^5~).
~2~ ~v~: Tăng giá trị các phần tử hiện tại trong hàng lên ~v~ (~1 \le v \le 10^5~).
~3~ ~x~: Xóa các phần tử có giá trị là ~x~ tại thời điểm hiện tại (~1 \le x \le 10^5~).
Output
Dòng đầu tiên in ra số lượng phần tử còn lại trong hàng sau ~q~ truy vấn.
Dòng thứ hai in ra các phần tử ở trong hàng theo thứ tự từ đầu đến cuối.
Scoring
Subtask | Điểm | Giới hạn |
---|---|---|
1 | ~30~ | ~1 \le q \le 1000~ |
2 | ~30~ | Không có truy vấn loại ~3~ |
3 | ~40~ | Không có ràng buộc gì thêm |
Sample Input 1
9
1 1
1 2
1 3
3 3
2 1
1 3
3 3
2 5
1 6
Sample Output 1
2
7 6
Notes
Ở test ví dụ trên:
Sau truy vấn thứ nhất, dãy ~a = \{1\}~
Sau truy vấn thứ hai, dãy ~a = \{1,2\}~
Sau truy vấn thứ ba, dãy ~a = \{1,2,3\}~
Sau truy vấn thứ tư, dãy ~a = \{1,2\}~
Sau truy vấn thứ năm, dãy ~a = \{2,3\}~
Sau truy vấn thứ sáu, dãy ~a = \{2,3,3\}~
Sau truy vấn thứ bảy, dãy ~a = \{2\}~
Sau truy vấn thứ tám, dãy ~a = \{7\}~
Sau truy vấn cuối cùng, dãy ~a = \{7,6\}~
Points: 100
Cho một đàn bò đánh số theo thứ tự từ ~1~ đến ~n~. Hàng ngày, sẽ có ~k~ sự kiện diễn ra theo thứ tự, sự kiện thứ ~i~ sẽ đảo ngược vị trí các con bò trong đoạn ~[l_i, r_i]~.
Biết rằng ~k~ sự kiện đó hàng ngày đều được diễn ra như nhau. Hãy xác định vị trí từng con bò sau ~d~ ngày.
Input
Dòng đầu gồm ba số nguyên dương ~n~, ~k~ và ~d~ (~1 \leq n \leq 10^5, 1 \leq k \leq 100, 1 \leq d \leq 2 \cdot 10^9~).
~k~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương ~l_i~, ~r_i~ tương ứng với việc đảo ngược vị trí các con bò trong đoạn ~l_i, r_i~ ~(1 \le l_i \le r_i \le n)~.
Output
- Gồm một dòng gồm ~n~ số nguyên dương, số thứ ~i~ ghi ra số thứ tự của con bò tại vị trí ~i~.
Scoring
Subtask | Điểm | Giới hạn |
---|---|---|
1 | ~10\%~ | ~k \cdot d \le 100~ |
2 | ~20\%~ | ~d \le 100~ |
3 | ~70\%~ | Không có ràng buộc gì thêm. |
Sample Input 1
4 4 2
2 3
1 4
3 4
1 2
Sample Output 1
4 3 2 1
Sample Input 2
4 3 10062006
2 3
1 4
3 4
Sample Output 2
1 2 3 4
Notes
Ở test ví dụ thứ nhất:
Ngày đầu tiên:
Sau sự kiện ~1~, vị trí của các con bò là: ~1~ ~3~ ~2~ ~4~
Sau sự kiện ~2~: ~4~ ~2~ ~3~ ~1~
Sau sự kiện ~3~: ~4~ ~2~ ~1~ ~3~
Sau sự kiện ~4~: ~2~ ~4~ ~1~ ~3~
Ngày thứ hai:
Sau sự kiện ~1~: ~2~ ~1~ ~4~ ~3~
Sau sự kiện ~2~: ~3~ ~4~ ~1~ ~2~
Sau sự kiện ~3~: ~3~ ~4~ ~2~ ~1~
Sau sự kiện ~4~: ~4~ ~3~ ~2~ ~1~
Points: 100
Cho một xâu ~S~ độ dài ~N~ chỉ gồm các ký từ '(' và ')'.
Bạn được cho ~Q~ truy vấn, truy vấn thứ ~i~ thuộc một trong hai dạng sau:
~1~ ~x~: Nếu ~S_x~ là '(' thì ~S_x~ sẽ trở thành ')'. Nếu ~S_x~ là ')' thì ~S_x~ sẽ trở thành '('.
~2~ ~x~: Tìm độ dài dãy ngoặc đúng dài nhất bắt đầu tại vị trí ~x~.
Ta định nghĩa một dãy ngoặc đúng như sau:
Nếu ~A~ rỗng thì ~A~ là một dãy ngoặc đúng
Nếu ~A~ là một dãy ngoặc đúng thì ~(A)~ cũng là một dãy ngoặc đúng
Nếu ~A~, ~B~ là dãy ngoặc đúng thì ~AB~ cũng là một dãy ngoặc đúng
Một vài ví dụ cho dãy ngoặc đúng: "(())()", "((()))", "()()()".
Input
Dòng thứ nhất chứa hai số nguyên dương ~N~ và ~Q~ ~(1 \le N, Q \le 5 \cdot 10^5)~.
Dòng thứ hai chứa xâu ~S~.
~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~t~ và ~x~ ~(t \in {1, 2}, 1 \le x \le N)~.
Output
Với mỗi truy vấn ~t = 2~, in ra độ dài dãy ngoặc đúng dài nhất bắt đầu tại vị trí ~x~ trên một dòng.
Scoring
Subtask | Điểm | Giới hạn |
---|---|---|
1 | ~20\%~ | ~n, q \le 1000~. |
2 | ~30\%~ | ~n, q \le 10^5~ |
3 | ~50\%~ | Không có ràng buộc gì thêm. |
Sample Input 1
3 4
(()
2 1
2 2
1 2
2 1
Sample Output 1
0
2
2
Sample Input 2
8 6
)((())()
2 3
1 7
2 2
2 1
1 1
2 1
Sample Output 2
6
6
0
8
Notes
Trong test ví dụ đầu tiên:
Ở truy vấn thứ ~1~, dãy ngoặc đúng bắt đầu tại vị trí ~x = 1~ là ~\varnothing~.
Ở truy vấn thứ ~2~, dãy ngoặc đúng bắt đầu tại vị trí ~x = 2~ là "()".
Ở truy vấn thứ ~3~, ~S~ đổi thành "())".
Ở truy vấn thứ ~4~, dãy ngoặc đúng bắt đầu tại vị trí ~x = 1~ là "()".