当前位置: 首页 > news >正文

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

[蓝桥杯 2022 国 B] 齿轮

题目描述

这天,小明在组装齿轮。

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

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

输入格式

输入共 Q+2Q+2Q+2 行,第一行为两个正整数 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,Q100;

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

对于 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,Q2×105;ai,qi2×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;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;
}

在这里插入图片描述

相关文章:

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

[蓝桥杯 2022 国 B] 齿轮 题目描述 这天&#xff0c;小明在组装齿轮。 他一共有 nnn 个齿轮&#xff0c;第 iii 个齿轮的半径为 rir_{i}ri​, 他需要把这 nnn 个齿轮按一定顺序从左到右组装起来&#xff0c;这样最左边的齿轮转起来之后&#xff0c;可以传递到最右边的齿轮&a…...

景区在线售票系统功能开发介绍

目前游客线上订票已经普及&#xff0c;景区开通线上购票渠道&#xff0c;方便游客购票&#xff0c;对于还没有开通线上购票的景区来说&#xff0c;需要提前了解一下景区线上售票系统的一些功能&#xff0c;下面给大家详细介绍一下景区在线售票需要哪些功能。 1、在线售票 包含门…...

webService的底层调用方式

webservice中采用协议Http&#xff0c;是指什么意思 WebService使用的是 SOAP (Simple Object Access Protocol)协议 Soap协议只是用来封装消息用的。封装后的消息你可以通过各种已有的协议来传输&#xff0c;比如http,tcp/ip,smtp,等等&#xff0c;你甚至还一次用自定义的协议…...

关于文件的一些小知识下

&#x1f34d;个人主页&#x1f34d;:&#x1f51c;勇敢的小牛儿&#x1f6a9; &#x1f531;推荐专栏&#x1f531;&#xff1a;C语言知识点 ⚠️座右铭⚠️&#xff1a;敢于尝试才有机会 &#x1f412;今日鸡汤&#x1f412;&#xff1a; 你受的苦 吃的亏 担的责 扛的罪 忍的…...

使用Cheat Engine与DnSpy破解Unity游戏

题目连接&#xff1a; https://play.picoctf.org/practice/challenge/361?originalEvent72&page3我们是windows系统&#xff0c;所以点击windows game下载游戏 双击运行pico.exe 屏幕上方的一串英文是叫我们找flag&#xff0c;我在这个小地图里走来走去也没flag&#xff…...

溯源取证-内存取证基础篇

使用工具&#xff1a; volatility_2.6_lin64_standalone 镜像文件&#xff1a; CYBERDEF-567078-20230213-171333.raw 使用环境&#xff1a; kali linux 2022.02 我们只有一个RAW映像文件&#xff0c;如何从该映像文件中提取出我们想要的东西呢&#xff1f; 1.Which volatili…...

Leetcode.100 相同的树

题目链接 Leetcode.100 相同的树 easy 题目描述 给你两棵二叉树的根节点 p和 q&#xff0c;编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同&#xff0c;并且节点具有相同的值&#xff0c;则认为它们是相同的。 示例 1&#xff1a; 输入&#xff1a;p [1,2,3…...

每个程序员都应该知道的8大算法

在编程开发中&#xff0c;算法是用于解决特定问题或完成特定任务的一组指令或过程。算法可以用任何编程语言表示&#xff0c;可以像一系列基本操作一样简单&#xff0c;也可以像涉及不同数据结构和逻辑的多步骤过程一样复杂。 算法的主要目标是接收输入、处理它并提供预期的输…...

Nestjs实战超干货-概况-模块-Modules

模块 模块就是一个声明了装饰器Module()的类。装饰器Module()提供了元数据&#xff0c;以便让Nest组织应用程序结构。 每个应用程序至少有一个模块&#xff0c;即根模块。根模块是 Nest 用来构建应用程序图的起点&#xff0c;应用程序图是 Nest 用来解析模块和提供者关系和依赖…...

template

模板 模板注意事项 模板的函数体和声明一定要在一起&#xff0c;即放在同一个.h文件中&#xff0c;而不能将其分开到cpp和h文件中模板的编译技巧就是尽量多编译&#xff0c;模板很难查找错误模板的报错一般只有第一行有作用模板指定类型从左到右依次指定 模板推导 #pragma #…...

