题目简述
给定一个字符串 \(A\),可以选择区间 \([i,j]\) 翻转一次,求能得到多少本质不同的字符串。(\(A\) 的长度不超过 \(2 \times 10^5\))。
思路
首先解释本质不同的含义,即不完全相等的两个字符串(可能 \(A\) 是 \(B\) 的字串)。
如果想直接求得答案显然是不现实的(虽然可求)。那么可以想到正难则反,既然求本质不同的字符串难求,则可求总方案数和本质相同的方案数并相减即可。
可以发现,如 \(str_{i - 1} = str_{j + 1}\),则区间 \([str_i,str_j]\) 与区间 \([str_{i - 1},str_{j + 1}]\) 的字串本质相同,故只能算一种方案。
总方案数为 \(\frac{n \times (n - 1)}{2}\),其中 \(n\) 为字符串 \(A\) 的长度,其次本质相同的方案数即为每种字母中选两个的方案数总和,具体体现为 \(\sum {\frac{a_i \times (a_i - 1)}{2}}\)。
下面是代码实现:
#include<iostream>
#include<cstring>
using namespace std;
long long num[30]; // 记得开 long long!
string str;
int main() {
cin >> str;
long long n = str.size();
for(int i = 0; i < n; i ++) num[int(str[i] - 'a')] ++; // 预处理字母个数。
long long ans = n * (n - 1) / 2; // 总方案数。
for(int i = 0; i < 26; i ++) ans -= num[i] * (num[i] - 1) / 2; // 减去本质相同的方案数。
cout << ans + 1 << endl; // 要加上本身!
return 0;
}
因为洛谷提交不了,所以放上官网的提交记录:
\[\texttt{The End!} \] 标签:方案,int,题解,agc019,long,num,本质,str From: https://www.cnblogs.com/So-noSlack/p/17736360.html