CF298A Snow Footprints 题解

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;
}