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

信息学奥赛初赛天天练-20-完善程序-vector数组参数引用传递、二分中值与二分边界应用的深度解析

PDF文档公众号回复关键字:20240605
在这里插入图片描述

1 2023 CSP-J 完善程序1

完善程序(单选题,每小题 3 分,共计 30 分)

原有长度为 n+1,公差为1等升数列,将数列输到程序的数组时移除了一个元素,导致长度为 n 的开序数组可能不再连续,除非被移除的是第一个或最后之个元素。需要在数组不连续时,找出被移除的元素。试补全程序。

源程序

01 #include <iostream>
02 #include <vector>
03
04 using namespace std;
05
06 int find_missing(vector<int>& nums){
07 		int left = 0, right = nums.size() - 1;
08 		while (left < right){
09   		int mid = left + (right-left) / 2;
10   		if (nums[mid]==mid+ ①){
11        		②;
12    		}else{
13      		③
14    		}
15   	}
16  	return ④;
17 }
18
19 int main(){
20 		int n;
21 		cin >> n;
22 		vector<int> nums(n);
23 		for (int i= 0; i< n; i++) cin >> nums[i];
24 		int missing_number = find_missing(nums);
25 		if(missing_number == ⑤) {
26     		cout << "Sequence is consecutive" << endl;
27 		}else{
28    		cout << "Missing number is " << missing_number << endl;
29 	    }
30 		return 0;
31 }

33 ①处应填( )

A 1 B nums[0] C right D left

34 ②处应填( )

A left=mid+1 B right=mid-1 C right=mid D left=mid

35 ③处应填( )

A left=mid+1 B right=mid-1 C right=mid D left=mid

36 ④处应填( )

A left+nums[0] B right+nums[0] C mid+nums[0] D right+1

37 ⑤处应填( )

A nums[0]+n B nums[0]+n-1 C nums[0]+n+1 D nums[n-1]

2 相关知识点

1) vector 参数传递-值传递

函数内形参改变对调用实参无影响

#include<bits/stdc++.h>
using namespace std;/*值传递 函数内增量了副本 函数内修改 对实参无影响 
*/ 
void testVector(vector<int> vec){vec.push_back(4); /*输出vec数组中每个元素,main函数实参传递过来3个2,函数内增加了1个4输出 2 2 2 4 */ for(int i=0;i<vec.size();i++){cout <<vec[i]<< ' ';}
}int main(){vector<int> vec(3,2);//声明一个vector数组,初始化3个2 testVector(vec);//调用函数输出 cout<<endl; //testVector 增加的4 对main函数的vec没影响/*输出vec数组中每个元素3个2输出 2 2 2 */ for(int i=0;i<vec.size();i++){cout <<vec[i]<< ' ';}return 0;
}

2) vector 参数传递-指针传递

函数内形参改变,改变了调用的实参

#include<bits/stdc++.h>
using namespace std;/*指针传递 函数操作的是vector指针,通过指针对vector数组修改后vector被改变 
*/ 
void testVector(vector<int> *vec){(*vec).push_back(4); /*输出vec数组中每个元素,main函数实参传递过来3个2,函数内增加了1个4输出 2 2 2 4 */ for(int i=0;i<(*vec).size();i++){cout <<(*vec)[i]<< ' ';}
}int main(){vector<int> vec(3,2);//声明一个vector数组,初始化3个2 testVector(&vec);//调用函数输出 cout<<endl; //testVector 增加了4 /*输出vec数组中每个元素3个2和 4输出 2 2 2 4*/ for(int i=0;i<vec.size();i++){cout <<vec[i]<< ' ';}return 0;
}

3) vector 参数引用传递

函数内形参改变,改变了调用的实参

#include<bits/stdc++.h>
using namespace std;/*指针传递 形参相当于是实参的别名,对形参的操作其实就是对实参的操作,形参vector改变,实参也会改变 
*/ 
void testVector(vector<int> &vec){vec.push_back(4); /*输出vec数组中每个元素,main函数实参传递过来3个2,函数内增加了1个4输出 2 2 2 4 */ for(int i=0;i<vec.size();i++){cout <<vec[i]<< ' ';}
}int main(){vector<int> vec(3,2);//声明一个vector数组,初始化3个2 testVector(vec);//调用函数输出 cout<<endl; //testVector 增加了4 /*输出vec数组中每个元素3个2和 4输出 2 2 2 4*/ for(int i=0;i<vec.size();i++){cout <<vec[i]<< ' ';}return 0;
}

