题目
样例输入
5
AABBB
样例输出
6
思路
刚拿到这个题目的感觉就是懵,非常懵...题目很简单,但是怎么做呢...
我们来分析一下,什么样的字串是满足条件的呢?
在一个字串中:
①如果字母两边至少其中一个字母与之相同,即出现连续的两个及以上相同的字母,如AA,那么在这种序列中的字母都满足条件。
②如果字母两边的均与它本身不同,如对于字母A,BAB使其满足条件。
③特殊情况,字母在头或尾,如果它相邻的字母与它不同,但字串中存在相同字母,如ABBBBBA,也是满足条件的。
进一步分析:
①②包含了如果字母不是头或者尾的所有情况,即在字串中间的字母一定满足条件。
但是头或尾的字母,字串中必须有与其相同的字母才能满足条件。
即不满足条件的字串情况为:ABBB...B、BAAA...A、AAA...AB、BBB...BA。
如果从正面写,即计算可以达成条件的字串,需要对每个字串的每个字母进行判断,对于3e5的数据范围来讲,是会超时的。
但是如果从反面计算,减去不满足字串的情况,就会很快。
我使用了week11,计算寿司的方法,将序列分段,分段方法为相同的字母为一段。使用结构体str记录每一段的字母与num,以及记录段数。在相邻两段间,有两种不符合条件的字串,假如前一段是A,后一段是B,不符合条件的字串是AAA...AB、ABBB...B。
对字串AAAAAB,不符合的字串共有AB、AAB、AAAB、AAAAB、AAAAAB,数量即为段的长度。
注意,会将AB这种情况重复计算,所以应该加回1。
ps:因为数据范围是3e5,最大 ans 进行乘法计算,会超出 int 范围,ans应该是 long long 类型。
代码
#include<iostream>
using namespace std;
struct str
{
char word;
int num = 0;
}b[300010];
char c[300010];
int main()
{
int n;
cin >> n;
cin >> c;
long long ans = (long long)n * (n - 1) / 2;
int k = 0;
int now = c[0];
b[k].num++;
b[k].word = c[0];
for (int i = 1; i < n; i++)
{
if (c[i] == now)
b[k].num++;
else
{
now = c[i];
k++;
b[k].word = now;
b[k].num++;
}
}
k++;//k表示结构体的数目
for (int i = 0; i < k - 1; i++)
{
ans -= b[i].num;
ans -= b[i + 1].num;
ans++;
}
cout << ans;
//system("Pause");
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)