洛谷P8799 [蓝桥杯 2022 国 B] 齿轮 C语言/C++

[蓝桥杯 2022 国 B] 齿轮

题目描述

这天，小明在组装齿轮。

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

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

输入格式

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

第二行为 $n$ 个正整数 $r_1,r_2,\dots ,r_n$，表示每个齿轮的半径。

后面 $Q$ 行，每行一个正整数 $q_i$ 表示询问。

输出格式

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

样例 #1

样例输入 #1

5 3
4 2 3 3 1
2
4
6

样例输出 #1

YES
YES
NO

提示

【样例说明】

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

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

询问 $3$ 没有方案。

【评测用例规模与约定】

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

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

对于 $100\%$ 的数据，保证 $n,Q\le 2\times 10^5;a_i,q_i\le 2\times 10^5$。

蓝桥杯 2022 国赛 B 组 I 题。

所需变量

int n;//代表n个齿轮的大小

int Q;//代表询问的次数

int arr[200005] = {0};//用于存储每个齿轮的大小

int control = 0;//1代表1倍是否存在

int i,j;//循环变量

int temp;//用于接收每个齿轮大小，然后再存入进去

int min = 0;//代表齿轮的最小大小

int max = 0;//代表齿轮的最大大小

int q[200005];//代表每次询问的齿轮大小

int control2 = 0;//代表后面是否存在，如果不存在那么control2就是0，就输出NO,否则就输出YES

思路：我们要知道齿轮转动倍数跟中间那些齿轮半径都没有关系，只跟最开始和最后那个有关系，如果是k倍，我们只需要最后那个齿轮的半径是最开始那个的k倍就能满足题目所需要求！
因此首先我们将每个数都存入进去，然后再arr数组中，我们分别用下标表示这个齿轮的半径，如果存在我们就把arr[i]赋值为1，如果这个数已经存在，在遇到一个相同的，我们就将control赋值为1！代码如下：

for(i = 0;i<n;i++){cin>>temp;if(temp<min){min = temp;}if(temp>max){max = temp;}if(arr[temp] == 1){control = 1;continue;}arr[temp] = 1;
}

得到每个齿轮半径后，我们Q次询问每次询问就是看这个数的关于q[i]的倍数是否存在（即为1），如果存在就输出YES，否则就输出NO,代码如下：

for(i = 1;i<=Q;i++){control2 = 0;if(q[i] == 1){if(control == 1){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}else{for(j = min;j<=(max/q[i])+1;j++){if(arr[j] == 0){continue;}if(arr[j*q[i]] == 1){cout<<"YES"<<endl;control2 = 1;break; }}if(control2 == 0){cout<<"NO"<<endl;}}}

完整代码如下（有错）：

#include<iostream>
using namespace std;
int main(){int n,Q,arr[200005] = {0},control = 0,i,j,temp,min = 0,max = 0,q[200005],control2 = 0;cin>>n>>Q;for(i = 0;i<n;i++){cin>>temp;if(temp<min){min = temp;}if(temp>max){max = temp;}if(arr[temp] == 1){control = 1;continue;}arr[temp] = 1;}for(i = 1;i<=Q;i++){cin>>q[i];}for(i = 1;i<=Q;i++){control2 = 0;if(q[i] == 1){if(control == 1){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}else{for(j = min;j<=(max/q[i])+1;j++){if(arr[j] == 0){continue;}if(arr[j*q[i]] == 1){cout<<"YES"<<endl;control2 = 1;break; }}if(control2 == 0){cout<<"NO"<<endl;}}}return 0;
}

后面这个逻辑是没有问题的，但是对于有些测试点出现RE，然后在测试过程中发现是我数组定义小了，后面我们将arr数组扩大十倍，就通过了！
正确答案：

#include<iostream>
using namespace std;
int main(){int n,Q,arr[2000005] = {0},control = 0,i,j,temp,min = 0,max = 0,q[2000005],control2 = 0;cin>>n>>Q;for(i = 0;i<n;i++){cin>>temp;if(temp<min){min = temp;}if(temp>max){max = temp;}if(arr[temp] == 1){control = 1;continue;}arr[temp] = 1;}for(i = 1;i<=Q;i++){cin>>q[i];}for(i = 1;i<=Q;i++){control2 = 0;if(q[i] == 1){if(control == 1){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}else{for(j = min;j<=(max/q[i])+1;j++){if(arr[j] == 0){continue;}if(arr[j*q[i]] == 1){cout<<"YES"<<endl;control2 = 1;break; }}if(control2 == 0){cout<<"NO"<<endl;}}}return 0;
}