P8437 题解

· · 题解

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

本题的最大切入口在于：

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 计划。对解决此类问题有着大大的帮助。