[POI 18 Stage 2] Difference

作法：

首先可以把其中兩種字母抽出來看，這樣可以求出一個答案，而對所有可能的字母組都求一次答案，並且取這些答案的 max 即可，不難證明這樣會是對的。所以現在問題轉化為如何求一個只有兩種字元的字串的答案。假設他們一個是 a 一個是 b 好了，考慮平面上的點集 ( x_i , y_i ) ，其中 x_i 和 y_i 分別代表前 i 個數裡面有幾個 a 和幾個 b ( 就是一個前綴和的概念 )，而我們的目標是要找到 i , j 使得 | ( x_i - x_j ) - ( y_i - y_j ) | 最大，可以改寫成 | ( x_i - y_i ) - ( x_j - y_j ) |，也就是如果記 f ( x , y ) = x - y ，那麼我們想要求的就是 | f ( i ) - f ( j ) | 的最大值。但 i , j 還必須要有個限制，就是不能有 x_i = x_j 或是 y_i = y_j ( 因為這樣會變成 i+1 ~ j 中只有一種字母 )，所以用雙指標，記錄當前合法的 f ( j ) 的最大和最小值，當算到 ( x_i , y_i ) 的時候用所有剛變合法的 f ( j ) 拿去更新最大和最小值，那麼以 ( x_i , y_i ) 為右端點的答案就會是 | f ( i ) - mi | 或是 | f ( i ) - ma | ，其中 mi 和 ma 分別為當前合法 f 值的最小和最大值，對全部取 max 就可以得到答案了。

code :

#include<bits/stdc++.h>
#define INF 10000000
#define ABS(x) ( (x)>0 ? (x) : (-(x)) )
using namespace std;
const int maxn=1000000+10 ;
 
struct P{int x,y;};
P cal(const P &p,int t)
{
    return t==0 ? (P){p.x,p.y+1} : (P){p.x+1,p.y} ;
}
 
vector<int> v[26] ;
int tmp[maxn] ;
int solve(const vector<int> &v1,const vector<int> &v2)
{
    int cnt=0 , j=0 ;
    for(int i=0;i<v1.size();i++)
    {
        while(j<v2.size() && v2[j]<v1[i])
            j++ , tmp[cnt++]=1 ;
        tmp[cnt++]=0 ;
    }
    while(j<v2.size()) tmp[cnt++]=1 , j++ ;
 
    int ret=0 ;
    P p={0,0},p2={0,0} ;
    for(int i=0,j=0 , mi=0,ma=0;i<cnt;i++)
    {
        p=cal(p,tmp[i]) ;
        if(!p.x || !p.y) continue ;
        while(j<i)
        {
            P np2=cal(p2,tmp[j]) ;
            if(np2.x==p.x || np2.y==p.y) break ;
            p2=np2 ;
            mi=min(mi,p2.x-p2.y) ;
            ma=max(ma,p2.x-p2.y) ;
            j++ ;
        }
        ret=max(ret,ABS(p.x-p.y-mi)) ;
        ret=max(ret,ABS(p.x-p.y-ma)) ;
    }
    return ret ;
}
 
char s[maxn] ;
main()
{
    int n ; scanf("%d%s",&n,s+1) ;
    for(int i=1;i<=n;i++) v[s[i]-'a'].push_back(i) ;
    int ans=0 ;
    for(int i=0;i<26;i++) if(!v[i].empty())
        for(int j=i+1;j<26;j++) if(!v[j].empty())
        ans=max(ans,solve(v[i],v[j])) ;
    printf("%d\n",ans) ;
}