Discription

给定一个长为 $n$ 的只有 $L$ 和 $R$ 的字符串 $S$ ，字符串每一个字符上都有一个点。现在开始 $10^{100}$ 轮移动，每一轮移动，每个字符上的点按照它当前字符上的字母来决定向左还是向右移动，如果为 $L$ 则向左移动一格， $R$ 则向右移动一格。保证字符串开头字符为 $R$ ，末尾字符为 $L$ 。输出经过 $10^{100}$ 轮移动后每个字符上点的个数。

Solution

模拟+找规律。
首先不要被 $10^{100}$ 吓到，观察样例和样例解释，发现经过这么多轮前结果其实早就决定了，而不是在最后一轮交换所决定的，这个巨大的数字言下之意就是这个字符串上的点都会聚在某一个位置。而 $10^{100}$ 是偶数，所以我们只要求出点都聚在一起后再经过第偶数轮的答案即可。
我们可以把字符串看成多个由 $L$ 和 $R$ 所组成的多个区间，每个区间互不干扰，且每个区间内左边都是 $R$ ，右边都是 $L$ 。区间内的点会在这个区间内 $R$ 和 $L$ 的交界处汇集。所以我们先求出每个区间内所有点聚在一起后点的数量的情况，把左边 $R$ 的个数记录在区间内最右边的 $R$ 上，右边 $L$ 的个数记录在区间内最左边的 $L$ 上。
之后便是找规律看多次移动后点的情况。可以用竖式在Excel里模拟下每轮情况。不难发现，当我们把区间内的点都聚集在区间内 $L$、$R$ 的交界处后，之后的移动就是这两个点上的数字互相交换。对于 $L$、$R$ 数量之和为偶数的情况，点的数量均匀分配，即为 $(L+R)/2$ ，记录在相应位置的结果数组上。对于不是偶数的情况，如果 $L$ 的个数为奇数，则 $L$ 的结果不变， $R$ 的结果为 $R$ 的数量加一，反之亦然。最后顺序输出（记得加空格）。
$\$
非最优解法。

Code

#include<bits/stdc++.h>
using namespace std;
string s;
int n,a[100001],res[100001];
bool ifcr=1,ifcl=0;
int cr,cl,nl;
int main()
{
	cin>>s;
	n=s.length();
	s+='O';
	//统计区间内L R个数
	for(int i=0;i<n+1;i++)
	{
		if(ifcr)
		{
			if(s[i]=='R')	cr++;
			else
			{
				a[i-1]=cr;
				cr=0;
				ifcr=0;ifcl=1;
				nl=i;
			}	
		}
		if(ifcl)
		{
			if(s[i]=='L')	cl++;
			else
			{
				a[nl]=cl;
				cl=0;
				ifcr=1;ifcl=0;
				cr++;
			}
		}
	}
    
	//计算交换情况
	for(int i=0;i<n;i++)
	{
		if(a[i]!=0)
		{
			if((a[i]+a[i+1])%2==0)
			{
				res[i]=(a[i]+a[i+1])/2;
				res[i+1]=res[i];
			}
			else
			{
				res[i]=floor((a[i]+a[i+1])/2);
				res[i+1]=res[i];
				if(a[i]%2==0)	res[i+1]++;
				else res[i]++;
			}
			i++;
		}
	}
	for(int i=0;i<n;i++)	cout<<res[i]<<" ";
	return 0;
}