AtCoder Grand Contest 019 B - Reverse and Compare【思维】

AtCoder Grand Contest 019 B - Reverse and Compare

题意：给定字符串，可以选定任意i、j且i<=j（当然i==j时没啥卵用），然后翻转i到j的字符串，问能组成多少种不同的字符串。

　　tourist出的题。。感觉好棒，虽然简单，但我就是不知道怎么弄，感觉思维好匮乏。

　　首先，如果Si=Sj，那么反转i到j和翻转i+1到j-1是一样的，也就是这种翻转不会贡献更多的答案。那么其实只要求i<j且Si！=Sj的个数就行了，当然，本身不变也是一种答案。求解i<j且Si！=Sj的个数可以从总的i<j的翻转个数中减去不合法的，也就是Si==Sj的。总的个数就是字符串长度len*(len-1)/2，因为可以这样想，s[0]能与后面len-1个字符组成字串翻转，s[1]能跟后面len-2个字符组成字符串翻转...，所以总结果就是len-1+len-2+len-3+...+1=len*(len-1)/2。然后统计每个字符出现的次数cnt(c)，每种字符组成的不合法种数是cnt(c)*(cnt(c)-1)/2，跟上面道理一样。所以答案就是：

　　　　　　　　　　1+len*(len-1)/2-∑cnt(c)*(cnt(c)-1)/2

　　看来数据类型尽量要统一，刚开始设len为int类型就WA了，全是long long就对了。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<map>

 using namespace std;

 typedef long long ll;

 map<int, ll> mp;

 char s[];

 int main()

 {

     cin >> s;

     ll len = strlen(s);

     for (int i = ; i < len; i++)

         mp[s[i] - 'a']++;

     ll ans = ;

     ans += len*(len - ) / ;

     for (int i = ; i < ; i++)

         if (mp[i]) ans -= mp[i] * (mp[i] - ) / ;

     cout << ans << endl;

     return ;

 }

巴特西

AtCoder Grand Contest 019 B - Reverse and Compare【思维】

最新文章

热门文章