题目描述

难度分:$1400$

输入$T(\leq 50)$表示$T$组数据。

每组数据输入$n(1 \leq n \leq 50)$和$n$个长度不超过$50$的01字符串。

你可以执行任意次交换操作，每次交换两个字符，它俩可以来自同一个字符串或者不同字符串。

输出最多可以有多少个回文串。

输入样例

4
1
0
3
1110
100110
010101
2
11111
000001
2
001
11100111

输出样例

1
2
2
2

算法

贪心

由于可以跨串交换字符，所以本质上就是给了一堆$0$和$1$的字符，让你分配出$n$个串，$n$个串的长度也给你。刚开始用动态规划来做，但是一直TLE。后来发现有性质：

1. 如果一个字符串的长度$len$为偶数，那就必须要有偶数个$1$，此时$0$也是奇数个，$0$和$1$都均匀分布在两侧；
2. 如果$len$为奇数，那有多少个$1$都行，有奇数个$1$，那$1$就充当回文串的中心，$0$均匀分布在两侧；否则$0$就是奇数个，$0$充当回文中心，$1$均匀分布在两侧。

因此，我们可以统计长度为奇数的串的个数$cnt$，以及所有串中$1$的个数。

1. 如果$1$有奇数个，由于偶数长度的串无法消耗奇数个$1$，所以至少要有一个长度为奇数的串消耗奇数个$1$，这样就还剩下偶数个$1$，剩下的串长度不管是奇数还是偶数都能消耗掉，能够形成$n$个回文串；如果一个长度为奇数的串都没有，那就肯定有一个串有奇数个$1$导致无法构成回文，一共有$n-1$个回文串。
2. 否则$1$有偶数个，无论是长度为奇数的串还是长度为偶数的串都能消耗掉，可以构成$n$个回文串。

复杂度分析

时间复杂度

整个算法过程就是遍历了所有的字符串，因此算法的时间复杂度为$O(n|s|)$，其中$|s|$是最大串长。

空间复杂度

除了输入的字符串，只用了几个有限的变量，所以额外空间复杂度为$O(1)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
int t, n;

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        string s;
        int cnt = 0, one = 0;
        for(int i = 0; i < n; i++) {
            cin >> s;
            int len = s.size();
            cnt += len&1;
            for(char c: s) {
                one += c == '1'? 1: 0;
            }
        }
        if(one&1) {
            if(cnt >= 1) {
                printf("%d\n", n);
            }else {
                printf("%d\n", n - 1);
            }
        }else {
            printf("%d\n", n);
        }
    }
    return 0;
}