P8892磁铁

cosf · 2022-12-11 11:35:41 · 题解

P8892 磁铁

先别想着做题！先别想着做题！先别想着做题！重要的事情说三遍！

我们先看看那两个操作都是有什么用的

举个栗子：有个字符串叫做：crazyouthcosf，那么我们可以把它想象成这个：

那么，第二个操作可能很多人都会想象成这个样子：

对吧。但是，这样处理很难理解。我们可以换一个思路：

这不就是一个环吗！也就是说，在这个环里面，磁铁的相对位置是不会变的。那么对于第一个操作，其实就是删除环中的任意连续的一段！那么其实就可以理解了。

我们可以先把题目中的 a 看作一个环，然后再在里面匹配一下，看看 b 是不是他的子序列，并且长度小于或等于 a，如果是，a 就可以变成 b，否则就不行。比如说，ytcoaz 是 crazyouthcosf 环中的一个子序列，而 crthou 不是。

毕竟 O(n^2) 是可以过的，所以朴素的算法是可以的 （其实是高级算法我不会）。

#include <iostream>
using namespace std;

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        string a, b;
        cin >> a >> b;
        int alen = a.length();
        int blen = b.length();
        a = a + a;
        b = " " + b;
        int ys = 0;
        for (int i = 0; i < alen; i++)
        {
            string c = a.substr(i, alen); // 枚举环中的每一条边，这样确保了枚出来的子串长度一定小于或等于 a 的长度。
            int cur = 0;
            for (int j = 0; j < alen; j++)
            {
                if (c[j] == b[cur + 1])
                {
                    cur++;
                }
                if (cur == blen)
                {
                    ys = 1;
                    break;
                }
            }
            if (ys)
            {
                break;
            }
        }
        if (ys)
        {
            cout << 'Y' << endl;
        }
        else
        {
            cout << 'N' << endl;
        }
    }
}