最长等差数列 V2

wjh15101051's space

卧薪尝胆，厚积薄发。

最长等差数列 V2

Date: Sun Aug 26 20:38:05 CST 2018

In Category: NoCategory

Description：

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

$1000\le n \le 50000$

Solution：

枚举第一项和第二项， $while+hash$ 判断能否继续，没了。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXN 50010

typedef long long ll;

ll n;

ll a[MAXN];

#define MOD 23333

struct map

{

	ll h[MOD],nxt[MAXN];

	ll s[MAXN];

	ll tot;

	map(){tot = 0;memset(h,0,sizeof(h));}

	void add(ll k)

	{

		++tot;s[tot] = k;nxt[tot] = h[k % MOD];h[k % MOD] = tot;

		return;

	}

	bool exist(ll k)

	{

		for(ll i = h[k % MOD];i != 0;i = nxt[i])

			if(s[i] == k)return true;

		return false;

	}

};

int main()

{

	map p;

	scanf("%lld",&n);

	for(int i = 1;i <= n;++i)scanf("%lld",&a[i]);

	sort(a + 1,a + 1 + n);

	for(int i = 1;i <= n;++i)p.add(a[i]);

	ll ans = 0;

	ll maxl = 200;

	for(int i = 1;i <= n;++i)

	{

		for(int j = i + 1;j <= n;++j)

		{

			ll d = a[j] - a[i];

			ll cur = a[j];

			ll len = 2;

			if(a[i] + d * (maxl - 1) > a[n])continue;

			while(p.exist(cur + d))

			{

				++len,cur += d;

			}

			ans = max(len,ans);

			maxl = max(maxl,ans);

		}

	}

	if(ans < 200)puts("No Solution");

	else cout << ans << endl;

	return 0;

}

In tag: 哈希

wjh15101051