第十三届蓝桥杯C++B组国赛I题——齿轮 (AC)

╰半橙微兮° 2023-09-28 23:17 36阅读 0赞

#### 目录 ####

*  1.齿轮
 *   *  1.题目描述
     *  2.输入格式
     *  3.输出格式
     *  4.样例输入
     *  5.样例输出
     *  6.样例说明
     *  6.数据范围
     *  7.原题链接
 *  2.解题思路
 *  3.Ac\_code

## 1.齿轮 ##

### 1.题目描述 ###

这天, 小明在组装齿轮。

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

![3b5bf5e758974805a42fb4b7b4705694.png][]

小明看着这些齿轮, 突然有  Q Q Q 个疑问：能否按一定顺序组装这些齿轮使得 最右边的齿轮的转速是最左边的齿轮的  q i q\_\{i\} qi 倍?

### 2.输入格式 ###

输入共  Q + 2 Q+2 Q\+2 行, 第一行为两个正整数  n , Q n,Q n,Q, 表示齿轮数量和询问数量。  
第二行为  n n n 个正整数  r 1 , r 2 , … , r n r\_\{1\}, r\_\{2\}, \\ldots, r\_\{n\} r1,r2,…,rn, 表示每个齿轮的半径。后面  Q Q Q 行, 每行一个正整数  q i q\_\{i\} qi表示询问。

### 3.输出格式 ###

Q Q Q 行, 对于每个询问, 如果存在至少一种组装方案满足条件, 输出  ′ Y E S ′ \\mathrm\{'YES\}' ′YES′, 否则输出 ’  N O \\mathrm\{NO\} NO '。

### 4.样例输入 ###

5 3  
4 2 3 3 1  
2  
4  
6

### 5.样例输出 ###

YES  
YES  
NO

### 6.样例说明 ###

询问 1 方案之一 ： 23341：23341  
询问 2 方案之一：42331

询问 3 没有方案

### 6.数据范围 ###

n , Q ≤ 2 × 1 0 5 ; r i , q i ≤ 2 × 1 0 5 n,Q≤2×10^5 ;r i ,q i ≤2×10^5 n,Q≤2×105;ri,qi≤2×105

### 7.原题链接 ###

[齿轮][Link 1]

## 2.解题思路 ##

首先，这里涉及到一个物理公式，涉及到线速度 v , v, v,角速度  w w w 以及半径  r r r 之间的关系。它们之间满足:  
 v = w ∗ r v=w\*r v=w∗r

而齿轮模型是一个经典的物理模型，**所有的齿轮的线速度都一样。** 对于任意的齿轮之间都一定满足:  
 w x ∗ r x = w y ∗ r y w\_x\*r\_x=w\_y\*r\_y wx∗rx=wy∗ry

假设最左边的的齿轮半径为  x x x ，最右边的齿轮半径为  y y y ，那么使得最右边的齿轮的转速(角速度)是最左边的  q q q 倍，则需满足：  
 w x ∗ q = w y w\_x\*q=w\_y wx∗q=wy  
联立上述两式可解得：  
 r x = q ∗ r y r\_x=q\*r\_y rx=q∗ry

所以我们可知，我们只需要去判断所有齿轮的半径之间是否存在两个齿轮的半径是  q q q 倍的关系。既然存在倍数关系，那么说明两个齿轮的半径其中一个必然是另外一个的因数。我们使用数组`st`，其中`st[[i]`表示是否有半径相差 q q q倍的两个齿轮。

我们可以将齿轮半径按**从小到大进行排序**，对于每个齿轮的半径 r i r\_i ri，我们将去分解其所有的因数,如果存在某个数 x x x是 r i r\_i ri的因数，并且之前已经出现过半径为 x x x的齿轮，则说明当 q = r i / x q=r\_i/x q=ri/x时，我们是可以完成要求的。当然我们在分解因数时，应该进行优化，当 x x x是 r i r\_i ri的因数时， r i / x r\_i/x ri/x也一定是 r i r\_i ri的因数，此时我们可以直接一起进行判断。这样分解每个数的复杂度的 O ( n ) O(n) O(n)级别降低到 O ( n ) O(\\sqrt n) O(n)。

每次判断一个数后我们将其放入`set`中，在判断该数的因数在是否出现也是看`set`中是否存在。**因为每个数的因数一定小于等于数的本身**，所以这是我们排序的目的，确保了如果一个数的因数存在，那么一定会在它之前出现。

这个题目一定要**注意一个点**，齿轮的个数可能只有一个，那么此时左齿轮恰好就是右齿轮，如果查询的 q q q为`1`时，是符合要求的，所以我们需要对这种情况进行特判。

时间复杂度： O ( n n ) O(n\\sqrt n) O(nn)

## 3.Ac\_code ##

#include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const int N=200010;
    
    bool st[N];
    int r[N];
    int main() 
    {
        
    	int n,q;
    	scanf("%d%d",&n,&q);
    	unordered_set<int> s;
    	for(int i=0;i<n;++i){
        
    		scanf("%d",&r[i]);
    	}
    	sort(r,r+n);
    	for(int i=0;i<n;++i){
        
    		int v=r[i];
    		for(int i=1;i<=v/i;++i){
        
    			if(v%i==0){
        
    				//存在这个半径为i的齿轮
    				if(s.find(i)!=s.end()){
        
    					st[v/i]=true;
    				}
    				//存在这个半径为v/i的齿轮
    				if(s.find(v/i)!=s.end()){
        
    					st[i]=true;
    				}
    			}
    		}
    		s.insert(r[i]);
    	}
    	for(int i=0;i<q;++i){
        
    		int h;
    		scanf("%d",&h);
    		if(n==1&&h==1) puts("YES");
    		else if(st[h]) puts("YES");
    		else puts("NO");
    	}
        return 0;
    }

[3b5bf5e758974805a42fb4b7b4705694.png]: https://img-blog.csdnimg.cn/3b5bf5e758974805a42fb4b7b4705694.png
[Link 1]: https://www.lanqiao.cn/problems/2200/learning/