蓝桥杯备赛(持续更新)

news/2024/11/7 7:15:30/

16届蓝桥杯算法类知识图谱.pdf

1. 格式打印

%03d:如果是两位数,将会在前面添上一位0

%.2f:会保留两位小数

如果是long,必须在数字后面加上L

2. 进制转化

2.1. 十进制转任意进制:

十进制转任意进制时,将这个十进制数除以进制数,比如2(也就是十进制转二进制),得到商和一个从0~1的余数,然后再以这个商为被除数,除了进制数2,继续得到商和一个从0~1的余数。以此方式不断相除,直到得到的商为0为止。此时,得到若干个余数,把这些余数按从后到先的顺序排列起来,那么这个排列起来的值即为该十进制转换成二进制的值。计算如图所示:

最后得到的余数为二进制的非零的最高位,最先得到的余数为二进制的最低位,可知:十进制数9转换成二进制数为1001。

2.2. 任意进制转十进制:

任意进制转十进制时,以二进制数1001为例:该进制的最低位(右一)的值1就表示实际的十进制值1,次低位(右二)的值0表示进制数2的一次方的0倍即为0,次次低位(右三)的值0表示进制数2的二次方4的0倍即为0,最高位(左一)的值1表示进制数2的三次方8的1倍即为8,以此类推,将每位得到的十进制数相加得到9,该和即为二进制数1001对应的十进制数。计算如图所示:

3. 一维前缀和

  1. 快速求解某区间内的各种形式的和即可使用
  2. 使用迭代求和
sum[i]=sum[i-1]+num[i]

4. 一维差分

  1. bi = ai-ai-1

其中b1 = a1

  1. 如果cb的前缀和:即,ci = ci-1 + bi
  2. 那么c就是原数组a

4.1. 常见性质

  1. 差分数组都是0,说明原数组每个元素都相同
  2. 差分数组的前缀和就是原数组
  3. 如果bl + d 与 br+1 - d同时作用,则c数组就是原数组ai+d的结果
  4. 对差分的某一个位置减一等价于对原数组此位置及以后的位置减一

4.2. 特殊数列

数列: 1 4 10 20 35

对应的差分数列:1 3 6 10 15

差分数列是等差数列

5. 快读模板

static FastReader in = new FastReader(); // 创建一个静态的 FastReader 对象,用于处理输入
static PrintWriter out = new PrintWriter(System.out); // 创建一个静态的 PrintWriter 对象,用于输出数据// FastReader 类,用于处理高效的输入
static class FastReader {static BufferedReader br; // 静态的 BufferedReader,用于高效读取输入static StringTokenizer st; // 静态的 StringTokenizer,用于将输入字符串分割为标记// 构造函数,初始化 BufferedReader 以从标准输入读取数据FastReader() {br = new BufferedReader(new InputStreamReader(System.in)); // 使用 System.in 作为输入流初始化 BufferedReader}// next() 方法,返回下一个字符串标记String next() {String str = ""; // 定义一个空字符串,用于存储读取到的行// 如果 StringTokenizer 为 null 或没有更多标记可读取,读取新行while (st == null || !st.hasMoreElements()) {try {str = br.readLine(); // 使用 BufferedReader 读取一整行输入} catch (IOException e) { // 捕获可能的 I/O 异常throw new RuntimeException(e); // 如果发生异常,抛出运行时异常}st = new StringTokenizer(str); // 将读取到的行传递给 StringTokenizer 进行分割}return st.nextToken(); // 返回 StringTokenizer 的下一个标记}// nextInt() 方法,返回下一个整数输入int nextInt() {return Integer.parseInt(next()); // 使用 next() 方法读取字符串并转换为整数}// nextDouble() 方法,返回下一个双精度浮点数输入double nextDouble() {return Double.parseDouble(next()); // 使用 next() 方法读取字符串并转换为双精度浮点数}// nextLong() 方法,返回下一个长整数输入long nextLong() {return Long.parseLong(next()); // 使用 next() 方法读取字符串并转换为长整数}
}
  1. StringTokenizer 的分词作用
    • StringTokenizer 的作用是将一行输入拆分成多个标记,便于依次处理(比如单词或数字)。
    • 可以理解为:st 是一个“分词器”,根据空格等分隔符来划分输入。
  1. 总结记忆方法:
    1. 输入原理BufferedReader + StringTokenizer = 快速读取并分词。
    2. 输出原理PrintWriter = 快速输出。
    3. 类型方法next() 负责读取字符串标记,nextInt() 等方法负责类型转换。

