题解：P12592 重生有惊喜

daitangchen2008 · 2025-05-24 18:08:44 · 题解

思路

原字符串能被重排为一个回文串，当且仅当原串中只有零个或一个小写字母的数量是奇数。
依据这个思路记录每个小写字母出现个数后判断奇数个数即可。

注意多测清空，时间复杂度 O(n)。

代码

#include<bits/stdc++.h>
using namespace std;
int a[10005];
signed main()
{
    int T;
    cin>>T;
    while(T--)
    {
        string st;
        cin>>st;
        int n=st.size();
        st=' '+st;
        for(int i=1;i<=n;i++)
            a[(int)(st[i]-'a')]++;
        int flag=0; 
        for(int i=0;i<=25;i++)
            if(a[i]%2==1)
            flag++;     
        if(flag>1)
            cout<<"No\n";
        else
            cout<<"Yes\n";
        for(int i=0;i<=255;i++)
            a[i]=0;
    }
    return 0;
 }