各题型题解 p { text-indent: 2em; } 算法基础 贪心 模拟 枚举 分治 排序 二分 P1182 数列分段 Section II - 洛谷 二分答案 构造 倍增 前缀和/差分 1526. 形成目标数组的子数组最少增加次数 - 力扣（LeetCode） 题目大意 问对初始全为0的序列，如果每次仅允许对[l,r]区间的所有元素加1，那么求出得到target数组的最少操作次数 我们知道对差分数组作前缀和能得到原数组。由于 target 是通过 \([l,r]\) 区间元素加 \(1\) 得到的，target 的差分数组 diff 显然记录了这样的过程： 每次 \([l,r]\) 操作对应 \(diff[l]+1\) 、 \(diff[r+1]-1\) 在操作结束后，对 diff 作前缀和操作，得到 target 我们要做的显然就是 “溯源”。 事实上，最少操作次数为其差分数组中正整数之和。 证明 显然正整数是操作的痕迹 ...

下列OJ平台仅代表题目信息的一个出处，不一定为OJ平台原创 每道题下面的均为其中关键的解题思路，题目大意并非完整题目，只出现解题思路中需要的变量。 （因此，基于测试用例t等无关变量将不会出现） 各题出处如下： Codeforces 洛谷 力扣 码蹄集OJ(百度) 蓝桥杯 其他 Codeforces Cherry Bomb Codeforces Round 1020 div.3 C. Cherry Bomb Problem - C - Codeforces tags: greedy math sortings *1000 题目大意 两个非负整数数组a与b，当我们称其互补时，当且仅当对于每个编号i，均有ai+bi= x, 其中x为一定值。我们希望数组a,b的每个元素均非负且不大于k,并且a与b是互补的。接下来，会给出n和k、完整的数组a，以及不完整的数组b，不完整的地方用-1补齐，请问有多少种填充b的办法满足我们的需要。 ​ 核心是如何确定互补值的值域，或者minb、maxb的值域 Fa ...

5.1.1 $I/O$ 设备的概念与分类一、基本概念 $I/O$ 设备即输入/输出（$Input/Output$）设备，是负责实现计算机与外部环境之间数据输入、输出交互的外部设备。 分类1. 按使用特性分类 人机交互类外部设备：用于实现人与计算机的交互，数据传输速度慢。 典型设备：鼠标、键盘、打印机等。 存储设备：用于持久化存储数据，数据传输速度快。 典型设备：磁盘、移动硬盘、光盘等。 网络通信设备：用于跨主机的网络数据通信，数据传输速度介于人机交互设备与存储设备之间。 典型设备：调制解调器、路由器等。 2. 按传输速率分类 低速设备：传输速率为每秒几个到几百字节。 典型设备：鼠标、键盘。 中速设备：传输速率为每秒数千至上万个字节。 典型设备：激光打印机。 高速设备：传输速率为每秒数千字节至千兆字节级别。 典型设备：磁盘。 3. 按信息交换的单位分类（核心考点） 块设备 数据传输的基本单位是“块”； 传输速率高，支持寻址，可随机读写任意一块； 典型设备：磁盘。 字符设备 数据传输的基本单位是字符； 传输速率慢，不可寻址，输入输出通常采用中 ...

4.1_1初识文件管理 4.1_2文件的逻辑结构分类总览文件逻辑结构分为两大类：无结构文件、有结构文件。 无结构文件：文件内部由二进制流/字符流构成，又称流式文件。例：Windows中的.txt文件。 有结构文件：又称记录式文件，由一组相似记录组成，每条记录包含若干数据项；一般选取一个数据项作为关键字。 按记录长度分为：定长记录、可变长记录。 有结构文件的逻辑结构包含三类：顺序文件、索引文件、索引顺序文件。 顺序文件 默认物理上为顺序存储。分为串结构、顺序结构。 串结构：记录顺序与关键字无关。 顺序结构：记录按关键字顺序排列。 定长记录 可以实现随机存取。第 $$i$$ 个记录相对位置：$$i \times L$$ 顺序结构：支持折半查找，可根据关键字快速检索记录。 串结构：无法利用关键字快速查找。 可变长记录 无法实现随机存取，查找时必须从头依次向后查找。 顺序文件缺点增加、删除记录操作困难；串结构相对简单。 索引文件解决可变长记录不能随机存取的问题。 建立索引表，每条记录对应一个索引项。索引表本身是定长记录的顺序文件，可以快速找到第 $$i$$ 条记录对应 ...

