坏掉的项链（洛谷P1203题题解，C++语言描述）

电玩女神 2022-10-22 02:57 171阅读 0赞

# 题目要求 #

[题目链接][Link 1]

![在这里插入图片描述][20210403120033161.png]

# 分析 #

链子是循环的，随便选一点断开不合适，所以把它作为一个线性的字符串其实不好。

处理方法是将字符串扩增一倍，即`necklace += necklace;`

这样的话，我们从初始出发，必然能遍历整个链子且不受出发点的影响。

我的思路类似于非递归的斐波那契数列，设置一个prev一个temp，比较result和prev+temp的大小，取最大值。

遍历的时候细节有很多：

1.  先初始化prev，要小心w作为开头，因为w相当于邻近的r或b
2.  每一轮都考虑当前r或b，尽可能多地取，包含w也取下来，统计temp
3.   r e s u l t = m a x ( r e s u l t , t e m p + p r e v ) result = max(result, temp+prev) result=max(result,temp\+prev)
4.  更新prev，不能更新为temp，而还要考虑到本轮初始的i前面的w，所以要加上

于是乎，我WA了三个数据点，如下：

测试用例2输入：

3
    rrr

测试用例2输出：

测试用例4输入：

17
    wwwwwwwwwwwwwwwww

测试用例4输出：

测试用例6输入：

8
    rrwwwwbb

测试用例6输出：

分别是三处细节问题，本质是一样的，即我没有考虑到一遍就跑完的情况，重复导致额外多加了很多。

处理方法是补充原则性判断  i < n i < n i<n 和  t e m p + p r e v ≤ n temp+prev ≤ n temp\+prev≤n

代码有注释，自行食用！

推荐[好的题解][Link 2]，但确实难懂，各位大神耗子尾汁。

# AC代码 #

#include <iostream>
    #include <cmath>
    
    using namespace std;
    
    int main() {
        
        int n, prev = 0, temp, result, i = 0, j;
        string necklace;
        cin >> n >> necklace;
        // 复制一份
        necklace += necklace;
        char prev_c, temp_c;
        // 合并最初的w
        while ((necklace[i] == 'w') && i < n) {
        
            prev++;
            i++;
        }
        // 初始化找出第一个prev 包含当前或w
        prev_c = necklace[i];
        // 限制防止跑两遍
        while ((necklace[i] == prev_c || necklace[i] == 'w') && i < n) {
        
            prev++;
            i++;
        }
        result = prev;
        // 否则会双倍
        if (i < n) {
        
            // 正式开始遍历
            for (; i < 2*n;) {
        
                temp = 0;
                temp_c = necklace[i];
                // 反向遍历找出前方w数
                j = i-1;
                // 合并之前的w
                while (necklace[j] == 'w') {
        
                    j--;
                }
                j = i-j-1;
                // 找出当前temp 包含当前或w
                while (necklace[i] == temp_c || necklace[i] == 'w') {
        
                    temp++;
                    i++;
                }
                if (temp+prev <= n) {
        
                    result = max(result, temp+prev);
                }
                // 由于每一个temp只考虑它和它后面的w，不考虑前面的w，所以当变成prev前要把当前temp的数量加上之前的w个数
                prev = temp+j;
            }
        }
        cout << result;
        return 0;
    }

[Link 1]: https://www.luogu.com.cn/problem/P1203
[20210403120033161.png]: /images/20221022/8bf428866a234ad3bd125c3f76418871.png
[Link 2]: https://www.luogu.com.cn/blog/user48991/solution-p1203