trang chủ / đề bài / binpalin

Xâu nhị phân đối xứng

Đề bài

Mô tả

Một xâu t được gọi là palindrome nếu đọc xuôi và đọc ngược đều giống nhau, tức là ti=t|t|+1−i với mọi 1≤i≤|t|. Ví dụ, các xâu 010, 1001 và 0 là palindrome.

Bạn có n xâu nhị phân s1,s2,…,sn (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 Q là số bộ dữ liệu.

Mỗi bộ dữ liệu gồm:

  • Dòng đầu tiên chứa số nguyên n là số xâu.
  • n dòng tiếp theo, dòng thứ i chứa xâu nhị phân si.

Dữ liệu ra

In ra Q dòng, dòng thứ i là số lượng xâu palindrome lớn nhất có thể đạt được đồng thời ở bộ dữ liệu thứ i.

Ràng buộc

  • 1≤Q≤50
  • 1≤n≤50
  • 1≤|si|≤50
  • Mỗi xâu si 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

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