洛谷链接 https://www.luogu.com.cn/problem/P9015

解题思路

我们首先来仔细读题并观察样例。可以发现，有以下 $3$ 个性质：

• $A_i\ge2$ 且 $A_i$ 为偶数。

这个性质很显然：若 $A_i<2$，则 Bessie 必然不可能完成一次折返。而一次折返会消耗两次次数，所以，当 $A_i$ 为奇数时，必然无解。

• 最后输出字符串的长度为 $\displaystyle\sum A_i$。

这依然是一个明显的性质，甚至在题目中也有提及。

这是题目中的原话：

Output a string $S$ of length $T=\sum\limits_{i=0}^{N-1}A_i$ where $S_i$ is L or R, indicating the direction Bessie travels in during second i. If there are multiple routes minimizing the number of direction changes, output any.

• 答案字符串中，字符 L 的数量与 R 相等，均为 $\dfrac{n}{2}$。

很好解释，由于最后需要回到起点，所以往右走的步数必须等于往左走的步数。

接着就可以进行贪心——最优的策略是能走就走，不能走就换方向，因为题目中明确表示了一定有解。

假设当前 Bessie 所在的点为 $x$，那么初始时有 $x=0$。

先考虑往右走，策略如下：

• 往右走：

接着，$\texttt{while}$ 循环结束，意味着该往左走了。

• 往左走：

最后，判断是否结束程序的条件自然就是 Bessie 回到了起点并且所有的边都走完了，即 $x=0$ 且 $vis_0$ 为假。

题目坑点

1. $x$ 从 $0$ 开始；
2. $A$ 数组的下标为 $0\sim n-1$；