Codeforces-352B

328 阅读 0 评论 217 点赞

我是靠谱客的博主怡然草莓，这篇文章主要介绍Codeforces-352B，现在分享给大家，希望可以做个参考。

题意：

在给定的序列中，有重复出现的数字x，所在的序列中的位置i构成一个等差数列，如果x只出现一次，px=0，px代表公差。

输出符合要求的x和公差，并且x是递增的。

此题，就是用数组标记。保存第一个数x出现的位置和公差d。根据an=a1+(n-1)d,进行判断就行了。

复制代码

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
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std ;

const int N=100005;
int cnt[N],fd[N],d[N];
bool flag[N];

int main()
{
	int n,a,ans,M;
    while(scanf("%d",&n)!=EOF){
		M=ans=0;
		memset(flag,1,sizeof(flag));
		memset(cnt,0,sizeof(cnt));
		memset(d,0,sizeof(d));
		for(int i=1;i<=n;i++){
			scanf("%d",&a);
			++cnt[a];
			if(flag[a]==0) continue;
			if(cnt[a]==1) fd[a]=i;		
			else if(cnt[a]==2) d[a]=i-fd[a];		
			else flag[a]=((fd[a]+(cnt[a]-1)*d[a])==i);
			M=max(a,M);				
		}
		for(int i=1;i<=M;i++){
			if(cnt[i]&&flag[i]) ans++;
		}
		printf("%dn",ans);
		for(int i=1;i<=M;i++){
			if(cnt[i]&&flag[i]) printf("%d %dn",i,d[i]);
		}
    }
 	return 0 ;
}