[CF1476D] Journey

[CF1476D] Journey - dp

Description

有点 0...n，对于第 i 条边 (i-1,i) 告诉你该边的方向，每走一步所有边的方向都会反转，对于每个点请你求出从该点最多能走到多少个不同的点。

Solution

如果碰到两条相同的边，就会返回，所以我们预处理出每个点向右走和向左走分别能走多少步，然后枚举起始点即可

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

#define int long long

void solve()
{
    int n;
    cin >> n;

    string str;
    cin >> str;

    vector<int> fl(n), fr(n);
    fl[0] = 1;
    for (int i = 1; i < n; i++)
        fl[i] = fl[i - 1] * (str[i] != str[i - 1]) + 1;
    fr[n - 1] = 1;
    for (int i = n - 2; i >= 0; i--)
        fr[i] = fr[i + 1] * (str[i] != str[i + 1]) + 1;

    vector<int> ans(n + 1);
    for (int i = 0; i <= n; i++)
    {
        if (i == 0)
            ans[i] = (str[i] == 'R' ? fr[i] + 1 : 1);
        if (i == n)
            ans[i] = (str[i - 1] == 'L' ? fl[i - 1] + 1 : 1);
        if (0 < i && i < n)
            ans[i] = (str[i] == 'R' ? fr[i] + 1 : 1) + (str[i - 1] == 'L' ? fl[i - 1] + 1 : 1) - 1;
    }

    for (int i = 0; i <= n; i++)
        cout << ans[i] << " ";
    cout << endl;
}

signed main()
{
    ios::sync_with_stdio(false);

    int t;
    cin >> t;

    while (t--)
        solve();
}