题解 | I. 走地鸡地走

I. 走地鸡地走

模拟题，注意到 ，并且几个条件都只需要判断前几步

坑点在于，转向 的定义是不同时才视为转向，所以 UURRDDLLUU 其实也发生了连续四次转向都为顺时针的情况

可以在 的时间复杂度内完成，其中 是一个小常数

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define fType int
#define foreach(x, a, b) for (fType x = a, _end_ = b; x <= _end_; x++)
#define foreach_sub(x, a, b) for (fType x = a, _end_ = b; x >= _end_; x--)
#define tpl make_tuple

const string sw = "URDL";

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    int _;
    cin >> _;

    while (_--)
    {
        int n;
        string s;
        cin >> n >> s;

        auto get = [&](char x) -> int
        {
            foreach (w, 0, 3)
                if (sw[w] == x) return w;
            return -1;
        };

        // a -> b
        auto dif = [&](int a, int b) -> int { return (b - a) - (((b - a) >> 31) << 2); };

        bool valid = 1;
        foreach (i, 1, n - 1)
        {
            if (dif(get(s[i]), get(s[i - 1])) == 2)
            {
                valid = 0;
                break;
            }
        }

        if (!valid)
        {
            cout << "NO\n";
            continue;
        }

        foreach (i, 3, n - 1)
        {
            if (s[i] == s[i - 1] && s[i] == s[i - 2] && s[i] == s[i - 3])
            {
                valid = 0;
                break;
            }
        }

        if (!valid)
        {
            cout << "NO\n";
            continue;
        }

        string t;
        t.reserve(n);
        for (auto ch : s)
            if (t.empty() || t.back() != ch) t.push_back(ch);
        n = t.size();
        s = t;

        foreach (i, 4, n - 1)
        {
            auto [d1, d2, d3, d4] = tpl(dif(get(s[i - 4]), get(s[i - 3])), dif(get(s[i - 3]), get(s[i - 2])),
                                        dif(get(s[i - 2]), get(s[i - 1])), dif(get(s[i - 1]), get(s[i])));

            if (d1 == d2 && d1 == d3 && d1 == d4)
            {
                valid = 0;
                break;
            }
        }

        if (!valid)
        {
            cout << "NO\n";
            continue;
        }

        cout << "YES\n";
    }

    return 0;
}

扩展思考：如果将规定 改成 "不允许出现连续 次转向都是顺时针或逆时针"，"不允许出现连续 次行走都向同一个方向"，且 ，怎么做呢？