Xâu nhị phân đối xứng
Đề bài
Mô tả
Một xâu được gọi là palindrome nếu đọc xuôi và đọc ngược đều giống nhau, tức là với mọi . Ví dụ, các xâu 010, 1001 và 0 là palindrome.
Bạn có xâu nhị phân (mỗi xâu chỉ gồm các ký tự 0 và 1). Bạn được phép thực hiện thao tác sau bao nhiêu lần tùy ý (có thể không lần nào): chọn hai ký tự bất kỳ rồi đổi chỗ chúng cho nhau. Hai ký tự này có thể nằm trong cùng một xâu hoặc ở hai xâu khác nhau. Lưu ý rằng độ dài của mỗi xâu không thay đổi.
Hãy tìm số lượng xâu lớn nhất có thể đồng thời là palindrome sau khi thực hiện các thao tác.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên là số bộ dữ liệu.
Mỗi bộ dữ liệu gồm:
- Dòng đầu tiên chứa số nguyên là số xâu.
- dòng tiếp theo, dòng thứ chứa xâu nhị phân .
Dữ liệu ra
In ra dòng, dòng thứ là số lượng xâu palindrome lớn nhất có thể đạt được đồng thời ở bộ dữ liệu thứ .
Ràng buộc
- Mỗi xâu chỉ gồm các ký tự 0 và 1.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 1 0 3 1110 100110 010101 2 11111 000001 2 001 11100111 |
1 2 2 2 |
Bộ 1: xâu 0 đã là palindrome. Bộ 2: không thể làm cả ba xâu thành palindrome, nhưng có thể làm hai xâu, ví dụ 0110, 111111 và 010000. Bộ 3: có thể đổi thành 11011 và 100001. Bộ 4: xâu thứ hai đã là palindrome, đổi chỗ ký tự thứ 2 và thứ 3 của xâu đầu được 010. |
| 1 3 1 1000 111110 |
3 | Có thể đổi thành 1, 1001 và 110011: cả ba xâu đều là palindrome. |
Bình luận