首页 > 其他分享 >51 nod 1056 最长等差数列 V2

51 nod 1056 最长等差数列 V2

时间:2022-11-22 19:34:42浏览次数:58  
标签:begin hash 1056 nod 51 longint 集合 end 等差数列


​1056 最长等差数列 V2​


基准时间限制:8 秒 空间限制:131072 KB 分值: 1280  ​​难度:9级算​​法题

例如:1 3 5 6 8 9 10 12 13 14

等差子数列包括(仅包括两项的不列举)

1 3 5

1 5 9 13

3 6 9 12

3 8 13

5 9 13

6 8 10 12 14

其中6 8 10 12 14最长,长度为5。

现在给出N个数,你来从中找出一个长度 >= 200 的等差数列,如果没有,输出No Solution,如果存在多个,输出最长的那个的长度。

Input

第1行:N,N为正整数的数量(1000 <= N <= 50000)。
第2 - N+1行:N个正整数。(2<= A[i] <= 10^9)
(注,真实数据中N >= 1000,输入范例并不符合这个条件,只是一个输入格式的描述)

Output

找出一个长度 >= 200 的等差数列,如果没有,输出No Solution,如果存在多个,输出最长的那个的长度。

Input示例

10
1
3
5
6
8
9
10
12
13
14

Output示例

No Solution


提供一个可能是正解的做法吧(源自本题讨论区),也就是 ​​@李陶冶​​​ 提到的分治做法,来自Jeff Erickson在1999年发表的一篇短论文  ​​​Finding longest arithmetic progressions​​ 。

这个论文的做法基于一个结论:大小为n的集合里长度至少为k的不同等差数列的数量是O(n*n/k*k)的。从这个结论入手可以尝试构造出答案。

首先要明确等差数列的定义。

一个等差数列可以用首项、公差和项数的三元组(first,delta,length)表示,当然这个first也可以换成末项last,取决于你的算法。

我们要考虑的等差数列要尽量用少的信息表示所有的可能,也就是说提取出来的等差数列之间不能有相互包含的关系,例如(2,3,4)和(2,3,5)就冗余了,而(2,3,4)和(5,3,4)也是冗余的,因为当它们出现在同一个序列里时,(2,3,5)也是存在的。

因此我们只需要考虑满足(first-delta)这个数字不存在,并且(last+delta)这个数字不存在的等差数列。

接下来要发现这样的等差数列在k充分大时是不多的。

定义集合里的两个元素是足够相邻的,当且仅当它们的排名之差不超过n/(k-1)。由鸽巢原理可知,一个长度为k的等差数列必然包含至少(k-1)/2对足够相邻的元素(考虑等差数列里排名最小的和排名最大的那两个元素)。

而集合里足够相邻的元素对数不超过n*n/2(k-1),我们所求的不同等差数列也不会包含相同的一对足够相邻的元素,所以我们能得到的等差数列数量是不超过n*n/(k-1)*(k-1)的。
最后要利用这个性质来构造相应的算法。

利用数量不多的性质,我们可以尝试找出所有长度至少为 200 的等差数列,从中选取最长的那个。

注意到上面的证明利用到了集合的大小,类似地也可以证明,这样的等差数列必然有⌊k/2⌋项在前⌊n/2⌋小的元素集合里,或者有⌊k/2⌋项在前⌈n/2⌉大的元素集合里。而集合大小减半同时数列项数减半对数列数量的影响是不大的,所以可以尝试对集合分治,分别找出更小情况的解,然后放到大的集合里尝试向左向右O(k)扩张,再进行去重,从而得到当前情况的解。

T(n,k)=O(n*n/k log n/k)。

实现上可能要注意几个细节:

1. 需要实现原集合的hash来保证扩张的复杂度。

2. 当k=O(log n)时,可以采用O(n*n)的dp直接计算,效率更高,此时递归层数是O(log k)的。

3. k实际上可以动态变化,从而优化常数,本题数据好像不太强,稍微写错点地方也不会出问题。

4. 论文中提到寻找最长等差数列的时候依次选取k=n,n/2,n/4,…,对于本题可以直接选取k=200。

———————————————————————————————————————————————

但因为种种原因,本题可以玄学搜索+各种剪枝用O(n*n)的时间复杂度完成。搜索方法:枚举第一个数,然后枚举公差,用hash判断可行性。

