Subtask 1
k = 1 k=1 k=1 的构造方式仅能为 l r l r l r l r … lrlrlrlr… lrlrlrlr… 或者 r l r l r l r l … rlrlrlrl… rlrlrlrl… 这种。
Subtask 2
n = m n=m n=m 的显然的解法就是输出 n 2 \displaystyle \frac{n}{2} 2n 个 l r lr lr。
综合上述算法可以得到 15 p t s 15pts 15pts 的好成绩!
Subtask 3,4
本质解法都是相同的。
k = 1 k=1 k=1 可以用 Sub1 的算法构造。
对于大部分的 k 可以如下构造,放 m 2 \displaystyle \frac{m}{2} 2m 个 l r lr lr,然后在后面连续接上 k k k 个 l l l 然后 1 1 1 个 r r r 这种循环。
but
这样的解法对于 k = 2 k=2 k=2 是有问题的,所以要做一点小调整。
观察知答案会增加 2 2 2。例子在右边,考虑 [ 2 9 ] \begin{bmatrix} 2 & 9 \end{bmatrix} [29] 的子串可知此时 m = 8 m=8 m=8:
I n p u t : Input: Input:
10 10 10 6 6 6 2 2 2
W r o n g O u t p u t : Wrong_Output: WrongOutput:
l r l r l r l l r l lrlrlrllrl lrlrlrllrl
所以可以在开头少放一个 l r lr lr 就可以保证答案不变了。
同时我们注意到所有不小于 2 2 2 的 k k k 都可以用 k = 2 k=2 k=2 的策略进行构造,所以连分类都省了。
然后你就被 h a c k ack ack 了!
我们事实上注意到上面的算法无法处理 n = m n=m n=m 的情况,于是我们可以选择特判。
但更简单的写法是,前面放的改成 r l rl rl,后面接的改成 l r l lrl lrl。这样就可以自然收掉 n = m n=m n=m。
然后你就可以喜提 100 pts 了!
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m,k;
cin>>n>>m>>k;
if(n==m||k==1)
{
for(int i=0;i<n;i++)if(i%2==0)cout<<"l";else cout<<"r";
}
else
{
if(k==2)
{
for(int i=0;i<m/2-1;i++)cout<<"lr";
for(int i=1;i<=n-m+2;i++)cout<<(i%(k+1)==0?"r":"l");
}
else
{
for(int i=0;i<m/2;i++)cout<<"lr";
for(int i=1;i<=n-m;i++)cout<<(i%(k+1)==0?"r":"l");
}
}
return 0;
}