3.1内存管理概念3.1.1_1内存的基础知识内存可以存放数据。程序执行前需要先放到内存中才能被 $CPU$ 处理，起到缓存 $CPU$ 与硬盘之间速度差异的作用。 一、什么是内存，有何作用 存储单元、内存地址的概念和联系 按字节编址 $vs$ 按字编址 二、进程运行的基本原理1. 指令的工作原理指令由操作码 + 若干参数（可能包含地址参数）构成。 2. 逻辑地址（相对地址） $vs$ 物理地址（绝对地址） 逻辑地址：相对于模块起始位置的地址，从 $0$ 开始编号，也叫相对地址。 物理地址：内存中真实的绝对地址。 3. 从写程序到程序运行 编辑：程序员编写源代码文件 $*.c$。 编译：编译程序将源代码编译为若干目标模块，将高级语言翻译为机器语言，生成 $*.o$。 链接：链接程序将一组目标模块、所需库函数链接在一起，生成完整装入模块，形成完整的逻辑地址，生成 $*.exe$。 装入（装载）：装入程序将装入模块放入内存运行，完成逻辑地址到物理地址的映射。 4. 三种链接方式 静态链接程序运行之前，把各目标模块与所需库函数链接成一个完整可执行装入模块，程序运行后不可拆分。 装入时 ...

2.1 进程与线程2.1.1 程序与进程 程序：是静态的，存放在磁盘里的可执行文件，是一系列指令集合。 进程（Process）：是动态的，是程序的一次执行过程。 同一个程序多次执行会对应多个进程。 2.1.2 进程的组成更确切的说，应该是进程实体(进程映像)的组成。进程实体由 $PCB$、程序段、数据段三部分组成。 $PCB$：进程控制块，是给操作系统用的，$PCB$ 是进程存在的唯一标志。当进程被创建时，操作系统为其创建 $PCB$，当进程结束时，会回收其 $PCB$。操作系统对进程进行管理工作所需的信息都存放在 $PCB$ 中。 进程描述信息 进程标识符 $PID$ 用户标识符 $UID$ 进程控制和管理信息 $CPU$、磁盘、网络流量使用情况统计 进程当前状态：就绪态/阻塞态/运行态 资源分配清单 正在使用哪些文件 正在使用哪些内存区域 正在使用哪些 $I/O$ 设备 处理机相关信息 如 $PSW$、$PC$ 等各种寄存器的值，用于实现进程切换 程序段：程序的代码（指令序列），是给进程自己用的。 数据段：运行过程中产生的各 ...

本blog考研操作系统主体内容由小白兔友情提供 1.1 操作系统的基本概念 1.1.1 操作系统的定义操作系统（Operating System，OS）是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配；以提供给用户和其他软件方便的接口和环境；它是计算机系统中最基本的系统软件。 1.1.2 操作系统的功能和目标资源的管理者（四大管理功能） 处理机管理：管理 $CPU$，负责进程调度、分配处理器资源 存储器管理：管理内存，负责内存分配、地址映射、内存保护与扩充 文件管理：管理文件，负责文件的存取、共享、保护，管理外存 设备管理：管理 $(I/O)$ 外设，负责设备分配、缓冲管理等 向上层提供服务（接口分类）操作系统向上提供三类接口，供不同对象使用： 给普通用户使用：用户接口（命令接口） 联机命令接口（交互式命令接口） 实例：$Windows$ 系统的 $cmd$ 命令提示符。 特点：用户输入一条命令，操作系统立刻执行、给出反馈，交互式实时操作。 脱机命令接口（批处理命令接口） 实例：$Windows$ 批处理 .bat 脚本文件。 特点 ...

7.1 I/O系统基本概念（*） 21年大纲已删除该内容 基本概念 I/O接口：又称 I/O 控制器、设备控制器，负责协调主机与外部设备之间的数据传输。 外部设备 7.2 I/O 接口 I/O接口的作用 数据缓冲：通过数据缓冲寄存器（DBR）达到主机和外设工作速度的匹配 错误或状态监测：通过状态寄存器反馈设备的各种错误、状态信息，供CPU查用 控制和定时：接收从控制总线发来的控制信号、时钟信号 数据格式转换：串-并、并-串 等格式转换 与主机和设备通信：实现 主机—I/O接口—I/O设备 之间的通信 I/O接口的工作原理 命令字也可被称为“控制字” 接口与端口 I/O接口的类型 7.3 I/O 方式 程序查询方式 独占查询：CPU \(100\%\) 的时间都在查询I/O状态，完全串行 定时查询：在保证数据不丢失的情况下，每隔一段时间CPU就查询一次I/O状态。查询的间隔内CPU可以执行其他程序 程序中断方式 中断的作用和原理 中断判优 中断处理过程 单重 ...

6.1 总线概述 基本概念：总线是一组能为多个部件分时共享的公共信息传送线路。 总线的分类 按数据传输方式： 串行总线 并行总线 按总线功能： 片内总线 系统总线 数据总线 地址总线 控制总线 通信总线 按时序控制方式： 同步总线 异步总线 系统总线的结构 总线的性能指标 6.2 总线事务和定时