上午小测1 B.序列哈希表+数学

2020 年 10 月 29 日
筆記
哈希表, 数论

题目描述

\(EZ\) 每周一都要举行升旗仪式，国旗班会站成一整列整齐地向前行进。

郭神摄像师想要选取其中一段照下来。他想让这一段中每个人的身高成等比数列，展示出最萌身高差。但他发现这个太难办到了。于是他决定放低要求，让等比数列的每两项之间可以是不连续的（例如：\(2\), \(4\), \(16\), …）。可他依然找不到满意的，便再次妥协，使这个等比数列可以是乱序的。

现在请你在其中找出最长的符合要求的一段，使得将这一段排序后为某个公比为 \(q\) 的等比数列的子序列\((q∈N*, q ≤ 1000)\)。

输入格式

第一行一个正整数\(N\)，表示有 \(n\)个人。

接下来 \(n\)行每行一个正整数\(a_1,a_2,…a_n,\) 依次表示\(n\)个人的身高。

输出格式

一行一个整数 \(ans\)，表示最长的符合要求的连续一段

样例

样例输入 1

7
2
4
6
6
1
36
3

样例输出 1

3

样例输入 2

10
1
2
3
4
5
6
7
8
9
10

样例输出 2

2

数据范围与提示

对于 \(20\%\)的数据，\(n \leq 100\)
对于 \(40\%\)的数据，\(n \leq 1000\)
对于另外 \(20\%\) 的数据，\(a_i \leq 100\)
对于 \(100\%\)的数据， \(n \leq 10^5,a_i \leq 10^{18}\)

分析

对于一个序列来说，如果它在排序之后能够形成一个等比数列
那么必须要满足序列中任意两数作除法得到的商是最小公比的整数次幂
我们要考虑的就是如何求出最小公比
因为公比最多为 \(1000\)，所以我们可以把 \(2\) 到 \(1000\) 的整数次幂扔到一个哈希表里
每次在哈希表里查询当前数对应的值是多少
注意要特判公比为 \(1\) 的情况

代码

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<set>
#define rg register
typedef long long ll;
inline ll read(){
	rg ll x=0,fh=1;
	rg char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1LL)+(x<<3LL)+(ch^48LL);
		ch=getchar();
	}
	return x*fh;
}
const int maxn=1e5+5;
const int mod=1e5+3;
const ll INF=1000000000000000000LL;
ll a[maxn],mmax,mmin;
int ans=1,h[maxn],tot=1,n;
struct hash{
	int num,nxt;
	ll val;
}b[maxn<<4];
inline void ad(int num,ll val){
	rg int now=1LL*val%mod;
	for(rg int i=h[now];i!=-1;i=b[i].nxt){
		if(b[i].val==val) return;
	}
	b[tot].val=val;
	b[tot].num=num;
	b[tot].nxt=h[now];
	h[now]=tot++;
}
inline int cx(ll val){
	rg int now=1LL*val%mod;
	for(rg int i=h[now];i!=-1;i=b[i].nxt){
		if(b[i].val==val) return b[i].num;
	}
	return 233;
}
std::set<ll> s;
int main(){
	memset(h,-1,sizeof(h));
	n=read();
	ll lat=0;
	int cnt=0;
	for(rg int i=1;i<=n;i++){
		a[i]=read();
		if(a[i]==lat){
			cnt++;
		} else {
			lat=a[i];
			cnt=1;
		}
		ans=std::max(ans,cnt);
	}
	for(rg int i=2;i<=1000;i++){
		lat=INF/i;
		for(rg ll j=i;j<=lat;j*=i){
			ad(i,j);
		}
	}
	for(rg int l=1;l<n;l++){
		s.clear();
		s.insert(a[l]);
		mmax=std::max(a[l],a[l+1]);
		mmin=std::min(a[l],a[l+1]);
		if(mmin==mmax || mmax%mmin) continue;
		s.insert(a[l+1]);
		rg int gys=cx(mmax/mmin);
		ans=std::max(ans,2);
		for(rg int r=l+2;r<=n;r++){
			if(s.find(a[r])!=s.end()) break;
			s.insert(a[r]);
			mmax=std::max(a[r],a[r-1]);
			mmin=std::min(a[r],a[r-1]);
			if(mmax%mmin) break;
			if(cx(mmax/mmin)!=gys) break;
			ans=std::max(ans,r-l+1);
		}
	}
	printf("%d\n",ans);
	return 0;
}

Tags: 哈希表数论