洛谷【P8437伟大的神】题解

题面描述

原题链接

伟大的神 TU 认为 ，一个所有出现的字符的数量相等的字符串是属于神的，他称之为神之字符串。
对于一个字符串 S S S，如果它的一个子串为神之字符串，即称这个子串为神之子串。
神 TU 认为，他喜欢的字符串只能由 l l l 和 r r r 构成，并且还要满足以下条件：
字符串的长度为 n n n。
字符串中最长神之子串长度为 m m m。
字符串中连续的相同的字符的数量不能超过 k k k。
弱小的神小 s 找不出神 TU 喜欢的字符串，现在他找到了你，你能帮帮他吗？

分析 部分分 Subtask 1( k = 1 k=1 k=1)

因为保证有解，所以 l l l和 r r r交替输出即可。

Subtask 2( n = m n=m n=m)

也就是说整个串的 l l l和 r r r数量一样，所以同样也是交替输出。

Subtask 3( k ≥ 3 k geq 3 k≥3)

交替输出 m / 2 m/2 m/2个 l l l和 r r r，接下来按两个 l l l一个 r r r的顺序输出就好了。

正解

当你把上述解决方法提交上去后，你会发现只能通过45%的数据，这是为什么呢？
Subtask1的范围是 k = 1 k=1 k=1,Subtask3的范围是 k ≥ 3 k geq 3 k≥3,不妨去考虑一下 k = 2 k=2 k=2的情况。
假设 n = 10 , m = 6 , k = 2 n=10,m=6,k=2 n=10,m=6,k=2,按Subtask3的做法，结果应该是：

lrlrlrllrl

第二到第九个字符（从1开始）的 l l l和 r r r数量相等，一共是8个字符，显然不对了。
在 m m m与 n n n不相等的情况下，我们可以在一开始少输出一组 l r lr lr，就可以解决该问题。

代码

#include 
using namespace std;


int main()
{
	int n,m,k;
	cin>>n>>m>>k;
	if(n==m)
	{
		for(int i=1;i<=m;i++)
		{
			if(i%2==1) cout<<"l";
			else cout<<"r";
		}
	} 
	else
	{
		int cnt=0,t=m-1;
		if(k>=2)k=2;
		for(int i=1;i<=m/2-1;i++) cout<<"lr";
		while(t<=n)
		{
			cnt++;
			if(cnt<=k) cout<<"l";
			else
			{
				cout<<"r";
				cnt=0;
			}
			t++;
		}
	}
	return 0;
}