CF298A Snow Footprints
rjdjx
1.背景
我在和同学打1300
2.题目
有一条笔直的雪路，分为 n 个区块。这些区块从左到右编号，从 1 到 n。如果一个人从 i 号区块移动到 (i + 1) 号区块，他将在 i 号区块留下一个右脚印。同样地，如果一个人从 i 号区块移动到 (i - 1) 号区块，他将在 i 号区块留下一个左脚印。如果 i 号区块上已经有一个脚印，新脚印将覆盖旧脚印。
一开始，没有脚印。然后北极熊爱丽丝从 s 号区块出发，进行一系列移动，最后停在 t 号区块。已知爱丽丝从不离开这条路。
你将得到爱丽丝脚印的描述。你的任务是通过观察脚印找到一对可能的 s, t 值。
输入
输入的第一行包含整数 n (3 ≤ n ≤ 1000)。
第二行包含道路的描述——一个由 n 个字符组成的字符串。每个字符将是 "."（没有脚印的区块），或 "L"（有左脚印的区块），"R"（有右脚印的区块）。
可以保证给定的字符串至少包含一个不等于 "." 的字符。此外，第一个和最后一个字符将始终是 "."。可以保证存在解决方案。
输出
打印两个用空格分隔的整数——s 和 t 的值。如果有多个可能的解决方案，你可以打印其中任何一个。
示例
| Inputcopy | Outputcopy |
|---|---|
9 ..RRLL... |
3 4 |
| Inputcopy | Outputcopy |
|---|---|
11 .RRRLLLLL.. |
7 5 |
注意
第一个测试样例是图片中的那个。
3.思路
这是一道唐人构造
首先观察到，整个序列只有可能是若干个.+若干个R+若干个L+若干个.
接下来，我们发现可以这样构造：
从起点（R第一次出现的位置）开始往右走，到达最右边后转方向往左走，到达终点（R最后一次出现的位置）
但是我们发现WA on test 4了，发现，没有特判全是L的情况，所以我们还需要特殊处理一下，这里比较简单。
3.Code
#include<bits/stdc++.h>
using namespace std;
int n,flag,flag1;
char s[2000010];
main(){cin>>n;for(int i=0;i<n;i++){cin>>s[i];if(!flag and s[i]=='R')cout<<i+1<<' ',flag=1;}flag=0;for(int i=n-1;i>=0;i--){if(!flag and s[i]=='R')cout<<(s[i+1]=='L'?i+1:i+2)<<' ',flag=1;}if(flag)return 0;for(int i=n-1;i>=0;i--){if(!flag and s[i]=='L')cout<<i+1<<' ',flag=1;}flag=0;for(int i=0;i<n;i++){cin>>s[i];if(!flag and s[i]=='L')cout<<i<<' ',flag=1;}return 0;
}