P1203 [USACO1.1]坏掉的项链Broken Necklace

P1203 [USACO1.1]坏掉的项链Broken Necklace
Luogu
应用
题库
训练
比赛
记录
讨论
4.7K
通过
12.6K
提交
题目提供者 FarmerJohn2
评测方式云端评测
标签 USACO
难度普及-
时空限制 1000ms / 128MB
提交题解

提示：收藏到任务计划后，可在首页查看。
最新讨论显示
推荐的相关题目显示
题目描述

你有一条由N个红色的，白色的，或蓝色的珠子组成的项链(3<=N<=350)，珠子是随意安排的。这里是 n=29 的二个例子:

第一和第二个珠子在图片中已经被作记号。

图片 A 中的项链可以用下面的字符串表示：
P1203 [USACO1.1]坏掉的项链Broken Necklace
brbrrrbbbrrrrrbrrbbrbbbbrrrrb

假如你要在一些点打破项链,展开成一条直线，然后从一端开始收集同颜色的珠子直到你遇到一个不同的颜色珠子，在另一端做同样的事(颜色可能与在这之前收集的不同)。确定应该在哪里打破项链来收集到最大数目的珠子。

例如，在图片 A 中的项链中，在珠子 9 和珠子 10 或珠子 24 和珠子 25 之间打断项链可以收集到8个珠子。

白色珠子什么意思?

在一些项链中还包括白色的珠子(如图片B) 所示。

当收集珠子的时候，一个被遇到的白色珠子可以被当做红色也可以被当做蓝色。

表现含有白珠项链的字符串将会包括三个符号 r ， b 和 w 。

写一个程序来确定从一条被给出的项链可以收集到的珠子最大数目。

输入输出格式

输入格式：
第 1 行: N, 珠子的数目

第 2 行: 一串长度为N的字符串, 每个字符是 r ， b 或 w。

输出格式：
输出一行一个整数，表示从给出的项链中可以收集到的珠子的最大数量。

输入输出样例

输入样例#1：复制
29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
输出样例#1：复制
11

代码如下（洛谷）：

#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<stack>
#include<map>
 
using namespace std;
 
#define FOU(i,x,y) for(int i=x;i<=y;i++)
#define FOD(i,x,y) for(int i=x;i>=y;i--)
#define MEM(a,val) memset(a,val,sizeof(a))
#define PI acos(-1.0)
 
const double EXP = 1e-9;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const ll MINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+7;
const int N = 1e6+5;
 
char a[750];
int n;
 
int solve(int x)
{
    int cnt1=0;
    char tmp='x';
    for(int i=x-1;i>=0;i--)
    {
        if(a[i]=='w')
            cnt1++;
        else
        {
            if(tmp=='x')
            {
                cnt1++;
                tmp=a[i];
            }
            else
            {
                if(a[i]==tmp)
                    cnt1++;
                else
                    break;
            }
        }
    }
    int cnt2=0;
    tmp='x';
    for(int i=x;i<2*n;i++)
    {
        if(a[i]=='w')
            cnt2++;
        else
        {
            if(tmp=='x')
            {
                cnt2++;
                tmp=a[i];
            }
            else
            {
                if(a[i]==tmp)
                    cnt2++;
                else
                    break;
            }
        }
    }
    return cnt1+cnt2;
}
 
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    std::ios::sync_with_stdio(false);
    while(~scanf("%d",&n))
    {
 
        scanf(" %s",&a);
        for(int i=n;i<2*n;i++)
            a[i]=a[i-n];
        int ans=0;
        for(int i=1;i<2*n;i++)
        {
            ans=max(ans,solve(i));
        }
        printf("%d\n",min(ans,n));
    }
    return 0;
}

USACO代码如下：

/*
ID: a1s2d1f1
LANG: C++
TASK: beads
*/
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<stack>
#include<map>
 
using namespace std;
 
#define FOU(i,x,y) for(int i=x;i<=y;i++)
#define FOD(i,x,y) for(int i=x;i>=y;i--)
#define MEM(a,val) memset(a,val,sizeof(a))
#define PI acos(-1.0)
 
const double EXP = 1e-9;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const ll MINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+7;
const int N = 1e6+5;
 
char a[750];
int n;
 
int solve(int x)
{
    int cnt1=0;
    char tmp='x';
    for(int i=x-1;i>=0;i--)
    {
        if(a[i]=='w')
            cnt1++;
        else
        {
            if(tmp=='x')
            {
                cnt1++;
                tmp=a[i];
            }
            else
            {
                if(a[i]==tmp)
                    cnt1++;
                else
                    break;
            }
        }
    }
    int cnt2=0;
    tmp='x';
    for(int i=x;i<2*n;i++)
    {
        if(a[i]=='w')
            cnt2++;
        else
        {
            if(tmp=='x')
            {
                cnt2++;
                tmp=a[i];
            }
            else
            {
                if(a[i]==tmp)
                    cnt2++;
                else
                    break;
            }
        }
    }
    return cnt1+cnt2;
}
 
int main()
{
    freopen("beads.in","r",stdin);
    freopen("beads.out","w",stdout);
    std::ios::sync_with_stdio(false);
    while(~scanf("%d",&n))
    {
 
        scanf(" %s",&a);
        for(int i=n;i<2*n;i++)
            a[i]=a[i-n];
        int ans=0;
        for(int i=1;i<2*n;i++)
        {
            ans=max(ans,solve(i));
        }
        printf("%d\n",min(ans,n));
    }
    return 0;
}

代码仅供参考，如有更简的代码，请回复。

P1203 [USACO1.1]坏掉的项链Broken Necklace

相关推荐