题意

圆形链条，打断一处可以形成一条链。问在哪个地方开始打断，能够形成最大的连续颜色（白色视作同样的颜色）？

分析

说起来很高级，但是我们实际上并不需要穷举打断的地方，只需要把串重复三回啊三回。然后从第二个串的左边开始循环找连续颜色的“初始色”（如果是白色，那么左右看看），在初始色的左右找相同。可以看出共有n个初始色的位置，所以算法也就是O(n2)" role="presentation">O(n2)O(n2)的复杂度。然后还有一些细节要处理。作为一条初级题目，比较锻炼这个时候的萌新的代码力。

代码

/*

ID: samhx1

LANG: C++14

TASK: beads

*/

#include <bits/stdc++.h>

#define MP make_pair

#define PB push_back

#define fi first

#define se second

#define ZERO(x) memset((x), 0, sizeof(x))

#define ALL(x) (x).begin(),(x).end()

#define rep(i, a, b) for (ll i = (a); i <= (b); ++i)

#define per(i, a, b) for (ll i = (a); i >= (b); --i)

#define QUICKIO                  \

    ios::sync_with_stdio(false); \

    cin.tie(0);                  \

    cout.tie(0);

using namespace std;

using ll = long long;

using ull = unsigned long long;

using pi = pair<ll,ll>;

signed main()

{

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

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

    int n; string str; cin>>n>>str;

    string judgeStr=str+str+str; // damn 0

    int maxans=-1;

    for(int i=n;i!=n*2;++i)

    {

        char clr_left=judgeStr[i-1]; int cnt_left=0;

        while(clr_left=='w' && cnt_left<n) // damn 1

            clr_left=judgeStr[i-1-(++cnt_left)];

        while((judgeStr[i-1-cnt_left]==clr_left || judgeStr[i-1-cnt_left]=='w') && cnt_left<n) //damn 2

            cnt_left++;

        char clr_right=judgeStr[i]; int cnt_right=0;

        while(clr_right=='w' && cnt_right+cnt_left<n)

            clr_right=judgeStr[i+(++cnt_right)];

        while((judgeStr[i+cnt_right]==clr_right || judgeStr[i+cnt_right]=='w') &&

        cnt_left+cnt_right<n)

            cnt_right++;

        //cout<<i-n<<" "<<cnt_left<<" "<<cnt_right<<endl;

        maxans=max(maxans,cnt_left+cnt_right);

    }

    cout<<maxans<<endl;

    return 0;

}

巴特西

「日常训练」「小专题·USACO」 Broken Necklace（1-2）

题意

分析

代码

最新文章

热门文章