题目链接

BZOJ2213

题解

考虑任意一对点的贡献，单独拿出那些点所在位置
一个设为\(1\)，一个设为\(-1\)，从头到尾扫一遍维护前缀和，以及当前最小前缀和
两者相减更新答案
需要注意的是当前最小前缀和更新的位置之后必须存在另一个字符，否则就不满足最小出现次数最少大于\(0\)的限制

由于每个位置最多拿出来\(26\)次，所以是\(O(26n)\)的

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
#include<cmath>
#include<vector>
#include<map>
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define mp(a,b) make_pair<int,int>(a,b)
#define cls(s) memset(s,0,sizeof(s))
#define cp pair<int,int>
#define LL long long int
using namespace std;
const int maxn = 1000005,maxm = 100005,INF = 1000000000;
inline int read(){
    int out = 0,flag = 1; char c = getchar();
    while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
    while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
    return out * flag;
}
vector<int> pos[26];
int n,ans;
void work(int x,int y){
    int nowx = 0,nowy = 0,minx = INF,miny = INF,mnx = 0,mny = 0;
    unsigned int px = 0,py = 0;
    while (px < pos[x].size() || py < pos[y].size()){
        if (py == pos[y].size() || (px < pos[x].size() && pos[x][px] < pos[y][py])){
            miny = min(miny,mny);
            nowx++; nowy--;
            px++;
        }
        else {
            minx = min(minx,mnx);
            nowy++; nowx--;
            py++;
        }
        mnx = min(nowx,mnx); mny = min(mny,nowy);
        if (minx < INF) ans = max(ans,nowx - minx);
        if (miny < INF) ans = max(ans,nowy - miny);
    }
}
int main(){
    n = read(); int x; char c = getchar();
    while (!isalpha(c)) c = getchar();
    for (int i = 1; i <= n; i++){
        x = c - 'a';
        pos[x].push_back(i);
        c = getchar();
    }
    for (int x = 0; x < 26; x++)
        for (int y = x + 1; y < 26; y++)
            work(x,y);
    printf("%d\n",ans);
    return 0;
}

转载于:https://www.cnblogs.com/Mychael/p/9218353.html

原文链接：https://blog.csdn.net/weixin_30342827/article/details/99037296

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。