6. 二维差分

二维差分是在一维差分的基础上推导的公式。

之前学过,差分数组的前缀和就是原数组,由此进行推导即可。

使用 s表示前缀和数组,a表示原数组。

则:

s(i,j) = a(i,j) + s(i-1,j) + s(i,j-1) - s(i-1,j-1)

那么我们现在要求二维差分数组,就:

  1. 原数组看做差分数组
  2. 前缀和看做原数组

具体原因见下图。

那么,我们要求差分(定为 b),就将差分移到左边(原式中的 a):

a(i,j) = s(i,j) - s(i-1,j) - s(i,j-1) + s(i-1,j-1)

更换为正确的字母后:

b(i,j) = a(i,j) - a(i-1,j) - a(i,j-1) + a(i-1,j-1)

上式就是二维差分的公式。

要求原数组的话,就将 b 求前缀和即可。

6.1. 二维数组对于某个区域加常数 c

使用二维差分数组。

b(x1,y1) += c;

b(x1,y2+1) -= c;

b(x2+1,y1) -= c;

b(x2+1,y2+1) += c;(多减了一次)

之后再对 b 数组求前缀和得到二维原数组。


http://www.ppmy.cn/news/1544993.html

相关文章

基于Zynq FPGA对雷龙SD NAND的测试

一、SD NAND 特征 1.1 SD 卡简介 雷龙的 SD NAND 有很多型号,在测试中使用的是 CSNP4GCR01-AMW 与 CSNP32GCR01-AOW。芯片是基于 NAND FLASH 和 SD 控制器实现的 SD 卡。具有强大的坏块管理和纠错功能,并且在意外掉电的情况下同样能保证数据的安全。 …

IDEA构建JavaWeb项目,并通过Tomcat成功运行

目录 一、Tomcat简介 二、Tomcat安装步骤 1.选择分支下载 2.点击下载zip安装包 3.解压到没有中文、空格和特殊字符的目录下 4.双击bin目录下的startup.bat脚本启动Tomcat 5.浏览器访问Tomcat 6.关闭Tomcat服务器 三、Tomcat目录介绍 四、WEB项目的标准结构 五、WEB…

【Linux】Linux管道揭秘:匿名管道如何连接进程世界

🌈个人主页:Yui_ 🌈Linux专栏:Linux 🌈C语言笔记专栏:C语言笔记 🌈数据结构专栏:数据结构 🌈C专栏:C 文章目录 1.什么是管道 ?2. 管道的类型2.1 匿…

国内短剧源码短剧系统搭建小程序部署H5、APP打造短剧平台

​在当今的互联网时代,短剧作为一种新兴的娱乐形式,受到了越来越多用户的喜爱。为了提供更好的用户体验和满足用户需求,一个好的短剧系统需要具备多元化的功能和优质的界面设计。 本文将介绍国内短剧源码短剧系统搭建小程序部署H5、APP所需的…

Git进阶(十八):git rebase详解

文章目录 一、前言二、rebase 图解三、应用示例四、重建提交历史五、rebase VS merge六、拓展阅读 一、前言 rebase 使用方法 git rebase [基节点] git rebase [基节点] [待变基节点]rebase后面的参数可以是两个,也可以是一个,当rebase为一个参数的时…

Harmony OS 如何实现 C++ NATIVE YUV420(其他数据格式如BGRA等)自渲染

在HarmonyOS下自渲染视频数据 在本文中,我们将介绍如何在HarmonyOS下自渲染视频数据。我们将实现包括创建本地窗口、设置缓冲区选项、请求缓冲区、处理视频帧数据以及刷新缓冲区等步骤。 环境准备 在开始之前,请确保您已经安装了HarmonyOS的开发环境&…

scala Map训练

Map实训内容: 1.创建一个可变Map,用于存储图书馆中的书籍信息(键为书籍编号,值为包含书籍名称、作者、库存数量的元组),初始化为包含几本你喜欢的书籍信息。 2.使用 操作符添加两本新的书籍到图书馆集合中。 3.根据书籍编号查询某一本特定的书籍信息&…

初学Java基础Day22---枚举

一,枚举的使用 1.枚举的引入 案例: //案例:枚举的引入 //需求:编写季节类(season),该类只有四个对象(Spring,summer,autumn,winter)public class Test01{public static void main(String[] args){Season spring Sea…