[codeforces 1324B] Yet Another Palindrome Problem 回文+边界处理

139 阅读 0 评论 92 点赞

我是靠谱客的博主俊秀火龙果，这篇文章主要介绍[codeforces 1324B] Yet Another Palindrome Problem 回文+边界处理，现在分享给大家，希望可以做个参考。

Codeforces Round #627 (Div. 3) 比赛人数6434

[codeforces 1324B] Yet Another Palindrome Problem 回文+边界处理

总目录详见https://blog.csdn.net/mrcrack/article/details/103564004

也在线测评地址http://codeforces.com/contest/1324/problem/B

Problem	Lang	Verdict	Time	Memory
B - Yet Another Palindrome Problem	GNU C++11	Accepted	31 ms	0 KB

回文，经常处理这样的数据，因此，处理该题很有信心。

手工模拟样例，发现只要找到3个数，脚标满足i<j<k,数值满足ai==ak，即为满足条件。

程序处理如下：

构造结构体，记录数组的读入序列，读入数值，对数值进行自小到大排序，只要相等的数据之间能找到序列差大于1即可。

具体可看代码。

自认为编得比较好的地方，是对边界的处理，有意识的设置了结构体的0位置，n+1位置的数据。

复制代码

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
#include <cstdio>
#include <algorithm>
using namespace std;
struct node{
int seq,v;
}a[5010];
int cmp(node a,node b){
return a.v==b.v?a.seq<b.seq:a.v<b.v;
}
int main(){
int t,n,i,flag,pre;//pre记录相同v的起始位置seq
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i].v),a[i].seq=i;
sort(a+1,a+1+n,cmp);
a[0].v=a[n+1].v=-1,a[0].seq=0,a[n+1].seq=n+1,flag=0,pre=0;//边界处理
for(i=1;i<=n+1;i++)
if(a[i].v!=a[i-1].v){//pre到i之间的数值v相同
if(a[i-1].seq-a[pre].seq>1){
flag=1;
break;
}
pre=i;
}
if(flag)printf("YESn");
else printf("NOn");
}
return 0;
}