战绩
结果 AC:3, WA:0,N:3
状态：不错
题目列表
比R1难不少，前三题洛谷评级是：黄，橙，绿
T1
模拟没啥好说的...看看题，注意细节
T2
排序+二分，非常好想
T3
这才是重点
题面
CF600C Make Palindrome
题目描述
如果一个字符串从左到右和从右到左读都是一样的，我们称之为回文串。例如 "kazak"、"oo"、"r" 和 "mikhailrubinchikkihcniburliahkim" 都是回文串，而 "abb" 和 "ij" 不是。
给你一个由小写拉丁字母组成的字符串 \(s\)。每次你可以选择字符串中的任意一个位置，将该位置的字母改成任意其他小写字母。因此，每次更改后字符串的长度不会改变。最开始你可以对 \(s\) 进行若干次这样的修改。然后，你可以对字符串中的字母进行任意排序（即任意打乱顺序），排列的过程不计为更改。
你需要通过最少的字母更改操作，将原字符串变为一个回文串。如果有多种方法能做到操作次数最少，你还需要输出字典序（按字母顺序）最小的那个回文串。换句话说，首先要最小化修改次数，然后最小化最终的回文串的字典序。
输入格式
输入仅一行，包含字符串 \(s\)（\(1 \leq |s| \leq 2 \cdot 10^{5}\)），字符串只包含小写拉丁字母。
输出格式
输出一个经过最少修改且字典序最小的回文串。
输入输出样例 #1
输入 #1
aabc输出 #1
abba输入输出样例 #2
输入 #2
aabcd输出 #2
abcba说明/提示
由 ChatGPT 5 翻译
其实我一下就想到了思路...但是一开始还是有一些漏洞
可以搞一个\(map\)它能让字典序从小到大排序, 存每一个字母有多少个,
有两种情况
- 如果是偶数，放两边就行，不影响回文
- 如果是奇数，覆盖另一个奇数的位置，这样两个都变偶数
看代码
#include <bits/stdc++.h>using namespace std;map<char, int> mp; // 存储每个字母的数量，其实也可以直接用数组，优化不大signed main() {string s;cin >> s;int n = s.size();s = '!' + s; // 和上面一行位置千万不要写反for (int i = 1; i <= n; i++) {mp[s[i]]++;}vector<char> odd; // 找到里面出现奇数次的字母for (auto& i : mp) { // 找呗if (i.second & 1) odd.push_back(i.first);}int l = 0, r = odd.size() - 1;while (l < r) {mp[odd[l]]++;mp[odd[r]]--;l++, r--;}/*我们希望字典序小的在外围就是在保证操作次数最优的前提下，让字典序小的多一点*/string s1 = "", s2 = ""; // 用于拼接，分两段更方便记录char mid = 0; // 如果有奇数个字符，中间的那个for (auto& i : mp) {if (i.second & 1) {mid = i.first; // 拿到这个唯一是奇数的，最后要放在中间的东西i.second--; // 去掉中心的一个}int half = i.second / 2; // 均分，一个变量存一半s1 += string(half, i.first); // 填充half个i.second到s1s2 += string(half, i.first); // 同理}//输出cout << s1;if (mid) cout << mid;reverse(s2.begin(), s2.end());cout << s2 << endl;return 0;
}
小技巧
回文数可以分两个字符串存，输出时拼上就行，奇数长度时不要忘了中间那个数！
如果对你有帮助，点个赞再走吧！