A simple Blog for wyx I've been down the bottle hoping.
BZOJ 4236: $JOIOJI$
发表于: | 分类: Oi | 评论:0 | 阅读:155

$J[i]-J[k-1] = O[i] - O[k-1]$
$J[i] - O[i] = J[k-1] - O[k-1]$
$O,I$同理
我们把$J[i]-O[i]$扔到一个$map$里存一下左端点,遇到相同的就更新答案就行了
注意0,0的初始化
时间复杂度$O(nlog(n))$
当然我们也可以$HASH$
给每一位一个权值,权值的和为一个素数
然后每次$mod$一下,在对应结果处记录一下左端点就行了

#include <map>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define N 200000+5
using namespace std;

map <pair<int,int>,int> mp;
int A,B,C;
char str[N];

int main()
{
    int n; cin >> n;
    scanf("%s",str+1);
    int ans = 0;
    mp[make_pair(0,0)] = 0;
    for(int i=1;i<=n;++i)
    {
        if(str[i] == 'J') ++ A;
        else if(str[i] == 'O') ++ B;
        else ++C;
        if(mp.find(make_pair(A-B,B-C)) == mp.end())
            mp[make_pair(A-B,B-C)] = i;
        else
            ans = max(ans,i-mp[make_pair(A-B,B-C)]);
    }
    printf("%d\n",ans);
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP