JOIOJI

(joioji.c/.cpp/.pas)

【问题描述】

JOIOJIさん是JOI君的叔叔。“JOIOJI”这个名字是由“J、O、I”三个字母各两个构成的。
最近，JOIOJIさん有了一个孩子。JOIOJIさん想让自己孩子的名字和自己一样由“J、O、I”三个字母构成，并且想让“J、O、I”三个字母的出现次数恰好相同。
JOIOJIさん家有一份祖传的卷轴，上面写着一首长诗，长度为n，由“J、O、I”三个字母组成。JOIOJIさん想用诗中最长的满足要求的连续子串作为孩子的名字。
现在JOIOJIさん将这首长诗交给了你，请你求出诗中最长的、包含同样数目的“J、O、I”三个字母的连续子串。
(P.S. JOIOJIさん=JOI欧吉桑=JOI叔叔)

【输入】

输入文件名为(joioji.in)。
第一行一个正整数n，代表这首长诗的长度
接下来一行一个长度为n的字符串S，表示这首长诗，保证每个字符都是“J、O、I”三个字母中的一个

【输出】

输出文件名为(joioji.out)。
输出一行一个正整数，代表最长的包含等数量“J、O、I”三个字母的最长连续子串的长度。如果不存在这样的子串，输出0
joioji.in joioji.out
10
JOIIJOJOOI 6

样例解释

选择“IIJOJO”这个子串，长度为6，包含“J、O、I”三个字母各2个，这是最长的满足要求的子串。

数据范围与约定

对于30%的数据，n<=200
对于60%的数据，n<=4000
对于100%的数据，n<=2*10^5

---

这道题，挺有意思。
叙述很简单，就是找最长的子段，要求’J’,’O’,’I’,出现的次数相同。
首先说一下我的算法：
很容易想到的想法就是把J,O,I，分别附上一些数值，比如令J=5，O=11，I=13；那么J+O+I=29，如果任意一个区间段的和（S），S%29==0，那么可以近似认为在这一段中，是由若干个(JOI)组成的，也就满足了J=O=I，
如：JOOIJI，可以看做JOIJOI；
那么现在的问题是找到这样好的数字，让出现错误的可能最小；
经过了大量反复的尝试之后，发现了这样的一些TIPS：
1.尽可能选择素数，因为他们凑出S的倍数可能性最小；
2.J,O,I的差尽可能大，原因同上；
3.S尽可能大；
4.不需要用O（n2）处理，用一个hash表即可实现O(n);
随机数据，对能否Ac不付任何责任
Code:

#include<stdio.h>
#include<string.h>
typedef long long ll;
#define  MAXN 210000
char str[MAXN];
ll a[MAXN],s[MAXN],hash[2999923];
ll max(ll a,ll b)
{return a>b?a:b;
}
int main()
{freopen("joioji.in","r",stdin);freopen("joioji.out","w",stdout);ll n;scanf("%lld",&n);scanf("%s",str);for(ll i=0;i<n;i++){if(str[i]=='J'){a[i+1]=5;}if(str[i]=='O'){a[i+1]=1313131;}if(str[i]=='I'){a[i+1]=1313;}}for(ll i=1;i<=n;i++){s[i]=s[i-1]+a[i];s[i]%=1314449;}ll length=0;for(ll i=1;i<=n;i++){if(hash[s[i]]==0){hash[s[i]]=i;}else {length=max(length,i-hash[s[i]]);}}/*for(ll i=1;i<=n;i++){for(ll j=n;j>=i+1;j--){if((s[j]-s[i-1])%599927==0){length=max(length,j-i+1);break;}} }*/printf("%lld\n",length);return 0;
}

---

正解是用STL中的map；
用j_num[]，o_num[],i_num[],分别表示到第i位为止，JOI，分别出现的次数。
再开两个数组d1[],d2[];
设j_num[x]-o_num[x]=d1[x];
o_num[x]-i_num[x]=d2[x];
那么如果d1[x]=d2[x]，就满足题意了。
先开一个pair< int,int >
用map< pr,int >mp;表示：

所以流程应该是，先从头找一遍，如果位置找过了，那么记录一下长度，找最大就是Ans；
Code2：

#include<stdio.h>
#include<string.h>
#include<map>
#include<algorithm>
#define MAXN 202001
#define pr pair<int,int>
using namespace std;
map<pr,int>mp;
int n;
int j_num[MAXN],o_num[MAXN],i_num[MAXN],d1[MAXN],d2[MAXN];
char s[MAXN];
int max(int a,int b){return a>b?a:b;}
int main()
{freopen("joioji.in","r",stdin);freopen("joioji.out","w",stdout);scanf("%d",&n);scanf("%s",s);for(int i=0;i<n;i++){if(s[i]=='J'){j_num[i+1]++;}if(s[i]=='O'){o_num[i+1]++;}if(s[i]=='I'){i_num[i+1]++;}j_num[i+1]+=j_num[i],o_num[i+1]+=o_num[i],i_num[i+1]+=i_num[i];d1[i+1]=j_num[i+1]-o_num[i+1];d2[i+1]=o_num[i+1]-i_num[i+1];}int ans=0;for(int i=1;i<=n;i++){if(mp[pr(d1[i],d2[i])]){int k=mp[pr(d1[i],d2[i])];ans=max(ans,i-k);}else{mp[pr(d1[i],d2[i])]=i;}}printf("%d\n",ans);return 0;
}