【51nod1056】最长等差数列V2

  • 哈希大法好,怒斩9级算法题
  • 本文为博主原创,未经许可不得转载

正解我也看不懂,只好硬着头皮暴力水了

$n^2$枚举前两项,然后$hash$判断后面的项是否存在即可

注意公差为0的情况要特判就好了

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
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 50010
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
using namespace std;
typedef long long ll;
const int mod=1e7;
int n,ans,maxx,minn,a[MAXN],hash[mod+10];
inline int read(){
int x=0,f=1; char ch=getchar();
while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
void Special_check(){
int ret=1; sort(a+1,a+n+1);
for(int i=1;i<=n;++i){
if(a[i]==a[i-1]) ++ret;
else cmax(ans,ret),ret=1;
}
}
int Hash(int x){
int pos=x%mod; if(!pos) pos=mod;
while(hash[pos]&&hash[pos]!=x) pos=pos%mod+1;
return pos;
}
int find(int x){return hash[Hash(x)]==x;}
int main(){
//freopen(FILE".in","r",stdin);
//freopen(FILE".out","w",stdout);
n=read(); minn=2e9;
for(int i=1;i<=n;++i) a[i]=read();
for(int i=1;i<=n;++i){
cmax(maxx,a[i]);
cmin(minn,a[i]);
}
Special_check();//特判公差为0的情况
for(int i=1;i<=n;++i) hash[Hash(a[i])]=a[i];
for(int i=1;i<=n;++i)for(int j=i+1;j<=n;++j){
int D=a[j]-a[i],cur=2,ret=a[j];
if((ll)a[i]+(ll)ans*D>maxx) continue;
while(find(ret+D)) ++cur,ret+=D;
cmax(ans,cur);
}
if(ans<200) puts("No Solution");
else printf("%d\n",ans);
//printf("%d\n",clock());
return 0;
}
文章目录
,