USACO Section 1.1 Broken Necklace 解题报告

2022-03-18 03:34:23

题目

题目描述

有一串项链，它是由红蓝白三种颜色的珠子组成的，b代表蓝色，w代表白色，r代表红色，当它完整的时候是一个闭合的环形。现在它在某一个节点断裂了，之前的环形也随之变成了直线形。从两端开始收集这些珠子，收集的规则是只能收集与端点珠子相同颜色的，且是连在一起的珠子。白色的珠子可以染色成为红色的或者是蓝色的，也就是说白色的珠子可以看成是蓝色的或者是红色的。例如我现在有一串断裂的项链，它的珠子排列成下面的这种方式：

bwwbrbbrwwr

当我从左边开始收集珠子的时候，我只能收集到bwwb，从右边开始收集只能收集到rwwr，这样我总共可以收集8颗珠子。现在的问题是：有一条项链由N个珠子组成，在哪一个断点断开我们可以收集到最多的珠子，输出收集最多的珠子数量。

数据范围

3 <= N <= 350

样例输入

29

wwwbbrwrbrbrrbrbrwrwwrbwrwrrb

样例输出

解题思路

最朴素暴力的解法就是枚举每一个断裂的位置，然后对每一种情况来模拟收集珠子，最后保存一个最大值。但是这种解法的时间复杂度比较高O(N^2)。

在写代码的时候注意几个细节：

在写x == 'A'这种语句的时候，最好写成'A' == x，这样可以避免手误写成x = 'A'，一旦出现这种bug一般很难检查出来。
下面的代码中第三个注释是一个很重要的条件。

解题代码

/*

ID: yinzong2

PROG: beads

LANG: C++11

*/

#define MARK

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

using namespace std;

const int maxn = 400;

int n, _max;

char str[maxn];

void work(int b, int e, int len) {

    char left = str[b];

    char right = str[e];

    int p = b;//用p来保存从左端开始收集，最多能到达的位置，当从右边开始收集的时候不能超过此位置。

    int cnt1 = 1, cnt2 = 1;

    for(int i = (b-1+len)%len; i != e; i = (i-1+len)%len) {

        //注意这种写法，能够避免将判断写成赋值的错误

        if('w' == left) {

            left = str[i];

        } else {

            //str[i] != 'w'是一个很重要的条件，只有当下一个珠子的颜色不一样且不是白色的时候才能进行下一步

            if(str[i] != left && str[i] != 'w') {

                break;

            }

        }

        cnt1++;

        p = i;

    }

    for(int i = (e+1)%len; i != p; i = (i+1)%len) {

        if('w' == right) {

            right = str[i];

        } else {

            if(str[i] != right && str[i] != 'w') {

                break;

            }

        }

        cnt2++;

    }

    _max = (cnt1+cnt2) > _max ? (cnt1+cnt2) : _max;

}

int main() {

#ifdef MARK

    freopen("beads.in", "r", stdin);

    freopen("beads.out", "w", stdout);

#endif

    while(~scanf("%d", &n)) {

        scanf("%s", str);

        int len = strlen(str);

        if(len <= 2) {

            printf("%d\n", len);

            continue;

        }

        bool allSame = true;

        _max = 0;

        for(int i = 0; i < len; i++) {

            if(str[i] != 'w' || str[(i+1)%len] != 'w') {

                work(i, (i+1)%len, len);

                allSame = false;

            }

        }

        if(allSame) printf("%d\n", len);

        else printf("%d\n", _max);

    }

    return 0;

}

在官方给的解析中有一个写法挺有意思的，也比较简洁。思路还是与上述一致，只是换了一种遍历方法。代码如下：

/*

ID: yinzong2

PROG: beads

LANG: C++11

*/

#define MARK

#include <cstdio>

#include <iostream>

#include <cstring>

#include <string>

using namespace std;

int n;

string s;

// 采用另一种思维方式，我们从左往右开始遍历，同样也是遍历每一个可以切割的点，具体看代码

