P8437 题解

· · 题解

首先，对于一组 n,m,k，我们很容易可以构造出如下方案：

\overbrace{lrlrlrlr\cdots}^{m\texttt{个}}\;\underbrace{lllll\cdots}_{k\texttt{个}}\;rlllll\cdots r\cdots

很容易发现，在第 m 个字符之后，l 字符的数量始终大于 r 字符的数量。所以可以始终保证最大的神之子串长度为 m。
但是有一个小小的问题。当 n=10,m=6,k=\color{red}2 时，就会出现这种情况：

l\;\overbrace{rlrlrllr}^{8?}\;l

很明显，我们的算法炸了。原因就出在中间 rllr 这一段。由于 k=2，所以在后缀第一次进入循环时，l 会恰好等于 r+1。也就是说，去掉头一个 l，就能得到更长的子串。因此，我们需要做一些小小的改动，把 rllr 纳入子串里，即：

\overbrace{lrlrlrlr\cdots rl}^{m\texttt{个}}\;rrlrrl\cdots

特判一下即可得到正确答案。

AC 代码

#include <bits/stdc++.h>

using namespace std;

int n, m, k;

int main() {
    scanf("%d%d%d", &n, &m, &k);
    if (k != 2) { // 特判k
        for (int i = 1; i <= m; ++i) putchar(i & 1 ? 'l' : 'r'); // lr循环字串部分
        for (int i = m + 1; i <= n; i += k + 1) {  //lll...r循环部分
            for (int j = i; j < i + k && j <= n; ++j) putchar('l');
            if (i + k <= n) putchar('r');
        }
    } else {
        for (int i = 1; i <= m - 2; ++i) putchar(i & 1 ? 'l' : 'r'); putchar('r'), putchar('l'); //lrlr...rl（小改动）
        for (int i = m + 1; i <= n; i += 3) {
            putchar('r');
            if (i + 1 <= n) putchar('r');
            if (i + 2 <= n) putchar('l');
        }
    }
}