BZOJ 4236 "JOIOJI"（前缀和+map+pair）

传送门：

　　[1]:BZOJ

　　[2]:洛谷

•题解

　　定义数组 a,b,c 分别表示 'J' , 'O' , 'I' 的前缀和；

　　要想使区间 (L,R] 满足条件当且仅当 a[R]-a[L] = b[R]-b[L] = c[R]-c[L];

　　那么，由 a[R]-a[L] = b[R]-b[L] ⇔ a[R]-b[R] = a[L]-b[L];

　　同理，由 b[R]-b[L] = c[R]-c[L] ⇔ b[R]-c[R] = b[L]-c[L];

　　提前预处理出 a,b,c 数组后；

　　对于 i 位置，查找之前是否含有满足 a_i-b_i = a_j-b_j && b_i-c_i = b_j-c_j 的位置 j，并且 j 尽可能的小；

　　如何高效的查找呢？

　　使用 map<pair<int ,int > , int >；

　　对于之前处理过的位置 j ，将 a_j-b_j 和 b_j-c_j 存入到 pair<int ,int > 中，每次查找是否存在 (a_i-b_i,b_i-c_i) 即可；

　　如果存在，求解当前答案，反之，将其加入到map中；

•Code

 #include<bits/stdc++.h>

 using namespace std;

 #define pii pair<int ,int >

 const int maxn=2e5+;

 int n;

 char s[maxn];

 int a[maxn];

 int b[maxn];

 int c[maxn];

 map<pii ,int >f;

 int Solve()

 {

     f.clear();

     f[pii(,)]=;///将(0,0)加入到f中

     a[]=b[]=c[]=;

     int len=strlen(s+);

     for(int i=;i <= len;++i)

     {

         a[i]=a[i-]+(s[i] == 'J');

         b[i]=b[i-]+(s[i] == 'O');

         c[i]=c[i-]+(s[i] == 'I');

     }

     int ans=;

     for(int i=;i <= len;++i)

     {

         pii tmp=pii(a[i]-b[i],b[i]-c[i]);

         if(f.count(tmp))

             ans=max(ans,i-f[tmp]);

         else

             f[tmp]=i;

     }

     return ans;

 }

 int main()

 {

     scanf("%d",&n);

     scanf("%s",s+);

     printf("%d\n",Solve());

     return ;

 }

巴特西

BZOJ 4236 "JOIOJI"（前缀和+map+pair）

•题解

•Code

最新文章

热门文章