Zq's Blog STL,算法 [STL]bzoj4236: JOIOJI

[STL]bzoj4236: JOIOJI

题目描述

JOIOJI桑是JOI君的叔叔。“JOIOJI”这个名字是由“J、O、I”三个字母各两个构成的。

最近,JOIOJI桑有了一个孩子。JOIOJI桑想让自己孩子的名字和自己一样由“J、O、I”三个字母构成,并且想让“J、O、I”三个字母的出现次数恰好相同。

JOIOJI桑家有一份祖传的卷轴,上面写着一首长诗,长度为N,由“J、O、I”三个字母组成。JOIOJIさん想用诗中最长的满足要求的连续子串作为孩子的名字。

现在JOIOJI桑将这首长诗交给了你,请你求出诗中最长的、包含同样数目的“J、O、I”三个字母的连续子串。

输入

第一行一个正整数N,代表这首长诗的长度

接下来一行一个长度为$N$的字符串$S$,表示这首长诗,保证每个字符都是“J、O、I”三个字母中的一个

输出

输出一行一个正整数,代表最长的包含等数量“J、O、I”三个字母的最长连续子串的长度。如果不存在这样的子串,输出0

样例输入

10
JOIIJOJOOI

样例输出

6

提示

选择“IIJOJO”这个子串,长度为6,包含“J、O、I”三个字母各2个,这是最长的满足要求的子串。
$1<=N<=2*10^5$;

来源

JOI 2013~2014 春季training合宿 竞技3 By PoPoQQQ

题解

STL题$\approx$水题;

要求”J,O,I”三个字母出现的次数相等,即$Sum[R][J]-Sum[L][J]=Sum[R][O]-Sum[L][O]=Sum[R][I]-Sum[L][I]$;

移项得

$Sum[R][J]-Sum[R][O]=Sum[L][J]-Sum[L][O]$

$Sum[R][O]-Sum[R][I]=Sum[L][O]-Sum[L][I]$

开个$map$记一下$Sum[J]-Sum[O],Sum[O]-Sum[I]$,询问的时候找一下位置即可;

#include<map>
#include<cstdio>
#include<algorithm>
#define S(a) (0*(a=='I')+1*(a=='J')+2*(a=='O'))
using namespace std;
int N,Ans,Sum[3];
map<pair<int,int>,int>id;
int main()
{
    scanf("%d",&N);
    id[make_pair(0,0)]=0;
    for (int i=1;i<=N;i++){
        char ch=getchar();
        while (ch!='I'&&ch!='J'&&ch!='O') ch=getchar();
        Sum[S(ch)]++;pair<int,int> S=make_pair(Sum[S('J')]-Sum[S('O')],Sum[S('O')]-Sum[S('I')]);
        if (id.find(S)==id.end()) id[S]=i;else Ans=max(Ans,i-id[S]);
    }
    printf("%d\n",Ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注