二分查找

• 引入

  1、假设对于一个有序数列，例如 $\{1, 2, 3, 5, 5, 5, 8, 9\}$ (实际可能会很长)，我们要在里面查找某个元素的位置或其是否存在
  2、如果普通地使用循环遍历，那么时间复杂度为 $O(n)$ 常数级；但如果使用二分查找，时间复杂度仅为 $O(\log_2 n)$ 对数级，效率大大提升
  3、二分查找每次操作得到当前未比较序列的中间下标 $mid$，如果 $mid$ 对应的值满足(或不满足)条件，则对于有序数列而言，$mid$ 前面的一系列值都满足(或都不满足)条件，这样便一次查找了未比较序列的一半的元素，便可根据情况调整未比较序列的边界。重复以上操作，直到未比较序列都已经比较，整个序列便按照给定的条件分为了(满足条件/不满足条件)两个组别，根据实际情况返回下标即可

一维前缀和

• 例题引入

  1、设计一个程序，假如有一个已知长度和数据的数列(如 $\{1, 3, 7, 5, 2\}$ )，程序将 $m$ 次询问该数列的任意区间的区间和 $sum[p, q]$ (例如三次分别询问 $sum[2, 4]$、$sum[0, 3]$、$sum[3, 4]$)
  2、简单分析，我们可知如果每次都用循环直接累加，那么单次的时间复杂度为 $O(n)$ ；又因为需要$m$ 次询问，则程序的时间复杂度至少为 $O(n*m)$。显然当数据量较大时，程序的运行速度很慢。而前缀和的时间复杂度只需要 $O(n)$
  3、对于这类问题，我们可以通过前缀和来简化程序，具体如下

注：所有算法的排序原理动图请前往VisualGo观看或前往视频 1|视频 2学习原理

算法复杂度与稳定性

• 稳定性复杂度口诀

  1、插帽龟(插入、冒泡、归并)，它很稳(稳定性)，此外还有基你太稳(基数排序)
  2、插帽龟喜欢选帽插(选择、冒泡、插入)，插完就方了(平均时间复杂度 $O(n^2)$)
  3、快归队(快速、归并、堆)，$n$ 老二(平均时间复杂度 $O(n\log_2 n)$)

Cmake 简介

• Cmake 是什么

  1、Cmake是高级编译配置工具。当多个人要用不同的语言或者编译器开发一个项目，最终要输出一个可执行文件或共享库，这时候Cmake 的作用就凸显出来了
  2、Cmake的所有操作都是通过编译CMakeLists.txt所写内容来完成的
  3、学习Cmake的目的，是为了将来处理大型 C/C++/Java 项目做准备，其也是一种生成 Makefile 的工具

前置准备

• 前言及准备

  1、首先，请确保你已经根据VScode 基本环境配置文章学会了配置环境，并成功配置了 C/C++环境
  2、比起前文的方案使用GCC 编译器，本方案使用Clang + Cmake配置环境，因此需要在上方文章所给链接下载LLVM/Clang套件
  3、同MinGW-w64配置方法类似，将bin 目录添加到Path 环境变量中，确保在cmd中输入clang -v输出clang 版本号，配置完成后进入下面的步骤

引入

1、C 与 C++的数据类型表示范围有上限，有时会遇到一些特别大的数据量级，使用unsigned long long都无法表示
2、此时需要使用高精度算法，当然通常只用来表示数据和做一些简单运算
3、所谓高精度，就是用字符数组来模拟数据运算(运算过程大多模拟竖式运算)
4、下面将介绍一些常用的高精度算法

下载

Qt 中文官网

安装 Qt

• Qt 安装说明

1、安装 Qt，记住Qt 安装的路径，选择组件时，在Qt一栏选择需要的Qt 版本
2、其中 Qt 版本下选择的是对应的开发库，MSVC和MinGW两个编译器使用哪个就选中哪个，其余组件按需选择
3、此外最下方的开发工具，按需选择。其中Cmake和Ninja建议必选，如果使用MinGW还需要选择对应的 MinGw 版本

引入

• 引入

  1、算法竞赛是思维脑力的较量。一道好的算法题可以区分出好的算法程序(可以获得较高得分)和不那么好的算法程序(低分甚至零分)
  2、评价算法的优劣是有一套标准的。利用这套标准，可以在动手实践之前即可估计这种写法是否靠谱
  3、如果判断这套算法可能超时或超出内存限制而导致无法得分，则应该想想有没有更好的写法
  4、接下来便来学习如何评价一套算法