题解 AT1877 【回文分割】

记录字符串中每个字符出现的次数$s_i$ 如果$s_i$为偶数，那么这些字符i就可以和别的回文串拼在一起变成更长的回文串 如果$s_i$为奇数，那就必须从i中拿一个出来作为某个回文串的中间字符 比如$S=aabbb$ 一个b要在中间 而剩下的可以和这个b合在一起 变成 $abbba$或者$babab$ 容易发现，$s_i$中有多少个为奇数，最少就可以分成几个串 知道最少可以分成几个串以后枚举长度即可 $update :$不用枚举长度，答案即为【比$len/num$大的最小奇数$-2$】除一下即可 $Code:$ ```cpp include<cstdio> #include<cstring> char str[100010]; int ed[30], num; int main() { scanf("%s", str); for(int i = strlen(str)-1; i >= 0; i--) ++ed[str[i]-'a']; for(int i = 0; i < 26; i++) num += ed[i]&1; if(!num) printf("%d\n", strlen(str)); else printf("%d\n", ((strlen(str)/num+1)|1)-2); return 0; } ```