ACM程序设计选修课——1043: Radical loves integer sequences（YY）

1043: Radical loves integer sequences

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 36 Solved: 4
[ Submit][ Status][ Web Board]

Description

One day Radical got hold of an integer sequence a1, a2, ..., an of length n. He decided to analyze the sequence. For that, he needs to find all values of x, for which these conditions hold:

x occurs in sequence a.

Consider all positions of numbers x in the sequence a (such i, that ai = x). These numbers, sorted in the increasing order, must form an arithmetic progression.

Help Radical, find all x that meet the problem conditions.

Input

The first line contains integer n (1 ≤ n ≤ 105). The next line contains integers a1, a2, ..., an (1 ≤ ai ≤ 105). The numbers are separated by spaces.

Output

In the first line print integer t — the number of valid x. On each of the next t lines print two integers x and px, where x is current suitable value, px is the common difference between numbers in the progression (if x occurs exactly once in the sequence, px must equal 0).

Print the pairs in the order of increasing x.

Sample Input

Sample Output

这题前几次看真心没看懂，今天下午看了一下，发现是判断同一个数字出现的下标是否是等差数列，是则输出公差，否则则不输出。

没什么算法，就是记录时判断麻烦点..

代码：

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<string>
#include<deque>
#include<cmath>
#include<queue>
#include<set>
#include<map>
bool ok[100009];
int mop[100009];
int step[100009];
int pos[100009];
using namespace std;
int main (void)
{
	int t,i,j,n,tstep,cnt;
	while (~scanf("%d",&n))
	{
		memset(ok,0,sizeof(ok));//判断改数是否存在等差数列
		memset(mop,0,sizeof(mop));//记录该数的出现次数
		memset(step,0,sizeof(step));//记录该数的公差
		memset(pos,0,sizeof(pos));//记录该数的每（前）一次出现的下标pos
		tstep=0;
		cnt=0;
		for (i=1; i<=n; i++)
		{
			scanf("%d",&t);
			mop[t]++;
			if(mop[t]>=1)//若出现过
			{				
				if(mop[t]==1)//若此时只有一次
				{
					ok[t]=1;//暂时可行
					cnt++;//暂时可行数+1
					pos[t]=i;//此时为第一次出现的位置
					step[t]=0;//此时公差为0
				}
				else if(mop[t]==2)//两次
				{					
					step[t]=i-pos[t];//公差Δd
					pos[t]=i;//位置更变
					ok[t]=1;//暂时可行
				}
				else//三次以上
				{					
					tstep=i-pos[t];//临时公差
					if(tstep!=step[t])//若不等于此前的公差，则
					{
						if(ok[t])//若此前没有被减掉
							cnt--;//减掉该数
						ok[t]=0;//变为不可行						
					}
					pos[t]=i;//位置变更	
				}
			}
		}
		printf("%d\n",cnt);
		for (i=1; i<=100000; i++)
		{
			if(ok[i])
			{
				if(mop[i]==1)
				{
					printf("%d %d\n",i,0);
				}
				else
				{
					printf("%d %d\n",i,step[i]);
				}
			}
		}
	}	
	return 0;
}

秒客网