int main() {

#ifdef MARK

    freopen("beads.in", "r" ,stdin);

    freopen("beads.out", "w", stdout);

#endif // MARK

    cin >> n >> s;

    s = s+s;

    int ans = 0;

    for (int i = 0; i < n; ++i) {

        char c = s[i];

        int cnt = 0;

        // 注意这个状态的设置很有技巧性

        int state = 0;

        if ('w' == c) {

            state = 0;

        } else {

            state = 1;

        }

        int j = i;

        while (state <= 2) {

            while (j < n+i && ((s[j] == c) || 'w' == s[j])) {

                j++;

                cnt++;

            }

            state++;

            c = s[j];

        }

        ans = max(ans, cnt);

    }

    cout << ans << endl;

    return 0;

}

解题思路(Type 2)

上一种方法时间复杂度是O(N^2)，当数据量比较大的时候不能算是一个好的算法。我们可以接着进行优化，在参考了一些资料之后，发现可以用动态规划(dp)的思想将时间复杂度优化到O(N)。

具体操作如下：

我们为了方便模拟环，可以将珠子复制一份，使之变成线性的。
我们用四个数组bl[i]、br[i]、rl[i]、rr[i]来记录一些数据：
- bl[i]表示从第i颗珠子开始，向左边开始收集blue颜色的珠子，能够收集到的数目。
- br[i]表示从第i颗珠子开始，向右边开始收集blue颜色的珠子，能够收集到的数目。
- rl[i]表示从第i颗珠子开始，向左边开始收集red颜色的珠子，能够收集到的数目。
- rr[i]表示从第i颗珠子开始，向右边开始收集red颜色的珠子，能够收集到的数目。
状态转移方程如下：
- 从左端开始计算bl[],rl[]
- 当第i颗珠子是b时，bl[i] = bl[i-1] + 1; rl[i] = 0;
- 当第i颗珠子是r时，rl[i] = rl[i-1] + 1; bl[i] = 0;
- 当第i颗珠子是w时，bl[i] = bl[i-1] + 1; rl[i] = rl[i-1] + 1;
- 从右端开始计算br[],rr[]，与上述同理可得。
- 最终的结果为max( max(bl[i], rl[i]) + max(br[i+1], rr[i+1]) )

解题代码(Type 2)

/*

ID: yinzong2

PROG: beads

LANG: C++11

*/

#define MARK

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<algorithm>

using namespace std;

const int maxn = 360;

const int Maxn = 2*maxn;

int n, _max;

char str[Maxn], temp[maxn], s[Maxn+1];

int bl[Maxn], rl[Maxn];

int br[Maxn], rr[Maxn];

int main() {

#ifdef MARK

    freopen("beads.in", "r", stdin);

    freopen("beads.out", "w", stdout);

#endif // MARK

    while(~scanf("%d", &n)) {

        scanf("%s", str);

        strcpy(temp, str);

        strcat(str, temp);

        //为了方便后面的操作，我让字符串下标从1开始到2*n结束

        strcpy(s+1, str);

        //从左端开始，计算每一颗珠子从自身开始向左收集，最多能够收集到的数目

        bl[0] = rl[0] = 0;//虚拟出来第0颗珠子，使得第一颗珠子能够按照标准统一处理

        for(int i = 1; i <= 2*n; i++) {

            if('b' == s[i]) {

                bl[i] = bl[i-1] + 1;

                rl[i] = 0;

            } else if('r' == s[i]) {

                rl[i] = rl[i-1] + 1;

                bl[i] = 0;

            } else {

                bl[i] = bl[i-1] + 1;

                rl[i] = rl[i-1] + 1;

            }

        }

        //从右端开始，计算每一颗珠子从自身开始向右收集，最多能够收集到的数目

        br[2*n+1] = rr[2*n+1] = 0;//虚拟出来第2*n+1颗珠子，使得最后一颗珠子能够按照标准统一处理

        for(int i = 2*n; i >= 1; i--) {

            if('b' == s[i]) {

                br[i] = br[i+1] + 1;

                rr[i] = 0;

            } else if('r' == s[i]) {

                rr[i] = rr[i+1] + 1;

                br[i] = 0;

            } else {

                br[i] = br[i+1] + 1;

                rr[i] = rr[i+1] + 1;

            }

        }

        _max = 0;

        for(int i = 1; i < 2*n; i++) {

            _max = max(_max, max(bl[i], rl[i])+max(br[i+1], rr[i+1]));

        }

        //防止项链是由一种颜色组成的，这个时候有重复计算，会超过n

        _max = min(_max, n);

        printf("%d\n", _max);

    }

    return 0;

}

码农公寓

题目