codeforces#1248D2. The World Is Just a Programming Task（括号匹配转化为折线处理）

题目链接：

http://codeforces.com/contest/1248/problem/D2

题意：

可以执行一次字符交换的操作

使得操作后的字符串，循环移位并且成功匹配的方案最多

输出最多的方案数和交换的位置

数据范围：

$1\leq n \leq 300 000$

分析：

参考博客：https://www.cnblogs.com/LLTYYC/p/11718968.html

对于一个字符串，求它的循环移位匹配方案数

可以把字符串转换成折线，从0开始，遇到(则加一，遇到）则减一

如果(和)数量不同，明显答案是0，否则，答案是折线y最小值的顶点数量

可以偏移一下，使得最小值为0，那么整体折线向上偏移

如果折线归0，答案加一

那么考虑可以交换一次的情况

先对折线向上偏移

答案是1的数量或者 2的数量加不交换的答案，即，更改最小值为-1，或者增加0的数量，两种操作方案

其中区间1的数量最小值是1，区间2的数量同理

AC代码：

#include <bits/stdc++.h>

#define ll long long

#define pii pair<int,int>

using namespace std;

const int maxn=3e5+7;

int n;

char S[maxn];

int val[maxn];

int main(){

    scanf("%d",&n);

    scanf("%s",S+1);

    int off=0,minn=1e9;

    int now=0;

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

        if(S[i]==')')now--;

        else now++;

        if(minn>now){

            minn=now;

            off=i;

        }

    }

    if(now!=0){

        printf("0\n1 1\n");

        return 0;

    }

    int ans=0,ansl=1,ansr=1,anss=0;

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

        val[i+1]=val[i];

        int v=(off+i-1)%n+1;

        if(S[v]==')')val[i+1]--;

        else val[i+1]++;

        if(val[i]==0)ans++;

        //cout<<val[i]<<" ";

    }

   // coutMM

    anss=ans;

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

        if(val[i]==2){

            int en=i+1,tem=1;

            while(val[en]>=2){

                if(val[en]==2)tem++;

                en++;

            }

            if(tem+anss>ans){

                ans=tem+anss;

                ansl=(i+off-2+n)%n+1;

                ansr=(en+off-2+n)%n+1;

            }

            i=en;

        }

    }

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

        //cout<<val[i]<<" ";

        if(val[i]==1){

            int en=i+1,tem=1;

            while(val[en]>=1){

                if(val[en]==1)tem++;

                en++;

            }

            if(tem>ans){

                ans=tem;

                ansl=(i+off-2+n)%n+1;

                ansr=(en+off-2+n)%n+1;

            }

            i=en;

        }

    }

    printf("%d\n%d %d\n",ans,ansl,ansr);

    return 0;

}

巴特西

codeforces#1248D2. The World Is Just a Programming Task（括号匹配转化为折线处理）

题目链接：

题意：

数据范围：

分析：

AC代码：

最新文章

热门文章