题解 | #牛牛与回文串#

考察知识点：构造

由题易知，构造的回文串个数与字符串中出现次数为奇数的字符个数有关，所有成对出现的字符都不用单独构造。若所有字符都成对出现，则也至少需要构造 1 个回文串。

因此回文串的个数应为 max(n, 1)，其中 n 为出现次数为奇数的字符个数。

将单独出现的字符作为回文串的中心，其余字符成对出现在中心两侧即可。

时间复杂度：$O(\mathrm{\mid }s\mathrm{\mid })O(|s|)$

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

void solve()
{
    string s;
    cin >> s;
    map<char, int> mp;              // 记录每个字符出现的次数
    for (auto c : s)
        mp[c]++;
    int n = 0;
    vector<char> v;                 // 记录出现奇数次的字符
    for (auto p : mp)
    {
        if (p.second % 2)
        {
            n++;
            v.push_back(p.first);
        }
    }
    cout << max(n, 1) << endl;
    string cur;
    for (auto p : mp)
    {
        for (int i = 1; i <= p.second / 2; i++)
            cur += p.first;
    }
    cout << cur;
    if (v.size())
    {
        cout << v.back();
        v.pop_back();
    }
    reverse(cur.begin(), cur.end());
    cout << cur << endl;
    while (v.size())
    {
        cout << v.back() << endl;
        v.pop_back();
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}