萌新刚学C++，解决↑问题时用的是100分方法，但...

主要思路就是维护每个字符串的前缀和，先算出每个字符串中会加进去的所有字符串的相邻字符相等的对数。

然后算出字符串之间连接处的最大对数（详细见代码）。

大佬萌求调~

WA Code

太弱啦，代码中可能有很多没有用的地方qwq。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
int n, s[2][2];
ll sum[N];
ll calc(bool last, bool S) {
	int cnt[2][2] = {s[0][0], s[0][1], s[1][0], s[1][1]};
	--cnt[S][last];
	ll res = 0;
	while (cnt[0][0] + cnt[0][1] + cnt[1][0] + cnt[1][1] > 0) {
		bool is_changed = false;
		if (cnt[last][0] + cnt[last][1] == 0) {
			last ^= 1;
			is_changed = true;
		}
		if (cnt[last][0] && cnt[last][1]) {
			int i = (cnt[0][0] > 0) + (cnt[0][1] > 0) < (cnt[1][0] > 0) + (cnt[1][1] > 0);
			res += !is_changed;
			--cnt[last][i];
			last = i;
			continue;
		}
		for (int i = 0; i < 2; ++i) {
			if (cnt[last][i]) {
				res += !is_changed;
				--cnt[last][i];
				last = i;
				break;
			}
		}
	}
	return res;
}
int main() {
	ios :: sync_with_stdio(0);
	cin >> n;
	ll res = 0;
	for (int i = 1; i <= n; ++i) {
		string t;
		cin >> t;
		t = " " + t;
		int m = t.size() - 1;
		for (int j = 2; j <= m; ++j) {
			sum[j] = sum[j - 1] + (t[j - 1] == t[j]);
		}
		for (int j = 2; j <= m; ++j) {
			res += sum[m] - sum[j];
			++s[t[j] ^ '0'][t[m] ^ '0'];
		}
	}
	cout << res + max(calc(0, 0), max(calc(0, 1), max(calc(1, 0), calc(1, 1)))) << '\n';
	return 0;
}

QWQ感谢万分~