4) 二分查找中间值

/* 向右逼近,如果找到满足条件的数,会继续向右找更大的数mid=(left+right)/2 left和right都接近最大值时,可能溢出可以使用下面写法替换mid=left + (right-left) / 2;
*//* 向左逼近,如果找到满足条件的数,会继续向左找更小的数mid=(left+right+1)/2 left和right都接近最大值时,可能溢出可以使用下面写法替换mid=left + (right-left+1) / 2;
*/

5) 二分找边界

//左闭右闭 while left right 最终left=right+1
while(left<=right)  left = mid + 1; right =mid-1;
//左闭右开 while left right 最终left=right
while(left<right)   left = mid + 1; right =mid;
//左开右闭 while left right 最终left=right
while(left<right)   left=mid;       right=mid+1;
//左开右开 while left right 最终left=right-1
while(left+1<right) left=mid;       right=mid;

3 思路分析

二分法,在本程序中find_missing函数就是利用二分法来找到一个长度为n的数组中不连续的位置,从而找出被移除 元素的值。只需通过二分找到从左往右第一处使得nums[i]不为nums[0]+i的的位置,那么在数组中被移除的数就是nums[0]+i

33 ①处应填( )

A 1 B nums[0] C right D left

答案 B

分析

/*
若数组连续, 一定有nums[i]==nums[0]+i,所以只需通过二分找到第一处使得nums[i]不为nums[0]+i的的位置即可。因此二分的判断条件是nums[mid]==mid+nums[0]所以选B
*/

34 ②处应填( )

A left=mid+1 B right=mid-1 C right=mid D left=mid

答案 A

分析

