CF550A 【Two Substrings】

思路:暴力判每一个”BA”出现的位置,二分查找他前/后有没有满足条件的”AB”,时间复杂度$O(n\log_{2}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
# include <bits/stdc++.h>

const int MaxN = 100010;

std::vector<int> a, b;//存下标

int upper(int x)//二分后面的位置
{
int l = 0, r = a.size();
while(l < r)
{
int mid = (l + r) >> 1;
if(a[mid] > x)
r = mid;
else l = mid + 1;
}
return l;
}

int lower(int x)//二分前面的位置
{
int l = -1, r = a.size() - 1;
while(l < r)
{
int mid = (l + r + 1) >> 1;
if(a[mid] < x)
l = mid;
else
r = mid - 1;
}
return l;
}
int main()
{
std::string s;
std::cin >> s;
int len = s.length();
for(int i = 0; i < len - 1; i++)
{
std::string tmp = s.substr(i, 2);
if(tmp == "AB")
a.push_back(i);
else if(tmp == "BA")
b.push_back(i);
}//查找"AB"和"BA"出现的位置
if(a.size() == 0 || b.size() == 0)
return 0 * printf("NO");//特判
for(int i = 0; i < b.size(); i++)
{
int x = lower(b[i] - 1);//防重
int y = upper(b[i] + 1);
if(x != -1 || y != a.size())
return 0 * printf("YES");
}
printf("NO");
return 0;
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×