首先时最简单的做法，两层循环逐一判断，时间复杂度为 $O(n^2)$。但是现在无法通过最后一个数据点，需要优化程序。
对于一个从 $i$ 开始的情况，首先用一次二分找到最远的点符合只出现 H 或 G 的情况，设为 $l$。然后再用一次二分找到最远的点符合该区间内只有一个 H 或一个 G 的情况，设为 $r$。那么由题目的意思可知，$[i,n]$ 的区间对答案的贡献为 $r - (l + 1) + 1 = r - l$。注意题目的限制，连续的区间，长度不小于 $3$，因此一些特殊的地方要进行特判。这样，时间复杂度就降到了 $O(n \log n)$，可以通过本题。
接下来给一下代码：（思路有点奇怪嘿嘿）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 5e5 + 5;
const int MOD = 1e9 + 7;
inline int read ();
int n,a[MAX],b[MAX];
ll ans;
char str[MAX];
int main ()
{
n = read ();
scanf ("%s",str + 1);
for (int i = 1;i <= n;++i)
{
if (str[i] == 'G') a[i] = a[i - 1] + 1,b[i] = b[i - 1];
else a[i] = a[i - 1],b[i] = b[i - 1] + 1;
}
for (int i = 1;i <= n;++i)
{
int l = i + 2,r = n,st,end;
if (l > r) break;
while (l <= r)
{
int mid = (l + r) >> 1;
if (a[mid] - a[i - 1] == mid - i + 1 || b[mid] - b[i - 1] == mid - i + 1) l = mid + 1;
else r = mid - 1;
}
--l;
if (l < i + 2) st = i + 2;
else st = l + 1;
l = st,r = n;
while (l <= r)
{
int mid = (l + r) >> 1;
if (a[mid] - a[i - 1] == 1 || b[mid] - b[i - 1] == 1) l = mid + 1;
else r = mid - 1;
}
--l;
end = l;
ans += end - st + 1;
}
printf ("%lld\n",ans);
return 0;
}
inline int read ()
{
int s = 0;int f = 1;
char ch = getchar ();
while ((ch < '0' || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
|
