https://codeforces.com/contest/1251/problem/B
题目大意
给出 $n \ (\le 50)$ 个 $01$ 串，每个串 $s_i \ (|s_i| \le 50)$。可以任意交换任意两个串之间的一对字符，问最多能组成多少个回文串。
简要题解
我们最多可以得到 $n$ 个回文，我们尝试尽量达成这件事。
考虑所有串总长 $s = \sum s_i$ 的奇偶性，与 $01$ 个数的奇偶性。
当总长为偶数，我们只可能有偶数个奇数长串：
- 没有奇数长串，此时如果 $01$ 个数都是奇数，显然我们只能牺牲掉一个串去用这个 $01$ 对。
- 有偶数个奇数长的串，这样无论有没有 $01$ 为奇数（要么都是要么都不是），只要优先分配给奇数中心即可。
当总长为奇数时，一定有奇数个奇数长的串，同时一定有 $0$ 或 $1$ 的个数为奇数。我们只需优先将这个奇数个的数字放于某个奇数长串的中央，则可以构建 $n$ 个回文。
复杂度
$T$：$O(\sum s_i)$
$S$：$O(\sum s_i)$ 当然 $\max(s_i)$ 也是可以的
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n; cin >> n;
vector<string> s(n);
for (int i = 0; i < n; i++) {
cin >> s[i];
}
int evenlen = 0, cnt0 = 0, cnt1 = 0;
for (int i = 0; i < n; i++) {
if (!(s[i].length() & 1)) evenlen++;
for (char c : s[i]) {
if (c == '1') cnt1++;
else cnt0++;
}
}
if (evenlen == n && (cnt0 & 1)) {
cout << (n - 1) << '\n';
} else {
cout << n << '\n';
}
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] A. You Are Given Two Binary Strings... - Educational Codeforces Round 70 (Rated for Div. 2)