首页 > 代码库 > 51nod1056 最长等差数列 V2

51nod1056 最长等差数列 V2

2024-10-10 22:56:02   211人阅读

 

基准时间限制：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示例
1013568910121314
Output示例
No Solution

 

随机化 hash 脑洞题

当N增长到5万，V1版本的双指针也怼不过去了。

然而既然题被出到OJ上，就一定有做它的方法（那可不一定.jpg）。

注意到只有ans>=200时才算有解，这说明如果有解，那么解对应的那些数分布是比较密集的（口胡）。

我们可以试着随机枚举两项，算出它们的公差，再分别向前向后找数，看能不能把等差数列续得更长。如果扫描每个数，留给随机化的时间就太少了，我们可以把数存进hash表里，这样就可以O(1)查询数是否存在，跑得飞快。

那么需要随机化多少次呢？本着不卡OJ白不卡的学术精神，我们从小到大倍增尝试。

随机1000次就能过第一个点

随机10000次能过两个点

随机100000次能过四个点

随机800000次能过八个点

随机8000000次能过一半点

随机16000000次只错三个点

随机32000000次就AC辣！

可喜可贺，可喜可贺

 1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 using namespace std; 7 const int mxn=100007; 8 int read(){ 9     int x=0,f=1;char ch=getchar();10     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}11     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}12     return x*f;13 }14 struct hstb{15     int v,nxt;16 }e[mxn];17 int hd[mxn],mct=0;18 void insert(int x){19     int u=x%mxn;20     for(int i=hd[u];i;i=e[i].nxt){21         if(e[i].v==x)return;22     }23     e[++mct].v=x;e[mct].nxt=hd[u];hd[u]=mct;24     return;25 }26 int find(int x){27     int u=x%mxn;28     for(int i=hd[u];i;i=e[i].nxt){29         if(e[i].v==x)return 1;30     }31     return 0;32 }33 int n,a[mxn],b[mxn];34 int ans=0;35 int main(){36     int i,j;37     srand(19260817);38     n=read();39     for(i=1;i<=n;i++)a[i]=read(),b[i]=a[i];;40     sort(a+1,a+n+1);41     for(int i=1,cnt=0;i<=n;i++){42         if(a[i]==a[i-1])cnt++;43         else cnt=1;44         ans=max(ans,cnt);45     }46     for(i=1;i<=n;i++) insert(a[i]);47     random_shuffle(b+1,b+n+1);48     int T=32000000;49     while(T--){50         int x=rand()%(n-1)+1,y=rand()%(n-1)+1;51         x=b[x];y=b[y];if(x>y)swap(x,y);52         if(x==y)continue;53         int tmp=y-x;54         int res=2;55         for(i=y+tmp;i<=a[n];i+=tmp){56             if(find(i)){57                 res++;58             }59             else break;60         }61         for(i=x-tmp;i>=a[1];i-=tmp){62             if(find(i)){63                 res++;64             }65             else break;66         }67         ans=max(ans,res);68     }69     if(ans>=200)printf("%d\n",ans);70     else printf("No Solution\n");71     return 0;72 }

 

51nod1056 最长等差数列 V2


联系
我们