题目大意

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判。 随机个一定次数即可。 也可以枚举首项，那么可以加玄学优化就是可行性优化。

代码

#include <bits/stdc++.h> #define N 5000010 #define ll long long #define MOD 10000000 using namespace std; struct dong { int x,wz; } b[N]; int a[N],ha[N * 2]; int l,r; int k; int n,m; int d,ca; int ans; int mx,mi,num; ll t; bool cmp(dong a,dong b) { return a.x < b.x || a.x == b.x && a.wz < b.wz; } int hash(int x) { int k = x % MOD; if (!k) k = MOD; while (ha[k] != 0 && ha[k] != x) k = k % MOD + 1; return k; } int find(int x) { if (ha[hash(x)] == x) return 1; else return 0; } int main() { scanf("%d",&n); mi = 1e9; for (int i = 1; i <= n; i++) scanf("%d",&a[i]), mx = max(mx,a[i]), mi = min(mi,a[i]); sort(a+1,a+n+1); a[0]=a[1]-1; l=0; for (int i = 1; i <= n; i++) { if (a[i] == a[i-1]) l++; else { num = max(num,l); l = 1; } } ans = 199; num = max(num,l); if (num > ans) ans=num; for (int i = 1; i <= n; i++) ha[hash(a[i])] = a[i]; for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) { d = a[j]-a[i]; t = (ll)a[i] + (ll)d * ans; if (t < mi || t > mx) continue; k = a[j]; l = 2; while (1) { if (!find(k + d)) break; l++; k += d; } if (l > ans) ans = l; num = max(num,l); } if (ans < 200) printf("No Solution\n"); else printf("%d\n",ans); }