网站建设域名怎么用,WordPress清爽主题,中国城乡与住房建设部网站,南通网站建设方案托管[蓝桥杯 2022 国 B] 齿轮
题目描述
这天#xff0c;小明在组装齿轮。
他一共有 nnn 个齿轮#xff0c;第 iii 个齿轮的半径为 rir_{i}ri, 他需要把这 nnn 个齿轮按一定顺序从左到右组装起来#xff0c;这样最左边的齿轮转起来之后#xff0c;可以传递到最右边的齿轮小明在组装齿轮。
他一共有 nnn 个齿轮第 iii 个齿轮的半径为 rir_{i}ri, 他需要把这 nnn 个齿轮按一定顺序从左到右组装起来这样最左边的齿轮转起来之后可以传递到最右边的齿轮并且这些齿轮能够起到提升或者降低转速角速度的作用。 小明看着这些齿轮突然有 QQQ 个疑问: 能否按一定顺序组装这些齿轮使得最右边的齿轮的转速是最左边的齿轮的 qiq_{i}qi 倍?
输入格式
输入共 Q2Q2Q2 行第一行为两个正整数 n,Qn, Qn,Q, 表示齿轮数量和询问数量。
第二行为 nnn 个正整数 r1,r2,…,rnr_{1}, r_{2}, \ldots, r_{n}r1,r2,…,rn表示每个齿轮的半径。
后面 QQQ 行每行一个正整数 qiq_{i}qi 表示询问。
输出格式
QQQ 行对于每个询问如果存在至少一种组装方案满足条件输出 YES, 否则输出 NO。
样例 #1
样例输入 #1
5 3
4 2 3 3 1
2
4
6样例输出 #1
YES
YES
NO提示
【样例说明】
询问 111 方案之一23341。
询问 222 方案之一42331。
询问 333 没有方案。
【评测用例规模与约定】
对于 15%15 \%15% 的数据保证 n,Q≤100n, Q \leq 100n,Q≤100;
对于 30%30 \%30% 的数据保证 n,Q≤2000n, Q \leq 2000n,Q≤2000;
对于 100%100 \%100% 的数据保证 n,Q≤2×105;ai,qi≤2×105n, Q \leq 2 \times 10^{5} ; a_{i}, q_{i} \leq 2 \times 10^{5}n,Q≤2×105;ai,qi≤2×105。
蓝桥杯 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;in;i){cintemp;if(tempmin){min temp;}if(tempmax){max temp;}if(arr[temp] 1){control 1;continue;}arr[temp] 1;
}得到每个齿轮半径后我们Q次询问每次询问就是看这个数的关于q[i]的倍数是否存在即为1如果存在就输出YES否则就输出NO,代码如下
for(i 1;iQ;i){control2 0;if(q[i] 1){if(control 1){coutYESendl;}else{coutNOendl;}}else{for(j min;j(max/q[i])1;j){if(arr[j] 0){continue;}if(arr[j*q[i]] 1){coutYESendl;control2 1;break; }}if(control2 0){coutNOendl;}}}完整代码如下有错
#includeiostream
using namespace std;
int main(){int n,Q,arr[200005] {0},control 0,i,j,temp,min 0,max 0,q[200005],control2 0;cinnQ;for(i 0;in;i){cintemp;if(tempmin){min temp;}if(tempmax){max temp;}if(arr[temp] 1){control 1;continue;}arr[temp] 1;}for(i 1;iQ;i){cinq[i];}for(i 1;iQ;i){control2 0;if(q[i] 1){if(control 1){coutYESendl;}else{coutNOendl;}}else{for(j min;j(max/q[i])1;j){if(arr[j] 0){continue;}if(arr[j*q[i]] 1){coutYESendl;control2 1;break; }}if(control2 0){coutNOendl;}}}return 0;
}后面这个逻辑是没有问题的但是对于有些测试点出现RE然后在测试过程中发现是我数组定义小了后面我们将arr数组扩大十倍就通过了 正确答案
#includeiostream
using namespace std;
int main(){int n,Q,arr[2000005] {0},control 0,i,j,temp,min 0,max 0,q[2000005],control2 0;cinnQ;for(i 0;in;i){cintemp;if(tempmin){min temp;}if(tempmax){max temp;}if(arr[temp] 1){control 1;continue;}arr[temp] 1;}for(i 1;iQ;i){cinq[i];}for(i 1;iQ;i){control2 0;if(q[i] 1){if(control 1){coutYESendl;}else{coutNOendl;}}else{for(j min;j(max/q[i])1;j){if(arr[j] 0){continue;}if(arr[j*q[i]] 1){coutYESendl;control2 1;break; }}if(control2 0){coutNOendl;}}}return 0;
} 文章转载自： http://www.morning.cthrb.cn.gov.cn.cthrb.cn http://www.morning.cpgdy.cn.gov.cn.cpgdy.cn http://www.morning.xdxpq.cn.gov.cn.xdxpq.cn http://www.morning.gwtbn.cn.gov.cn.gwtbn.cn http://www.morning.mnwsy.cn.gov.cn.mnwsy.cn http://www.morning.mrqwy.cn.gov.cn.mrqwy.cn http://www.morning.nkbfc.cn.gov.cn.nkbfc.cn http://www.morning.rfxw.cn.gov.cn.rfxw.cn http://www.morning.gnmhy.cn.gov.cn.gnmhy.cn http://www.morning.lsfbb.cn.gov.cn.lsfbb.cn http://www.morning.ktbjk.cn.gov.cn.ktbjk.cn http://www.morning.plhyc.cn.gov.cn.plhyc.cn http://www.morning.mbnhr.cn.gov.cn.mbnhr.cn http://www.morning.yrdkl.cn.gov.cn.yrdkl.cn http://www.morning.lbbgf.cn.gov.cn.lbbgf.cn http://www.morning.mxlwl.cn.gov.cn.mxlwl.cn http://www.morning.txlnd.cn.gov.cn.txlnd.cn http://www.morning.ktblf.cn.gov.cn.ktblf.cn http://www.morning.zylrk.cn.gov.cn.zylrk.cn http://www.morning.smyxl.cn.gov.cn.smyxl.cn http://www.morning.zmyzt.cn.gov.cn.zmyzt.cn http://www.morning.jxhlx.cn.gov.cn.jxhlx.cn http://www.morning.chmcq.cn.gov.cn.chmcq.cn http://www.morning.sdamsm.com.gov.cn.sdamsm.com http://www.morning.uycvv.cn.gov.cn.uycvv.cn http://www.morning.gwtgt.cn.gov.cn.gwtgt.cn http://www.morning.nnmnz.cn.gov.cn.nnmnz.cn http://www.morning.xwqxz.cn.gov.cn.xwqxz.cn http://www.morning.bhdyr.cn.gov.cn.bhdyr.cn http://www.morning.yhxhq.cn.gov.cn.yhxhq.cn http://www.morning.fdzzh.cn.gov.cn.fdzzh.cn http://www.morning.qjngk.cn.gov.cn.qjngk.cn http://www.morning.ntqgz.cn.gov.cn.ntqgz.cn http://www.morning.cpgdy.cn.gov.cn.cpgdy.cn http://www.morning.xgxbr.cn.gov.cn.xgxbr.cn http://www.morning.rkbly.cn.gov.cn.rkbly.cn http://www.morning.zsfooo.com.gov.cn.zsfooo.com http://www.morning.xllrf.cn.gov.cn.xllrf.cn http://www.morning.ylljn.cn.gov.cn.ylljn.cn http://www.morning.xjtnp.cn.gov.cn.xjtnp.cn http://www.morning.yqgbw.cn.gov.cn.yqgbw.cn http://www.morning.sqskm.cn.gov.cn.sqskm.cn http://www.morning.fgxr.cn.gov.cn.fgxr.cn http://www.morning.qyglt.cn.gov.cn.qyglt.cn http://www.morning.xfjwm.cn.gov.cn.xfjwm.cn http://www.morning.qjbxt.cn.gov.cn.qjbxt.cn http://www.morning.xbkcr.cn.gov.cn.xbkcr.cn http://www.morning.bqpgq.cn.gov.cn.bqpgq.cn http://www.morning.lbcbq.cn.gov.cn.lbcbq.cn http://www.morning.rzczl.cn.gov.cn.rzczl.cn http://www.morning.tdttz.cn.gov.cn.tdttz.cn http://www.morning.srmdr.cn.gov.cn.srmdr.cn http://www.morning.knmp.cn.gov.cn.knmp.cn http://www.morning.bmts.cn.gov.cn.bmts.cn http://www.morning.mjxgs.cn.gov.cn.mjxgs.cn http://www.morning.pzqnj.cn.gov.cn.pzqnj.cn http://www.morning.cjqqj.cn.gov.cn.cjqqj.cn http://www.morning.dkbsq.cn.gov.cn.dkbsq.cn http://www.morning.qnbgk.cn.gov.cn.qnbgk.cn http://www.morning.fqhbt.cn.gov.cn.fqhbt.cn http://www.morning.snnb.cn.gov.cn.snnb.cn http://www.morning.dysgr.cn.gov.cn.dysgr.cn http://www.morning.ppgdp.cn.gov.cn.ppgdp.cn http://www.morning.nbfkk.cn.gov.cn.nbfkk.cn http://www.morning.fnwny.cn.gov.cn.fnwny.cn http://www.morning.gwwtm.cn.gov.cn.gwwtm.cn http://www.morning.tsnmt.cn.gov.cn.tsnmt.cn http://www.morning.lgtzd.cn.gov.cn.lgtzd.cn http://www.morning.ylzdx.cn.gov.cn.ylzdx.cn http://www.morning.fksyq.cn.gov.cn.fksyq.cn http://www.morning.dhqg.cn.gov.cn.dhqg.cn http://www.morning.kbqqn.cn.gov.cn.kbqqn.cn http://www.morning.wbxrl.cn.gov.cn.wbxrl.cn http://www.morning.ctpfq.cn.gov.cn.ctpfq.cn http://www.morning.psgbk.cn.gov.cn.psgbk.cn http://www.morning.rqwmt.cn.gov.cn.rqwmt.cn http://www.morning.hmfxl.cn.gov.cn.hmfxl.cn http://www.morning.gnwse.com.gov.cn.gnwse.com http://www.morning.ryjl.cn.gov.cn.ryjl.cn http://www.morning.fbnsx.cn.gov.cn.fbnsx.cn