Code:

uses math;
const m=10000000;
var
num,k,i,n,minans,maxans,len,ans,j,d:longint;
a,hash:array[0..10000005] of longint;t:int64;
procedure sort(l,r:longint);
var i,j,x,y:longint;
begin
i:=l;j:=r;x:=a[(l+r) div 2];
repeat
while a[i]<x do inc(i);
while x<a[j] do dec(j);
if not(i>j) then
begin
y:=a[i];a[i]:=a[j];a[j]:=y;
inc(i);dec(j);
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;
function hashhash(x:longint):longint;
var k:longint;
begin
k:=x mod m;
if k=0 then k:=k+m;
while (hash[k]<>0)and(hash[k]<>x) do k:=k mod m+1;
exit(k);
end;
function find(x:longint):boolean;
begin
if hash[hashhash(x)]=x then exit(true);
exit(false);
end;
begin
read(n);
minans:=maxlongint;
for i:=1 to n do
begin
read(a[i]);
if a[i]>maxans then maxans:=a[i];
if a[i]<minans then minans:=a[i];
end;
sort(1,n);
a[0]:=a[1]-1;
for i:=1 to n do hash[hashhash(a[i])]:=a[i];
for i:=1 to n do
for j:=i+1 to n do
begin
d:=a[j]-a[i];
k:=a[j];len:=2;
t:=a[i]+ans*d;
if (t>maxans)or(t<minans) then break;
while find(k+d) do
begin
k:=k+d;
inc(len);
end;
if len>ans then ans:=len;
end;
if ans<200 then writeln('No Solution') else
writeln(ans);
end.

标签:begin,hash,1056,nod,51,longint,集合,end,等差数列
From: https://blog.51cto.com/u_15888102/5878382

相关文章

  • 51 nod 1851 俄罗斯方块
    ​​1851 俄罗斯方块​​基准时间限制:1 秒空间限制:131072 KB分值: 160 ​​难度:6级算法题​​ 给一个黑白图,每次能将某些区域的格......
  • 51 nod 算法马拉松28 先序遍历与后序遍历
     ​​先序遍历与后序遍历​​ ​​​Scape​​​ (命题人)​​​tangjz​​​ (测试)基准时间限制:1 秒空间限制:131072 KB分值: 40对于给定......
  • Keil软件 fail to excute "C://C51//BIN//C51.exe"解决方案
    原因:编译器的路径因修改过而导致的错误解决方法:重新设置编译器的默认路径1、在Project->Components,Environment,Books...  2、Folders/Extensions 修改ToolB......
  • DOM_Node对象与案例4_动态表格_添加
    DOM_Node对象节点可以是元素节点、属性节点、文本节点,或者也可以是"节点类型"那一节中所介绍的任何一种节点。请注意,虽然所有的对象均能继承用于处理父节点和子节点的属性......
  • node 连接MySQL
    使用node创建一个服务端比java简单多,下面创建一个node服务端,连接MySQL并且将数据在浏览器显示出来一.node创建服务端案例varhttp=require("http");http.createSe......
  • nodejs02
    Express快速创建Web服务器express的基本使用先安装express包[email protected].导入expressconstexpress=require('express');2.创建web服务器cons......
  • [ERROR] mariadbd: The table 'INNODB_BUFFER_PAGE' is full
    问题描述:将information_schema导出sql文件到新库中恢复,sql中的表都是临时表,存储引擎都是memory,在导入的过程中实际大量会占用临时表。报错信息:ERROR1114(HY000)atline......
  • 安装指定node版本(适用windows)
    一开始在网上查了很多什么“n版本管理”还有“nvm”,感觉都不如直接覆盖来的痛快第一步:在官网找到自己想要的版本,网址:https://nodejs.org/dist/,下载.msi安装包我下载的......
  • node.js安装及环境配置超详细教程【Windows系统安装包方式】
    文章目录Step1:下载安装包Step2:安装程序Step3:查看Step4:环境配置最后补充:Step1:下载安装包https://nodejs.org/zh-cn/download/根据自己电脑系统及位数选择,我的电......
  • 51nod 1165 整边直角三角形的数量 【数学:公式--求约数】
    1165 整边直角三角形的数量基准时间限制:2 秒空间限制:131072 KB分值: 160 难度:6级算法题 收藏 关注直角三角形,三条边的长度都......