题解归档 - cf600C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf600C
• 本地来源：problems/cf600C/idea.md
• 题目链接：https://codeforces.com/contest/600/problem/C
• 原始标题：CF600C — Make Palindrome

思路

CF600C — Make Palindrome

题意

给定小写串 s，可任意改字母（每次改一个位置），改完后可任意重排。求最少改动次数下字典序最小的回文串。

做法

1. 统计 cnt[26]，收集奇数字母下标 od[]。
2. 最少改动：将 od 首尾配对，大下标 --、小下标 ++（等价于把大字母改成小字母），直到奇数个数为 n%2。
3. 若 od 仍剩一个，放中间；其余从 a 起每次取 cnt[i]>=2 填左右对称，得字典序最小回文。

验证

• 样例 aabc→abba，aabcd→abcba。
• WSL 对拍（n≤5，100 组）与手测边界 az→aa。
• 注：Kali 192.168.137.98 当前不可达，未走 stress.py。

结论

贪心配对 + 对称填字母，O(n)。

代码

来源：problems/cf600C/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:16:16
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
string s,ans;
ll cnt[30],od[30],n,i,j,k,l,r,zc;
int main(){
    cin>>s;
    n=(ll)s.size();
    for(i=0;i<n;i++) cnt[s[i]-'a']++;
    zc=0;
    for(i=0;i<26;i++)
        if(cnt[i]&1) od[zc++]=i;
    for(i=0,j=zc-1;i<j;i++,j--){
        cnt[od[i]]++;
        cnt[od[j]]--;
    }
    ans=string(n,' ');
    l=0;
    r=n-1;
    if(zc&1){
        ans[n/2]=char('a'+od[zc/2]);
        cnt[od[zc/2]]--;
    }
    for(i=0;i<26;i++){
        while(cnt[i]>=2){
            ans[l]=ans[r]=char('a'+i);
            l++;
            r--;
            cnt[i]-=2;
        }
    }
    cout<<ans<<endl;
    return 0;
}