自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 22:39:03，当前版本为作者最后更新于2022-07-18 12:28:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

值得一提的是，本题赛时 AC 率并非洛谷月赛 div.2A 最低，但是我单方面认为这是洛谷月赛最难的 div.2A。

本题的最大切入口在于：

• 数据保证可以找出神 TU 喜欢的字符串。
• 输入的 $m$ 均为偶数。

Subtask 1

本 subtask 满足性质 $k=1$。

因为连续的相同的字符的数量不能超过 $1$，为了确保 $S$ 中存在一个子串是“神”的，即所有出现的字符的数量相等，只需构造出 $\texttt{lrlrlrlr\dots}$ 的字符串即可。因为数据保证一定存在解，所以这样做是可行的。

Subtask 2

本 subtask 满足性质 $n=m$。

也就是说字符串 $S$ 为最长神之子串。实际上，Subtask 1 中构造出的 $\texttt{lrlrlrlr\dots}$ 即可符合这个要求。这是因为，$S$ 为最长神之子串，则 $S$ 必然是个偶数，否则无法满足 $\texttt l$ 与 $\texttt r$ 的个数相等。

Subtask 3

本 subtask 满足性质 $k \geq 3$。

我们的想法是：可以先构造出一个长度为 $m$ 的最长神之子串，然后再在后面随意添加字符，使得后面的部分不构成神之子串。

而在满足不能有超过 $k$ 个连续字符的情况下，前面的神之子串可以仿照上面两个 subtask 进行构造，即构造出长度为 $m$ 的字符串 $\texttt{lrlr\dots}$。需要注意的是 $m$ 为偶数，所以前面的神之子串在这样的构造情况下结尾字符是 $\texttt r$。接着为了让后面构成不了神之子串，我们可以放 $2$ 个 $\texttt{l}$ 与 $1$ 个 $\texttt{r}$。这样恰好满足连续字符不超过 $k$，且最长神之子串的长度为 $m$。

Subtask 4

注意，这里有个大坑点！在 $k=2$ 的情况下，上述构造不一定适用。以一组数据为例：

$\texttt{Input Data: 10 6 2}$

以上面的构造会得出如下结果：

$\texttt{Output Data: lrlrlrllrl}$

这个结果经不起推敲，因为该字符串从第 $2$ 位取到第 $9$ 位的话，正好存在 $4$ 个 $\texttt l$ 和 $4$ 个 $\texttt r$，使得实际的最长神之子串的长度是 $8$ 而不是 $6$。

实际上，这种情况只会在一开始的循环字符串 $\texttt{lr}$ 的后段，与后面的 $\texttt{lll\dots r}$ 段的前面会发生。因此，我们可以考虑破坏掉一开始的循环字符串后端，将最后一个 $\texttt{lr}$ 转化成 $\texttt{rl}$。

这样再仿照上述构造，即可完成本题。

#include <iostream>
using namespace std;
int main()
{
	int n,m,k;
	cin >> n >> m >> k;
	if (k==1)
	{
		for (int i=1;i<=n;i++)
			cout << (i&1?'l':'r');
		return 0;
	}
	for (int i=1;i<=m-2;i++)
		cout << (i&1?'l':'r');
	int cnt=1;
	cout << "rl";
	for (int i=m+1;i<=n;i++)
	{
		if (cnt==0)
			cout << 'l';
		else
			cout << 'r';
		cnt++;
		cnt%=3;
	}
	return 0;
}

打个广告：可爱八云蓝的 adhoc 计划。对解决此类问题有着大大的帮助。