关于#回文构造机#的问题，如何解决？(语言-c++)

Question

时间：1s 空间：256M

题目描述：

XTX非常喜欢回文串，他认为回文会给自己带来好运,有一天他看到一个字符串突发奇想，如果将这个字符串所有字符打乱，然后每次操作只能挑选若干个能构成回文串的字符组合成一个字符串，XTX最少需要操作几次才能取完所有字符。

输入格式：

输入一个字符串S,1≤|s|≤1000

输出格式：

第一行输出一个整数K，表示回文串的个数

接下来K行每行输出一个回文串，要求输出的所有字符串的字符集合恰好是输入的S中的所有字符集合

样例输入1：

abbaa

样例输出1：

1
ababa

样例输入2：

abc

样例输出2：

3
a
b
c

样例输入3：

aaabbbccc

样例输出3：

3
aba
bcb
cac

样例输入4：

z

样例输出4：

1
z

子任务一30分：|s|<=10

子任务二30分：|s|<=100

子任务三40分：|s|<=1000

Answer 1

这个题目其实很简单，回文数左右两边的字符都是成对的，只有正中间的一个字符是单个的。所以偶数个的字符都可以在第一次输出，然后每行（包括第一行）输出一个单个的字符即可。
下面是c语言代码，没有简化，时间复杂度大约是O(N)。

#include<stdio.h>

int main() {
    char s[501];//两边相同的字符只保留一个
    int c, i, j, k, times;
    int count[128] = {0}; //不确定有没有大写字母和数字
    //统计字符数目
    while (c = getchar(), c != '\n') {
        count[c]++;
    }
    //求出第一行
    for (i = j = 0; i < 128; i++) {
        while (count[i] > 1) {
            s[j++] = i;
            count[i] -= 2;
        }
    }
    for (i = 0; count[i] == 0 && i < 128; i++);
    if (i < 128) {
        s[j++] = i;
        count[i]--;
    }
    //计算并输出回文串个数
    for (times = 1, k = i + 1; k < 128; k++) {
        if (count[k] > 0)times++;
    }
    printf("%d\n", times);
    //输出第一行
    for (k = 0; k < j; k++) {
        putchar(s[k]);
    }
    for (k = j - 2; k >= 0; k--) {
        putchar(s[k]);
    }
    putchar('\n');
    //输出 后续行
    for (k = i + 1; k < 128; k++) {
        if (count[k] > 0) {
            putchar(k);
            count[i]--;
            putchar('\n');
        }
    }
    return 0;
}

Answer 2

这个是简化后的，最后一行没有换行符，如果需要的话，可以再加一个。

#include<stdio.h>
//把字符c输出n次
void putchar_n(char c, int n) {
    while (n-- > 0)putchar(c);
}

int main() {
    int c, i, k, times = 0;
    int count[128] = {0}; //不确定有没有大写字母和数字
//统计字符数目
    while (c = getchar(), c != '\n') {
        count[c]++;
    }
//计算输出行数
    for (i = 0; i < 128; i++) {
        if (count[i] % 2 > 0) {
            times++;//每有一个成单的字符，都要多一行输出
        }
    }
    if (times == 0)times = 1; //如果所有字符都是成对的，则一行输出
    printf("%d\n", times);
//输出第一行
    //逆序输出成对的字符的一个
    for (i = 127; i >= 0; i--)putchar_n(i, count[i] / 2);
    //输出第一个成单的字符
    for (k = 0; k < 128 && count[k] % 2 == 0; k++);
    if (k < 128)putchar(k++);
    //正序输出成对的字符的另一个
    for (i = 0; i < 128; i++) putchar_n(i, count[i] / 2);
//输出后续行
    for (; k < 128; k++)
        if (count[k] % 2 > 0) {
            putchar('\n');
            putchar(k);
        }
    return 0;
}

Answer 3

明白了，实在感谢，这道题卡我好长时间了😭