【CF1025C】Plasticine zebra

Source and Judge

CF1025C

Record

1h

Analysis

请先思考后再展开

要不是因为比赛的时候被第二题卡,还是能做出来的……
说多都是泪

然后我的做法和机房其他人都不一样
就是从操作的实际意义入手,发现等于没有翻转
例如形如 ab|cd 这样的字符串,得到所谓的ba|dc
但其实本质上,就是把后面那个放到前面,cd|ab,然后再整体倒过来
然后不难发现,整体倒过来没有任何意义
所以每次操作其实就是把后面的一段放到前面去,相当于跑一个环状的东西

所以说,只需要枚举一个起点,然后向后延伸就好了
比赛还剩五分钟的时候,感觉需要平方级别
回去的路上立刻就想到,其实维护一个双指针就好了

总而言之这道题真的很好想
从操作入手,思考本质就是了

Code

请先思考后再展开
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
int mymax(int x,int y) {return x>y?x:y;}
char s[210000];
bool check(int i,int j)
{
return ((j-i)%2==0 and s[i]==s[j]) or ((j-i)%2==1 and s[i]!=s[j]);
}
void main()
{
scanf("%s",s+1);
int n=strlen(s+1);
for(int i=n+1;i<=n+n;i++) s[i]=s[i-n];
int ans=1,r=1;
for(int l=1;l<=n;l++)
{
if(r<l) r=l;
while(r<=l+n-1 and check(l,r)) r++;
r--;
//printf("%d %d\n",l,r);
ans=mymax(ans,r-l+1);
}
printf("%d",ans);
}
};
int main()
{
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/f525.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%