//由判断条件 nums[mid]==mid+nums[0] 可知,mid的左半部分是满足顺序的,继续往右找//由于mid计算是向下取整,需要向右靠近 所以left=mid+1
//int mid = left + (right-left) / 2; mid计算是向下取整 需要left=mid+1,向右逼近
int find_missing(vector<int>& nums){int left = 0, right = nums.size() - 1;while (left < right){int mid = left + (right-left) / 2;if (nums[mid]==mid+nums[0]){left=mid+1;//找到满足条件的继续向右找}else{right=mid;}}return left+nums[0];
}
//nums={0,1,3,4,5} 下面模拟具体细节
/*
left =0 right=4
mid=(0+4)/2=2 nums[2]=3,mid+nums[0]=2+0=2 不等 rgiht=mid=2 left=0 满足 while(left<right)
mid=(0+2)/2=1 nums[1]=1,mid+nums[0]=1+0=1 相等 left=mid+1=1 right=2 不满足 while(left<right)
退出循环
返回left+nums[0]=2
*///int mid = left + (right-left) / 2; mid计算是向下取整 如果left=mid 可能会死循环
int find_missing(vector<int>& nums){int left = 0, right = nums.size() - 1;while (left < right){int mid = left + (right-left) / 2;if (nums[mid]==mid+nums[0]){left=mid;//如果改成left=mid 会死循环}else{right=mid;}}return left+nums[0];
}
//nums={0,1,3,4,5}时会死循环 下面模拟具体细节
/*
left =0 right=4
mid=(0+4)/2=2 nums[2]=3,mid+nums[0]=2+0=2 不等 rgiht=mid=2 left=0 满足 while(left<right)
mid=(0+2)/2=1 nums[1]=1,mid+nums[0]=1+0=1 相等 left=mid=1 right=2 满足 while(left<right)
mid=(1+2)/2=1 nums[1]=1,mid+nums[0]=1+0=1 相等 left=mid=1 right=2 满足 while(left<right)
*/

35 ③处应填( )

A left=mid+1 B right=mid-1 C right=mid D left=mid

答案 C

分析

/*
由于退出条件是 while (left < right) 最终退出时left==right ,前面又 left=mid+1,所以right==mid即可while(left<right) 对应 二分区间是前闭后开或者前开后闭
*/

36 ④处应填( )

A left+nums[0] B right+nums[0] C mid+nums[0] D right+1

答案 A

分析

//如果序列从0开始,最后1个找到的连续数字再找一个就是被移除的,前面示例
//nums={0,1,3,4,5} 下面模拟具体细节
/*
left =0 right=4
mid=(0+4)/2=2 nums[2]=3,mid+nums[0]=2+0=2 不等 rgiht=mid=2 left=0 满足 while(left<right)
mid=(0+2)/2=1 nums[1]=1,mid+nums[0]=1+0=1 相等 left=mid+1=1 right=2 不满足 while(left<right)
退出循环
返回left+nums[0]=2
移除的数是2
*///如果不从0开始
//nums={2,3,5,6,7}
/*
left =0 right=4
mid=(0+4)/2=2 nums[2]=5,mid+nums[0]=2+2=4 不等 rgiht=mid=2 left=0 满足 while(left<right)
mid=(0+2)/2=1 nums[1]=3,mid+nums[0]=1+2=3 相等 left=mid+1=2 right=2 不满足 while(left<right)
退出循环
返回left+nums[0]=2+2=4
移除的数是4
*/
//退出条件是while(left<right) 最终left==right
//所以答案A和B都对,一般习惯返回left

37 ⑤处应填( )

A nums[0]+n B nums[0]+n-1 C nums[0]+n+1 D nums[n-1]

答案 D

分析

找到数组的最后一个,无论最后一个是否相等都说明前面都是连续的

相关文章:

信息学奥赛初赛天天练-20-完善程序-vector数组参数引用传递、二分中值与二分边界应用的深度解析

PDF文档公众号回复关键字:20240605 1 2023 CSP-J 完善程序1 完善程序&#xff08;单选题&#xff0c;每小题 3 分&#xff0c;共计 30 分&#xff09; 原有长度为 n1,公差为1等升数列&#xff0c;将数列输到程序的数组时移除了一个元素&#xff0c;导致长度为 n 的开序数组…...

推荐系统学习 一

参考&#xff1a;一文看懂推荐系统&#xff1a;召回08&#xff1a;双塔模型——线上服务需要离线存物品向量、模型更新分为全量更新和增量更新_数据库全量更新和增量更新流程图-CSDN博客 一文看懂推荐系统&#xff1a;概要01&#xff1a;推荐系统的基本概念_王树森 小红书-CSD…...

分库分表详解

文章目录 分库分表概述分库分表详解分库分表的策略分库分表的注意事项常用的分库分表中间件mysql单表达到多少数据量需要分库分表数据库分库分表缺点分表要停服吗&#xff0c;不停服怎么做 分库分表概述 分库分表是数据库架构设计中的一种常见策略&#xff0c;尤其是在面对大规…...

【java前端课堂】04_类的继承

类的继承 在Java中&#xff0c;继承是面向对象编程的四大基本特性之一&#xff0c;它允许我们根据一个已有的类来定义一个新的类&#xff0c;这个新的类继承了原有类的特性&#xff08;属性和方法&#xff09;&#xff0c;并可以添加新的特性或修改原有特性。这样&#xff0c;…...

React nginx配置,一个端口代理多个项目(转发后找不到CSS,JS及图片资源问题解决)

场景&#xff1a; nginx 配置负载均衡&#xff0c;甲方只提供一个端口&#xff0c;一个域名地址 方法&#xff1a; 一个端口一个域名匹配多个应用 方法一&#xff1a; 依靠设备浏览器区分: 使用UserAgent头来识别用户的客户端, CDN监测vary头的信息&#xff0c;如果内容不一致…...

Unity协程详解

什么是协程 协程&#xff0c;即Coroutine&#xff08;协同程序&#xff09;&#xff0c;就是开启一段和主程序异步执行的逻辑处理&#xff0c;什么是异步执行&#xff0c;异步执行是指程序的执行并不是按照从上往下执行。如果我们学过c语言&#xff0c;我们应该知道&#xff0…...

【iOS】UI学习(二)

目录 前言UIViewContorllerUIViewContorller基础UIViewContorller使用 定时器和视图移动UISwitch控件UIProgressView和UISlider总结 前言 本篇博客是笔者在学习UI部分内容时的成果和遇到的一些问题&#xff0c;既是我自己的学习笔记&#xff0c;也希望对你有帮助&#xff5e; …...

React路由(React笔记之五)

本文是结合实践中和学习技术文章总结出来的笔记(个人使用),如有雷同纯属正常((✿◠‿◠)) 喜欢的话点个赞,谢谢! React路由介绍 现在前端的项目一般都是SPA单页面应用,不再是以前多个页面多套HTML代码项目了,应用内的跳转不需要刷新页面就能完成页面跳转靠的就是路由系统 R…...

调用讯飞星火API实现图像生成

目录 1. 作者介绍2. 关于理论方面的知识介绍3. 关于实验过程的介绍&#xff0c;完整实验代码&#xff0c;测试结果3.1 API获取3.2 代码解析与运行结果3.2.1 完整代码3.2.2 运行结果 3.3 界面的编写&#xff08;进阶&#xff09; 4. 问题分析5. 参考链接 1. 作者介绍 刘来顺&am…...

reduce过滤递归符合条件的数据

图片展示 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Document</title> </head><…...

Go微服务: 基于rocketmq:5.2.0搭建RocketMQ环境,以及示例参考

概述 参考最新官方文档&#xff1a;https://rocketmq.apache.org/zh/docs/quickStart/03quickstartWithDockercompose以及&#xff1a;https://rocketmq.apache.org/zh/docs/deploymentOperations/04Dashboard综合以上两个文档来搭建环境 搭建RocketMQ环境 1 ) 基于 docker-c…...

Wpf 使用 Prism 开发MyToDo应用程序

MyToDo 是使用 WPF &#xff0c;并且塔配Prism 框架进行开发的项目。项目中进行了前后端分离设计&#xff0c;客户端所有的数据均通过API接口获取。适合新手入门学习WPF以及Prism 框架使用。 首页统计以及点击导航到相关模块功能待办事项增删改查功能备忘录增删改查功能登录注册…...

vue-Dialog 自定义title样式

展示结果 vue代码 <el-dialog :title"title" :visible.sync"classifyOpen" width"500px" :showClose"false" class"aboutDialog"> <el-form :model"classifyForm" :rules"classifyRules">…...

数据库主键设计

文章目录 前言1. 自增ID&#xff08;Auto-Increment&#xff09;2. GUID (Globally Unique Identifier)3. 雪花算法&#xff08;Snowflake&#xff09;处理时钟回拨的方法1. 简单等待2. 配置时钟回拨安全窗口3. 使用不同的机器 ID 小结稳定的雪花算法实现方案示例实现1. 定义雪…...

小熊家务帮day13-day14 门户管理(ES搜索,Canal+MQ同步,索引同步)

目录 1 服务搜索1.1 需求分析1.2 技术方案1.2.1 使用Elasticsearch进行全文检索&#xff08;为什么数据没有那么多还要用ES&#xff1f;&#xff09;1.2.2 索引同步方案1.2.2.1 Canal介绍1.2.2.1 Canal工作原理 1 服务搜索 1.1 需求分析 服务搜索的入口有两处&#xff1a; 在…...

Android8.1高通平台修改默认输入法

需求 安卓8.1 SDK原生的输入法只能打英文, 需要替换成中文输入法. 以高通平台为例, 其它平台也适用. 查看设备当前默认输入法 adb shell settings list secure | grep input 可以看到当前默认是LatinIME这个安卓原生输入法. default_input_methodcom.android.inputmethod.l…...

49. 字母异位词分组

思路&#xff1a;题目的意思是&#xff0c;将所有字母相同的字符串放到一个数组中 解题思路是&#xff1a;使用map,使用排序好的字符串作为key&#xff0c;源字符串作为value,就可以实现所有字母相同的字符串对应一个key vector<vector<string>> groupAnagrams(ve…...

负压实验室设计建设方案

随着全球公共卫生事件的频发&#xff0c;负压实验室的设计和建设在医疗机构中的重要性日益凸显。负压实验室&#xff0c;特别是负压隔离病房&#xff0c;主要用于控制传染性疾病的扩散&#xff0c;保护医护人员和周围环境的安全。广州实验室装修公司中壹联凭借丰富的实验室装修…...

作文笔记10 复述故事

一、梳理内容&#xff08;用表格&#xff0c;示意图&#xff09; 救白蛇 得宝石 救相亲 变石头 人们纪念海力布 二、按顺序&#xff0c;不遗漏主要情节 &#xff08;猎人海力布热心救人&#xff09;救白蛇 得宝石&#xff08;白蛇强调宝石禁忌&#xff09;&#xff08;海力…...

业务安全蓝军测评标准解读—业务安全体系化

目录 1.前言 2.业务蓝军测评标准 2.1 业务安全脆弱性评分(ISVS) 2.2 ISVS评分的参考意义<...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...

麒麟系统使用-进行.NET开发

文章目录 前言一、搭建dotnet环境1.获取相关资源2.配置dotnet 二、使用dotnet三、其他说明总结 前言 麒麟系统的内核是基于linux的&#xff0c;如果需要进行.NET开发&#xff0c;则需要安装特定的应用。由于NET Framework 是仅适用于 Windows 版本的 .NET&#xff0c;所以要进…...