ABC136D Gathering Children

URL: actoder

题面描述: 每个广场上有一个小朋友,如果地上是‘L’上面的小朋友向左走,否则向右走,进行$10^{100}$次这样的操作

思路: 看每个广场的小朋友会卡在哪里,就可以判断他最终的位置了

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
string s;
int ans[100000],ahl[100000];
bool hl[100000];
char last;
int zk(int x){
if(s[x]!=last) return x;
if(hl[x]) return ahl[x];
hl[x]=1;
if(s[x]=='R') {
last=s[x];
return ahl[x]=zk(x+1);
}
else {
last=s[x];
return ahl[x]=zk(x-1);
}
}
int main(){
memset(hl,0,sizeof(hl));
ios::sync_with_stdio(false);
cin>>s;
for(int i=0;i<s.size();i++){
last=s[i];
int x=zk(i);
hl[i]=1;
ahl[i]=x;
if((x-i)%2==0){
ans[x]++;
}
else if((x-i)%2==1&&last=='R') ans[x-1]++;
else ans[x+1]++;
}
for(int i=0;i<s.size();i++) cout<<ans[i]<<' ';
return 0;
}