ACM程序设计选修课——1043:Radicallovesintegersequences（YY）

作者：男孩花朵 | 来源：互联网 | 2023-08-16 08:33

1043:RadicallovesintegersequencesTimeLimit:1SecMemoryLimit:128MBSubmit:36

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
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
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;
}

推荐阅读

ide
CSS3选择器的使用方法详解，提高Web开发效率和精准度

本文详细介绍了CSS3新增的选择器方法，包括属性选择器的使用。通过CSS3选择器，可以提高Web开发的效率和精准度，使得查找元素更加方便和快捷。同时，本文还对属性选择器的各种用法进行了详细解释，并给出了相应的代码示例。通过学习本文，读者可以更好地掌握CSS3选择器的使用方法，提升自己的Web开发能力。 ... [详细]

蜡笔小新 2023-12-14 14:37:52
ide
如何使用PHP向系统日历中添加事件？

本文介绍了如何使用PHP向系统日历中添加事件的方法，通过使用PHP技术可以实现自动添加事件的功能，从而实现全局通知系统和迅速记录工具的自动化。同时还提到了系统exchange自带的日历具有同步感的特点，以及使用web技术实现自动添加事件的优势。 ... [详细]

蜡笔小新 2023-12-14 21:02:28
bit
微软头条实习生分享深度学习自学指南

本文介绍了一位微软头条实习生自学深度学习的经验分享，包括学习资源推荐、重要基础知识的学习要点等。作者强调了学好Python和数学基础的重要性，并提供了一些建议。 ... [详细]

蜡笔小新 2023-12-14 20:58:32
js
【机器学习】生成式对抗网络模型综述

生成式对抗网络模型综述摘要生成式对抗网络模型(GAN)是基于深度学习的一种强大的生成模型，可以应用于计算机视觉、自然语言处理、半监督学习等重要领域。生成式对抗网络 ... [详细]

蜡笔小新 2023-12-14 17:51:18
import
Linux重启网络命令实例及关机和重启示例教程

本文介绍了Linux系统中重启网络命令的实例，以及使用不同方式关机和重启系统的示例教程。包括使用图形界面和控制台访问系统的方法，以及使用shutdown命令进行系统关机和重启的句法和用法。 ... [详细]

蜡笔小新 2023-12-14 15:52:52
import
在Windows 8上安装gvim中的插件的错误加载问题

本文讨论了在Windows 8上安装gvim中插件时出现的错误加载问题。作者将EasyMotion插件放在了正确的位置，但加载时却出现了错误。作者提供了下载链接和之前放置插件的位置，并列出了出现的错误信息。 ... [详细]

蜡笔小新 2023-12-14 14:44:00
input
[线段树|平衡树|树状数组]LightOJ - 1087 - Diablo

1087-DiabloPDF(English)StatisticsForum ... [详细]

蜡笔小新 2023-10-10 09:22:06
input
Nginx使用AWStats日志分析的步骤及注意事项

本文介绍了在Centos7操作系统上使用Nginx和AWStats进行日志分析的步骤和注意事项。通过AWStats可以统计网站的访问量、IP地址、操作系统、浏览器等信息，并提供精确到每月、每日、每小时的数据。在部署AWStats之前需要确认服务器上已经安装了Perl环境，并进行DNS解析。 ... [详细]

蜡笔小新 2023-12-14 19:42:01
object
在类中定义数组时出错 - Error on defining arrays in class

Iamtryingtomakeaclassthatwillreadatextfileofnamesintoanarray,thenreturnthatarra ... [详细]

蜡笔小新 2023-12-14 17:38:12
object
VScode格式化文档换行或不换行的设置方法

本文介绍了在VScode中设置格式化文档换行或不换行的方法，包括使用插件和修改settings.json文件的内容。详细步骤为：找到settings.json文件，将其中的代码替换为指定的代码。 ... [详细]

蜡笔小新 2023-12-14 17:15:38
object
IB 物理真题解析：比潜热、理想气体的应用

本文是对2017年IB物理试卷paper 2中一道涉及比潜热、理想气体和功率的大题进行解析。题目涉及液氧蒸发成氧气的过程，讲解了液氧和氧气分子的结构以及蒸发后分子之间的作用力变化。同时，文章也给出了解题技巧，建议根据得分点的数量来合理分配答题时间。最后，文章提供了答案解析，标注了每个得分点的位置。 ... [详细]

蜡笔小新 2023-12-14 15:00:29
object
如何使用Java获取服务器硬件信息和磁盘负载率

本文介绍了使用Java编程语言获取服务器硬件信息和磁盘负载率的方法。首先在远程服务器上搭建一个支持服务端语言的HTTP服务，并获取服务器的磁盘信息，并将结果输出。然后在本地使用JS编写一个AJAX脚本，远程请求服务端的程序，得到结果并展示给用户。其中还介绍了如何提取硬盘序列号的方法。 ... [详细]

蜡笔小新 2023-12-14 13:56:20
object
[译]技术公司十年经验的职场生涯回顾

本文是一位在技术公司工作十年的职场人士对自己职业生涯的总结回顾。她的职业规划与众不同，令人深思又有趣。其中涉及到的内容有机器学习、创新创业以及引用了女性主义者在TED演讲中的部分讲义。文章表达了对职业生涯的愿望和希望，认为人类有能力不断改善自己。 ... [详细]

蜡笔小新 2023-12-14 11:31:05
object
推荐系统遇上深度学习(十七）详解推荐系统中的常用评测指标

原创：石晓文小小挖掘机2018-06-18笔者是一个痴迷于挖掘数据中的价值的学习人，希望在平日的工作学习中，挖掘数据的价值， ... [详细]

蜡笔小新 2023-12-13 19:35:25
object
v8学习笔记(四) 对象机制

v8对象机制1.概述v8中每一个API对象都对应一个内部实现对象(堆对象)2.对象创建过程(1)v8::internal::Factory类: ... [详细]

蜡笔小新 2023-10-16 20:07:54

男孩花朵

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章