基准时间限制：8 秒 空间限制：131072 KB 分值: 1280
N个不同的正整数，从中选出一些数组成等差数列。
例如：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
随机化 hash 脑洞题
当N增长到5万，V1版本的双指针也怼不过去了。
然而既然题被出到OJ上，就一定有做它的方法（那可不一定.jpg）。
注意到只有ans>=200时才算有解，这说明如果有解，那么解对应的那些数分布是比较密集的（口胡）。
我们可以试着随机枚举两项，算出它们的公差，再分别向前向后找数，看能不能把等差数列续得更长。如果扫描每个数，留给随机化的时间就太少了，我们可以把数存进hash表里，这样就可以O(1)查询数是否存在，跑得飞快。
那么需要随机化多少次呢？本着不卡OJ白不卡的学术精神，我们从小到大倍增尝试。
随机1000次就能过第一个点
随机10000次能过两个点
随机100000次能过四个点
随机800000次能过八个点
随机8000000次能过一半点
随机16000000次只错三个点
随机32000000次就AC辣！
可喜可贺，可喜可贺
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
struct hstb{
int v,nxt;
}e[mxn];
int hd[mxn],mct=;
void insert(int x){
int u=x%mxn;
for(int i=hd[u];i;i=e[i].nxt){
if(e[i].v==x)return;
}
e[++mct].v=x;e[mct].nxt=hd[u];hd[u]=mct;
return;
}
int find(int x){
int u=x%mxn;
for(int i=hd[u];i;i=e[i].nxt){
if(e[i].v==x)return ;
}
return ;
}
int n,a[mxn],b[mxn];
int ans=;
int main(){
int i,j;
srand();
n=read();
for(i=;i<=n;i++)a[i]=read(),b[i]=a[i];;
sort(a+,a+n+);
for(int i=,cnt=;i<=n;i++){
if(a[i]==a[i-])cnt++;
else cnt=;
ans=max(ans,cnt);
}
for(i=;i<=n;i++) insert(a[i]);
random_shuffle(b+,b+n+);
int T=;
while(T--){
int x=rand()%(n-)+,y=rand()%(n-)+;
x=b[x];y=b[y];if(x>y)swap(x,y);
if(x==y)continue;
int tmp=y-x;
int res=;
for(i=y+tmp;i<=a[n];i+=tmp){
if(find(i)){
res++;
}
else break;
}
for(i=x-tmp;i>=a[];i-=tmp){
if(find(i)){
res++;
}
else break;
}
ans=max(ans,res);
}
if(ans>=)printf("%d\n",ans);
else printf("No Solution\n");
return ;
}