U368054题解

题意概述：有一个

n

个数和一个

m

个数的序列

a_i

，

b_i

，询问存不存在

a_i \times b_j=k

，

n，m \le 5 \times 10^5

。

针对

50\%

的数据：

n \le 3000,m \le 3000

。

暴力（

50pts

）：

一看到

n \le 3000

和

m \le 3000

，想到

O(nm)

的暴力算法，枚举每个

i

和

j

，判断

a_i \times b_j

是否等于

k

。

正解（

100pts

）：

看到

n \le 5 \times 10^5

和

m \le 5 \times 10^5

，想到

O(n \log m)

的算法。枚举对象太多超时了怎么办？减少枚举对象。只枚举

i

，询问

\dfrac{k}{a_i}

是否存在在

b

序列中。这个可以用 set 处理，时间复杂度是

O(\log m)

的。

当然，你也可以使用 map，时间复杂度也是

O(n \log m)

。

目前暂时没数据，预计 8/10 就有了。

Code（不要抄代码）：

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=500009;
set<int> s;
int a[N],b[N];
int main() {
	int n,m,k;
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=m;i++)
		cin>>b[i],s.insert(b[i]);
	for(int i=1;i<=n;i++) {
		if(k%a[i]!=0) continue;
		int x=k/a[i];
		if(s.find(x)!=s.end()) {
			cout<<i<<" "<<*s.find(x);
			return 0;
		}
	}
	cout<<-1<<endl;
	return 0;
}

时间复杂度

O(n \log m)

，足够通过本题。

文章操作

相关推荐

评论

U368054题解