CF-1251B Binary Palindromes 题解

题目大意

给你n个01串，你可以交换每个串中任意一个数字的位置，无论是不是同一个串，问能构成多少个回文串。

解题思路

吐了。。

刚刚看到这个题目的时候，数据这么小，我以为是一些时间复杂度比较大的算法。

自己直接去模拟去了。

结果不好模拟，没啥思路。。

卡了好久，去看了眼题解。

发现自己就根本没往这方面想。。

我们可以统计所有串中的0和1的数量。

可以分为三种情况。

1、0为偶，1为偶

显然，这些串是由l个偶长度串和m个奇长度串（m为偶数）构成的，不管m是否为0，都可以满足条件，所以n个串都可以是回文串。

2、0为奇，1为偶（0为偶，1为奇）

这些串是由l个偶长度串和m个奇长度串（m为奇数）构成的，可以把其中的奇数的插到一个奇长度串的中间，可以等价于第一种情况，所以n个串都可以是回文串。

3、0为奇，1为奇

这些串也是由l个偶长度串和m个奇长度串（m为偶数）构成的，但是如果m为0是不行的，会有一个串无法构成回文串，所以需要判断一下m是否小于2，因为m为2*k

完整代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

struct t{
	string s;
	int l;
}s[55];//之前写法留下来的，懒得改了，其实不需要这么麻烦的
int cnt[2];

int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		memset(cnt, 0, sizeof(cnt));
		for (int i = 1; i <= n; i++)	cin >> s[i].s, s[i].l = s[i].s.length();
		int c = 0;
		for (int i = 1; i <= n; i++) {
			if (s[i].l & 1)	c++;
			for (int j = 0; j < s[i].l; j++) {
				if (s[i].s[j] == '1')	cnt[1]++;
				else cnt[0]++;
			}
		}
		if ((cnt[1] & 1) && (cnt[0] & 1) && c < 2)	n--;
		cout << n << endl;
	}
}