Gathering Children 题解

· · 题解

给一个不需要脑子的做法。

设移动次数为 m=10^{100}。

直接模拟移动显然会超时，考虑通过倍增降低复杂度。

设 f_{i,j} 为在位置 i 移动 2^j 次后的位置，易知

f_{i,0}=\left\{ \begin{aligned} i-1&&s_i=\texttt L\\ i+1&&s_i=\texttt R\\ \end{aligned} \right. f_{i,j}=f_{f_{i,j-1},j-1}

只需将 m 转为二进制，若 2^n 对应的位上为 1 则进行一次 2^n 的移动即可。

代码：

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

#define N 100001
#define LOG 350

ll n;

string s;

ll f[N][LOG];

ll ans[N];

const string jmp="000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010001111000101110100000101010001000011000010010011010101010100111110010110001000010001110001000000100111001101010001110011111101000001110011001000110010000111100100110100001101011100111110110000110010100110100100101101011001001001001";

int main()
{
    ios::sync_with_stdio(false);
    cin>>s,n=s.size(),s=" "+s;
    for(int i=1;i<=n;i++)
        if(s[i]=='L')f[i][0]=i-1;
        else f[i][0]=i+1;
    for(int j=1;j<LOG;j++)
        for(int i=1;i<=n;i++)
            f[i][j]=f[f[i][j-1]][j-1];
    for(int i=1;i<=n;i++)
    {
        ll t=i;
        for(size_t j=0;j<jmp.size();j++)
            if(jmp[j]-'0')t=f[t][j];
        ans[t]++;
    }
    for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
}