P8437 题解

microchip · 2022-07-21 12:37:02 · 题解

打回去了一次QAQ 有些地方忘记加空格了

打月赛，只做出这一题......

个人认为这一题与NOI Online 2021的T1 切蛋糕有异曲同工之妙，都不涉及什么算法，得大量分类讨论，极其容易忽略情况（对某些赛制很不友好）。

我的想法：让长度为 m 的“神之子串”放在最前面，并保证后来不会再出现长度超过 m 的“神之子串”。

怎么实现呢？如果 n 等于 m ，那就好办了，让两个字母交替出现即可。但如果 n 小于 m，就要考虑后面的字符串该怎么安排了。

观察下面的字符串：

当m=6:
lrlrlrrrlrlrlrrrlrlrlrrrlrlrlr

不难发现，连续出现三次（及以上）同一个字符可以分隔不同的“神之子串”，所以我们可以让 l 与 r 交替出现，在长度达到 m 时再输出两个与当前"神之子串"末尾相同字符断开当前的“神之子串”，再继续让 l 与 r 交替出现，于是我们可以写下如下代码：

for(int i=1;i<=n;i++){
    if(l<m){  //在交替出现l与r
        if(l%2)cout<<'l';
        else cout<<'r';
    }else{
        if(i==n){
            if(l%2)cout<<'l';
            else cout<<'r';
            break;
        }if(i==n-1){
            if(l%2)cout<<"lr";
            else cout<<"rl";
            break;
        }
        if(l%2)cout<<"lrr";
        else cout<<"rll";
        l=0;i+=2;
    }l++;
}

但这种方法有个问题：首先，要断开当前的连续子串，必须要让 k≥3 ；其次，这种方法在 m=2 时行不通（你可以自己试一下）。所以我们就要讨论各种 k 小于 3 的情况了

1.如果 k=2 :

老样子，让 l 与 r 交替出现，但要断开数组就有问题了，由于只能让相同的字符连续出现两次，所以看看下面的字符串

设m=4：
lrlr

lrlrllr

也不难发现，在一个不能再往后扩展的"神之子串"后面，顶多再坚持三个字符，再往后"神之子串"长度就要超过 m 了。

那后面怎么办呢？

你读了读题，看见了这样一句话：数据保证可以找出神 TU 喜欢的字符串

所以就直接用 llr 结尾就行啦（注意字符串长度别超过 n）

代码如下：

for(int i=1;i<m/2;i++){//先lr互相出现
    cout<<"lr";
}n-=2*(m/2-1);
for(int i=1;i<=n;i++){//再用llr结尾
    if(i%3)cout<<'l';
    else cout<<'r';
}return 0;

2.如果 k=1：

那就只能 l 与 r 一直交替出现下去，根据那句"数据保证可以找出神 TU 喜欢的字符串"就知道，交替出现到结尾就是答案啦。再看看我们一开始写的没有任何特殊条件的代码，行吧，这种情况不需要写特殊代码，直接跑一开始写的代码就能得出答案

3.如果 m=2：