首页 > 代码库 > UVALive6659 - Dromicpalin Substrings

UVALive6659 - Dromicpalin Substrings

题意

给一个字符串,找出其子串可化为回文串的个数,子串可以任意改变其顺序。

思路

遍历每一个子串,若子串长度为奇数且只有一个字母的个数为奇数 或 字串长度为偶数且所有字母个数为偶数,则此子串为所求串。

总结

刚开始漏看了题,导致题意读错。

挺简单一道题,比赛时不记得怎样遍历每个子串。

对自己有点信心。加油。

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 int T, kase = 0; 6 int num[30]; 7 int main() 8 { 9     //freopen("in.txt","r",stdin);10     cin >> T;11     while(T--) {12         string s;13         cin >> s;14         int len = s.size();15         int ans = 0;16         for(int i = 0; i < len; i++) {17             ans++;18             memset(num,0,sizeof num);19             num[s[i]-a]++;20             int odd = 1;21             for(int j = i + 1; j < len; j++) {22                 if((++num[s[j]-a]) % 2) odd++;23                 else odd--;24                 if((!odd && (j-i)%2) || (odd == 1&& (j-i)%2 == 0)) ans++;25             }26         }27         cout << "Case " << ++kase << ": " << ans << endl;28     }29     return 0;30 }

 

UVALive6659 - Dromicpalin Substrings