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位置的数据。
#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("YES\n");
else printf("NO\n");
}
return 0;
}