比赛链接

2025牛客寒假算法基础集训营4

D.Tokitsukaze and Concatenate‌ Palindrome

题目描述

Tokitsukaze 有一个长度为 的字符串 和一个长度为 的字符串 。两个字符串均仅包含小写字母。随后，依次进行以下操作：
第一步，Tokitsukaze 可以将 重新排列（也可以不进行重新排列），再将 重新排列（也可以不进行重新排列）。例如，假设 ，对 重新排列后， 可以是： 这 种字符串中的一种；
第二步，Tokitsukaze 可以进行若干次替换（可以为 次）：每次选一个字符串，再从中选一个位置，然后把该位置上的字母替换成任意小写字母；
第三步，将 与 拼接起来形成一个新的字符串 。拼接时须让 在 之前，也就是说 。
现在，Tokitsukaze 想知道，在第二步操作时，至少需要替换几次，才能使 为回文串。

一个字符串被称作回文串，当且仅当这个字符串从左往右读和从右往左读是相同的。例如， 均是回文串。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：
第一行输入两个整数 ，表示字符串 和 的长度。
第二行输入一个长度为 、仅包含小写字母的字符串 。
第三行输入一个长度为 、仅包含小写字母的字符串 。

除此之外，保证单个测试文件的 之和不超过 、 之和不超过 。

输出描述

对于每一组测试数据，新起一行。输出一个整数，代表至少需要替换几次，才能使 为回文串。

解题思路

为方便说明，我们定义 相同字母对，即两个相同的字母，如 {a,a}。

回文字符串是镜像对称的，故交换字符串 与字符串 的位置不会影响结果。

我们先将长的字符串作为 ，由于对字符串排序无代价，我们优先组合 与 相同的字母为相同字母对。 由于比 多个字母,多余的字母组成回文串的中间部分。

我们统计 中剩余字母可以组成几个相同字母对，并将其作为回文串的中间部分。如果这些相同字母对的数量足够多，可全部替换回文串的中间部分，则中间部分的回文串所需代价为0；否则，代价为：

中间部分需要的字符数/2-中相同字母对的组

答案即为 剩余的字母产生的代价+中间部分的代价。

完整代码

#include<bits/stdc++.h>
using namespace std;

int cnta[26], cntb[26], n, m, ans;
string a, b;

static void solve() {
	for (char c : a)cnta[c - 'a']++;
	for (char c : b)cntb[c - 'a']++;

	// step 1: 消除相同字符
	for (int i = 0; i < 26; i++) {
		if (cnta[i] > cntb[i]) {
			cnta[i] -= cntb[i];
			cntb[i] = 0;
		}
		else {
			cntb[i] -= cnta[i];
			cnta[i] = 0;
			ans += cntb[i];
		}
	}

	// step 2: 统计a剩余的相同字母对数
	int pairs = 0, mx = abs(n - m) / 2;
	for (int i = 0; i < 26; i++) {
		pairs += cnta[i] / 2;
		if (pairs >= mx) {
			pairs = mx;
			break;
		}
	}

	// step 3: 输出答案
	cout << ans + (mx - pairs) << endl;
}

signed main() {
	int T; cin >> T;
	while (T--) {
		// 还原默认值
		ans = 0;
		memset(cnta, 0, sizeof(cnta));
		memset(cntb, 0, sizeof(cntb));
		cin >> n >> m >> a >> b;
		// 确保a更长
		if (a.size() < b.size()) {
			swap(a, b);
			swap(n, m);
		}
		solve();
	}
	return 0;
}

如有错误欢迎指正~