innovus中时序路径debug及命令使用详解?

写在前面&#xff1a;发现place结果所有与outport相关的timing check都找不到&#xff1f; 刚开始怀疑是sdc约束问题&#xff0c;check了input sdc文件及enc.dat/mmmc/mode/func.sdc 看一下是否设置了set_false_path.当然也可以用命令报出来: report_timing -unconstrained …...

C语言爱心代码大全集—会Ctrl+C就可以表白了

一、C语言爱心代码大全&#xff0c;会CtrlC就可以表白了&#xff01; 博主整理了一个C语言爱心代码大全&#xff0c;里面有C语言爱心代码会动的动态效果和C语言爱心代码大全静态效果&#xff0c;只需复制粘贴就可以用啦&#xff01; 1、动态C语言爱心代码效果图如下&#xff…...

python+vue+django耕地信息管理系统的设计与实现

基普通用户模块含有个人中心、耕地信息管理、转让许可申请管理、租赁许可申请管理等功能&#xff1b;普通管理员模块含有个人中心、用户管理、公示公告管理、耕地信息管理、耕地信息统计、转让许可申请管理、租赁许可申请管理、转让协议管理、租赁协议管理等功能&#xff1b;管…...

【云原生】Dockerfile制作WordPress镜像,实现compose编排部署

文章目录&#x1f479; 关于作者前言环境准备目录结构dockerfile制作镜像yum 脚本Dockerfile-mariadb 镜像Dockerfile-service 镜像docker compose 编排提升✊ 最后&#x1f479; 关于作者 大家好&#xff0c;我是秋意临。 &#x1f608; CSDN作者主页 &#x1f60e; 博客主页…...

五款好用又有趣的WIN10软件推荐

如果你想让你的电脑使用更方便、更有趣、更专业&#xff0c;那么你一定要看看这篇文章&#xff0c;因为我要给你推荐五款好用又有趣的WIN10软件 1.全局搜索——火柴 火柴是一款全局搜索软件&#xff0c;可以让你快速找到你想要的文件、程序、网页等&#xff0c;只需按下AltSp…...

朴素贝叶斯算法

# -*-coding:utf-8-*- """ Author: sunchang Desc: 代码4-7 朴素贝叶斯实现对异常账户检测 """ import numpy as np class NaiveBayesian: def __init__(self, alpha): self.classP dict() self.classP_f…...

【常见CSS扫盲雪碧图】从源码细看CSS雪碧图原理及实现,千字详解【附源码demo下载】

【写在前面】其实估计很多人都听过雪碧图&#xff0c;或者是CSS-Sprite&#xff0c;在很多门户网站就会经常有用到的&#xff0c;之所有引出雪碧图这个概念还得从前端加载多个图片时候页面闪了一下说起&#xff0c;这样给人的视觉效果体验很差&#xff0c;也就借此机会和大家说…...

Java多线程:ThreadLocal源码剖析

ThreadLocal源码剖析 ThreadLocal其实比较简单&#xff0c;因为类里就三个public方法&#xff1a;set(T value)、get()、remove()。先剖析源码清楚地知道ThreadLocal是干什么用的、再使用、最后总结&#xff0c;讲解ThreadLocal采取这样的思路。 三个理论基础 在剖析ThreadLo…...

96、数据的存储

运行实例&#xff1a; 在debug和release两种模式下&#xff0c;进行代码运行&#xff0c;debug下 i 的地址是大于arr[9] 的地址的&#xff0c;release 下i 的地址是小于arr[9] 的地址。原因是:release状态进行了优化处理。 C语言中基本的内置类型 整形数据类型 char …...

@EventListener注解详细使用(IT枫斗者)

EventListener注解详细使用 简介 EventListener是一种事件驱动编程在spring4.2的时候开始有的&#xff0c;早期可以实现ApplicationListener接口, 为我们提供的一个事件监听、订阅的实现&#xff0c;内部实现原理是观察者设计模式&#xff1b;为的就是业务系统逻辑的解耦,提高…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...