ABBADiv1

题意：

规定两种操作，一种是在字符串的末尾添加A，另一种是在末尾添加B然后反转字符串。现在给你一个起始串，一个终点串，然后问你是否能够通过以上两种操作，从起始串变为终点串。

题解：

将问题反过来考虑，那么问题就变为了是否能够从终点串变为起始串。令起始串为s，终点串为t。

首先考虑串t就是串s的子串，那么这个子串的前面的B的数量一定要和这个子串后面的B的数量相同，这是因为，只有相同的时候才能消掉。并且如果第一字符不是B，且匹配的位置不是在第一个，那么第一次的反转就无法成功，即s前面的那些A是消不掉的。

第二种情况就是t的反转时s的子串，做法和前面相似，只是判断条件变为了子串前面的B的数量要比后面的B的数量小1。

代码：

#include<iostream>

#include<cstring>

#include<vector>

#include<algorithm>

#include<string>

using namespace std;

class ABBADiv1 {

public:

    string canObtain(string initial, string target) {

        string s = initial, t = target;

        int pos = -;

        while (true) {

            pos = t.find(s, pos + );

            if (pos == t.npos)break;

            int B0 = , B1 = ;

            for (int i = ; i < pos; i++)if (t[i] == 'B')B0++;

            for (int i = pos + s.length(); i < t.length(); i++)if (t[i] == 'B')B1++;

            if (B0 == B1) {

                if (pos == )return "Possible";

                else if (t[] == 'B')return "Possible";

            }

        }

        reverse(s.begin(), s.end());

        pos = -;

        while (true) {

            pos = t.find(s, pos + );

            if (pos == t.npos)break;

            int B0 = , B1 = ;

            for (int i = ; i < pos; i++)if (t[i] == 'B')B0++;

            for (int i = pos + s.length(); i < t.length(); i++)if (t[i] == 'B')B1++;

            if (B0 == B1 +  && t[] == 'B')

                return "Possible";

        }

        return "Impossible";

    }

};

巴特西

Topcoder SRM 663 DIV 1

ABBADiv1

题意：

题解：

代码：

最新文章

热门文章