cjb-poi2011difference

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#define rep(i,n) for(int i=1;i<=n;i++)
#define mp make_pair
#define pb push_back
using namespace std;
#define PI 3.1415926535897932384626433
#define N 1000010
#define LF double
int n;
char s[N];
int a[N];
int ans=0;
vector<int> f[30];
void fuck(int x,int y)
{

    int tot=0;
    int h1=0,h2=0,cntx=f[x].size(),cnty=f[y].size();
    if (!cntx || !cnty)return;
    while (h1<cntx && h2<cnty)
        if (f[x][h1]<f[y][h2])a[++tot]=1,h1++;
        else a[++tot]=-1,h2++;
    for(int i=h1;i<cntx;i++)a[++tot]=1;
    for(int i=h2;i<cnty;i++)a[++tot]=-1;
    int now=0,flag=0;
    rep(i,tot)
    {
        now+=a[i];
        if (a[i]==-1)flag=1;
        if(flag)ans=max(ans,now);
        if (now<0)flag=now=0;
    }
    ans=max(ans,now-1); // 因为两种字母一定至少有一个，不加这句特判会导致末尾一段连续的1会被忽略。
}
int main()
{
    cin>>n;
    scanf("%s",s+1);
    rep(i,n)f[s[i]-'a'].pb(i);
    for(int i=0;i<26;i++)
        for(int j=0;j<26;j++)
            if (i!=j)fuck(i,j);
    cout<<ans<<endl;
}

/*
4
baaa
*/
}}}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#define rep(i,n) for(int i=1;i<=n;i++)
#define mp make_pair
#define pb push_back
using namespace std;
#define PI 3.1415926535897932384626433
#define N 1000010
#define LF double
int n;
char s[N];
int a[N];
int ans=0;
vector<int> f[30];
void fuck(int x,int y)
{
    int tot=0;
    int h1=0,h2=0,cntx=f[x].size(),cnty=f[y].size();
    if (!cntx || !cnty)return;
    while (h1<cntx && h2<cnty)
        if (f[x][h1]<f[y][h2])a[++tot]=1,h1++;
        else a[++tot]=-1,h2++;
    for(int i=h1;i<cntx;i++)a[++tot]=1;
    for(int i=h2;i<cnty;i++)a[++tot]=-1;
    int now=0,flag=0;
    rep(i,tot)
    {
        now+=a[i];
        if (a[i]==-1)flag=1;
        if(flag)ans=max(ans,now);
        if (now<0)flag=now=0;
    }
    ans=max(ans,now-1); // 因为两种字母一定至少有一个，不加这句特判会导致末尾一段连续的1会被忽略。
}
int main()
{
    cin>>n;
    scanf("%s",s+1);
    rep(i,n)f[s[i]-'a'].pb(i);
    for(int i=0;i<26;i++)
        for(int j=0;j<26;j++)
            if (i!=j)fuck(i,j);
    cout<<ans<<endl;
}
/*
4
baaa
*/