trang chủ / đề bài / icpc25_reg_f

Xâu cuối cùng tinh tế nhất

Đề bài

Mô tả

FWMC nhận được một xâu s độ dài n, chỉ gồm các ký tự A và B, làm quà sinh nhật. Danh tính của người cứ tặng xâu cho FWMC vào mỗi dịp sinh nhật vẫn còn là một bí ẩn...

FWMC bắt đầu nghịch xâu này. FWMC có thể thực hiện thao tác nén sau trên xâu bao nhiêu lần tùy ý:

  • Chọn một vị trí i sao cho 1≤i<n và si=si+1 (với n là độ dài xâu hiện tại). Xóa hai ký tự si và si+1, rồi chèn vào vị trí vừa xóa một ký tự loại còn lại (chèn B nếu si là A, và ngược lại).

FWMC cho rằng xâu có thứ tự từ điển càng nhỏ thì càng tinh tế. Xâu a nhỏ hơn xâu b theo thứ tự từ điển khi và chỉ khi một trong hai điều sau xảy ra:

  • a là tiền tố của b và a≠b;
  • tại vị trí đầu tiên mà a và b khác nhau, ký tự của a đứng trước ký tự của b trong bảng chữ cái.

Hãy giúp FWMC tìm xâu tinh tế nhất s′ có thể thu được từ xâu s, cùng với một dãy thao tác nén để thu được xâu đó.

Dữ liệu vào

Mỗi file dữ liệu gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa số bộ dữ liệu τ (1≤τ≤5000). Tiếp theo là mô tả các bộ dữ liệu:

  • Dòng đầu tiên chứa số nguyên n (1≤n≤5000): độ dài xâu s.
  • Dòng thứ hai chứa xâu s, chỉ gồm các ký tự A và B.

Dữ liệu đảm bảo tổng n qua tất cả các bộ dữ liệu không vượt quá 5000.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra:

  • Dòng thứ nhất chứa xâu s′: xâu tinh tế nhất có thể thu được từ xâu s.
  • Dòng thứ hai chứa số nguyên k (0≤k<n): số thao tác nén.
  • Dòng thứ ba chứa k số nguyên p1,p2,…,pk biểu diễn k thao tác. Giá trị pi nghĩa là thao tác thứ i xóa hai ký tự ở vị trí pi và pi+1, rồi chèn ký tự mới vào vị trí pi. Giá trị pi phải nhỏ hơn độ dài của xâu trước thao tác này. Nếu k=0, dòng này để trống.

Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ràng buộc

  • 1≤τ≤5000.
  • 1≤n≤5000, xâu s chỉ gồm các ký tự A và B.
  • Tổng n qua tất cả các bộ dữ liệu không vượt quá 5000.

Ví dụ

Input Output Giải thích
3
1
B
3
BAA
5
ABBBA
B
0

A
2
2 1
AA
3
3 3 2
Ở bộ dữ liệu thứ nhất, không thể thực hiện thao tác nào nên xâu tinh tế nhất là B. Ở bộ dữ liệu thứ hai, có thể thu được A (có thể chứng minh đây là xâu tinh tế nhất): BAA → BB → A. Ở bộ dữ liệu thứ ba, có thể thu được AA (có thể chứng minh đây là xâu tinh tế nhất): ABBBA → ABAA → ABB → AA.
3
4
AAAB
4
ABAB
6
BAABAB
AA
2
2 2
ABAB
0

AB
4
2 2 2 1
Ví dụ bổ sung (không có trong đề gốc). AAAB → ABB → AA. Xâu ABAB không có hai ký tự kề nhau giống nhau nên không thể nén. BAABAB → BBBAB → BAAB → BBB → AB.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0