Rday9

Rday9

贪心

Gathering Children

Given is a string S consisting of L and R.

Let N be the length of S. There are N squares arranged from left to right, and the i-th character of S from the left is written on the i-th square from the left.

The character written on the leftmost square is always R, and the character written on the rightmost square is always L.

Initially, one child is standing on each square.

Each child will perform the move below 10^{100} times:

Move one square in the direction specified by the character written in the square on which the child is standing. L denotes left, and R denotes right.
Find the number of children standing on each square after the children performed the moves.

Constraints
S is a string of length between 2 and 10^5 (inclusive).
Each character of S is L or R.
The first and last characters of S are R and L, respectively.
Input
Input is given from Standard Input in the following format:

S
Output
Print the number of children standing on each square after the children performed the moves, in order from left to right.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Sample Input 1
RRLRL
Sample Output 1
0 1 2 1 1
After each child performed one move, the number of children standing on each square is 0, 2, 1, 1, 1 from left to right.
After each child performed two moves, the number of children standing on each square is 0, 1, 2, 1, 1 from left to right.
After each child performed 10^{100} moves, the number of children standing on each square is 0, 1, 2, 1, 1 from left to right.
Sample Input 2
RRLLLLRLRRLL
Sample Output 2
0 3 3 0 0 0 1 1 0 2 2 0
Sample Input 3
RRRLLRLLRRRLLLLL
Sample Output 3
0 0 3 2 0 2 1 0 0 0 4 4 0 0 0 0

题解:
题意就是给一个R开头L结尾只包括R和L的字符串,然后有字符串长的广场,每个广场一个小孩,每个小孩需要按照地标走(地标就是当前位置的字符,R向右,L向左),问你走10^100次后每个广场的孩子人数。
我觉得是一道思维题,模拟几遍后发现只有在RL的交界处才会有孩子,而当一个子集(例如RRRRLL)中如果R+L是偶数,那么就把和平分到最后一个R和第一个L。如果是奇数就需要找到是R最后大还是L最后大了。

1
2
3
4
5
6
R  R  L                R  R  R L  L                        R  R  R R  R  L L
    0:           1  1  1                1  1  1 1  1                        1  1  1 1  1  1 1
    1:           0  2  1                0  1  2 2  0                        0  1  1 1  2  2 0
    2:           0  1  2                0  0  3 2  0                        0  0  1 1  3  2 0
    3:           0  2  1                0  0  2 3  0                        0  0  0 1  3  3 0
    4:           0  1  2                0  0  3 2  0                        0  0  0 0  4  3 0

由此我们可以发现,当r > l && (r - l)%2 == 1 时,如果l%2 == 0,r比l大1;否则l比r大1。同理可推到l > r的情况。

code:

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxx = 1e5;
int ans[maxx];

int main()
{
string s;
cin >> s;
int len = s.size();
int l, r;
for(int i = 0; i < len; i ++)
{
l = 0, r = 0;
if(s[i] == 'R')
{
r ++;
int x, y;
for(int j = i + 1; j < len; j ++)
{
if(s[j] == 'R')
r ++;
else
{
x = j;
break;
}
}
for(int j = x; j < len; j ++)
{
if(s[j] == 'L')
l ++;
if(s[j] == 'R' || j == len - 1)
{
ans[x] = ans[x - 1] = (l + r) / 2;
if(r > l && (r - l) % 2 == 1)
{
if(l % 2 == 1)
ans[x] ++;
else
ans[x - 1] ++;
}
else if(l > r && (l - r) % 2 == 1)
{
if(r % 2 == 1)
ans[x - 1] ++;
else
ans[x] ++;
}
y = j;
break;
}
}
i = y - 1;
if(y == len - 1)
i ++;
}
}
for(int i = 0; i < len; i ++)
{
cout << ans[i];
if(i < len - 1) cout << ' ';
else cout << '\n';
}
return 0;
}

---------------- The End ----------------
0%