题解 CF550A 【Two Substrings】

为什么我的做法跟别人如此不一样啊qwq

思路：暴力判每一个"BA"出现的位置，二分查找他前/后有没有满足条件的"AB",时间复杂度\(O(n\log_{2}n)\)

# 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;

}

巴特西

题解 CF550A 【Two Substrings】

为什么我的做法跟别人如此不一样啊qwq

最新文章

热门文章