JOIOJI

最好想的就是维护三个前缀和JOI的然后使得J[r]-J[l]==O[r]-O[l]==I[r]-I[l],显然r可以一步一步1->n但是l是一个问题直接枚举会超时怎么办????

骚气解法

维护一个pair的map,为什么用pair因为省事不用重载小于号你用node也可以那样要重载小于号,实际上也是殊途同归.然后我们就维护一下任意两个的差啥叫任意也就是(x-y,y-z)(x-z,z-y)随便任意两个但是要保证这个格式.然后设置(0,0)为0.这是什么格式?首先我们模拟肯定能验证他的正确性,然后我们可以发现如果我后续的二元组跟前面的有相同的,那么我们可以断定一个事.比如我现在用的是(x-y,y-z)的格式,那么我现在的xr-yr,yr-zr与前面的xl-yl,yl-zl相等了也就说明二元组内每个元素都相等就是说明xr-yr=xl-yl ==> xr-xl=yr-yl右边同理不就是我们要找的东西吗.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
char s[200005];
map<pair<int,int>,int> bk;
int _j,_o,_i,ans;
int main()
{
int n;
scanf("%d%s",&n,s+1);
bk[make_pair(0,0)]=0;
for(int i=1;i<=n;i++)
{
if(s[i]=='J')
_j++;
else if(s[i]=='O')
_o++;
else
_i++;
int x=_j-_o,y=_o-_i;
if(!bk[make_pair(x,y)]&&(x!=0||y!=0))
bk[make_pair(x,y)]=i;
else
ans=max(ans,i-bk[make_pair(x,y)]);
}
printf("%d",ans);
}
就算是一分钱,也是对作者极大的支持
------ 本文结束 ------

版权声明

Baccano by baccano is licensed under a Creative Commons BY-NC-ND 4.0 International License.
baccano创作并维护的Baccano博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证
本文首发于baccano 博客( http://baccano.fun ),版权所有,侵权必究。

小游戏

---小游戏:要不要来选择一下自己可能的老婆?---

简易发声器

---简易的七键钢琴插件---

可以使用鼠标点击琴键也可以使用主键盘1-7或者小键盘的1-7来操作

那么现在开始吧

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
0%