题解:齿轮

1.题意

地址:https://www.luogu.com.cn/problem/P8799

1.1 题目描述

这天，小明在组装齿轮。

他一共有 $n$ 个齿轮，第 $i$ 个齿轮的半径为 $r_{i}$, 他需要把这 $n$ 个齿轮按一定顺序从左到右组装起来，这样最左边的齿轮转起来之后，可以传递到最右边的齿轮，并且这些齿轮能够起到提升或者降低转速（角速度）的作用。

小明看着这些齿轮，突然有 $Q$ 个疑问: 能否按一定顺序组装这些齿轮使得最右边的齿轮的转速是最左边的齿轮的 $q_{i}$ 倍?

1.2 输入格式

输入共 $Q+2$ 行，第一行为两个正整数 $n, Q$, 表示齿轮数量和询问数量。

第二行为 $n$ 个正整数 $r_{1}, r_{2}, \ldots, r_{n}$，表示每个齿轮的半径。

后面 $Q$ 行，每行一个正整数 $q_{i}$ 表示询问。

1.3输出格式

$Q$ 行，对于每个询问，如果存在至少一种组装方案满足条件，输出 YES, 否则输出 NO。

样例输入

1
2
3
4
5

5 3
4 2 3 3 1
2
4
6

样例输出

1
2
3

YES
YES
NO

提示

【样例说明】

询问 $1$ 方案之一：23341。

询问 $2$ 方案之一：42331。

询问 $3$ 没有方案。

【评测用例规模与约定】

对于 $15 %$ 的数据，保证 $n, Q \leq 100$;

对于 $30 %$ 的数据，保证 $n, Q \leq 2000$;

对于 $100 %$ 的数据，保证 $n\ge 2,n, Q \leq 2 \times 10^{5} ; a_{i}, q_{i} \leq 2 \times 10^{5}$。

2.思路

很显然，放大（缩小）的倍率只和最开始和最后的两个齿轮有关系。与中间的齿轮无关。所以，对于每个询问$q_i$我们只需要找到是否存在两个齿轮使得它们的比值为$q_i$即可。

但是考虑到数据规模为2e5，且$q_i$范围也只有2e5，考虑预处理答案。注意一定要提前把齿轮离散化一下，也就是去重。

枚举两个齿轮的时间复杂度是$n^2$，显然不行。

考虑枚举一个齿轮，然后枚举它的不超过2e5倍数。这种做法的时间复杂度不好估计。在场上可以写个Python程序算一下：最坏情况下齿轮大小为1到2e5。显然可以像下面这样计算时间复杂度。要注意的是，齿轮要去重。否则最坏情况是全是大小为1的齿轮。

1
2
3
4

ans=0
for i in range(1,100000):
    ans = ans + int(100000/i)
print(ans)

结果为1166749

另外需要注意放大倍率为1的时候需要特判一下。

3.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 2e5+7;
int a[MAXN],vis[MAXN],m[MAXN];
bool ans[MAXN];
int main(){
	int n,q,cnt=0;
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(vis[a[i]]){
			ans[1]=1;
			continue;	
		}
		vis[a[i]]=1;
		m[++cnt]=a[i];
	}
	for(int i=1;i<=cnt;i++){
		for(int j=(m[i]<<1);j<=200000;j+=m[i]){
			if(vis[j])ans[j/m[i]]=1;
		}
	}
	int t;
	for(int i=1;i<=q;i++){
		scanf("%d",&t);
		cout<<(ans[t]==1?"YES\n":"NO\n"); 
	}
	return 0;
}