------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
XP02 DAY01：
1.算法的特性：
有穷性
确定性
可行性
零个或者多个输入
一个或者多个输出
2.时空复杂度：
时间复杂度
空间复杂度
大O记法简化规则：
①只保留最高阶
②若最高阶系数存在 且不是1，则删去该常数。
O(1)代表常数时间复杂度
时间复杂度由快到慢：常对幂指阶
3. 枚举算法
枚举算法是一种将 问题的所有可能结果一一列举，并用条件检验是否成立的解题思维。
枚举做题步骤：
①确定枚举对象
②确定枚举对象的取值范围
如果枚举对象存在等式关系，可以优化掉一层for循环
③条件检验是否成立 写在if语句里面。
4.前缀和数组
子段和-->前缀和 看竖线左边
比如求a[l]+ ~~~ a[r] 的和
l-1 |l~~~~~~r|
即PRE[R]-PRE[L-1]
5.差分数组
区间修改a[l]~~~~~ a[r] 每个元素 + c
|l~~~~r| +c 差分数组只修改两项 竖线右边
D[L]+=C;
D[R+1]-=C;
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
XP02 DAY02
二分查找算法
1. 概念
二分查找也称折半查找 (Binary Search) ，是在一组有序（升序/降序）的数据中查找一个元素，它是一种效率较高的查找方法。
2.二分查找步骤:
假设表中元素是按升序排列
重复做的事情：
得到中间元素位置mid
a[mid] 和 目标元素 x 作比较
① a[mid] == x : 找到目标元素，则查找成功
② a[mid] > x : 往a[mid]左边找，更新右端点
② a[mid] < x : 往a[mid]右边找，更新左端点
结束条件：直到子表不存在为止 即l>r
执行条件：子表存在 即 l<=r
不知道重复操作执行多少次，但知道什么时候结束---> while循环
3.代码实现：
二分求下界：
1.下界：
找到首个 ≥x 的元素位置，如果不存在，返回 N+1
2.二分求下界步骤:
假设表中元素是按非降序排列
重复做的事情：
得到中间元素位置 mid
a[mid] 和目标元素x 作比较
① a[mid] == x : 保存答案，往a[mid]左边找，更新右端点
② a[mid] > x : 保存答案，往a[mid]左边找，更新右端点
③ a[mid] < x : 往a[mid]右边找，更新左端点
结束条件：直到子表不存在为止 即l>r
执行条件：子表存在 即 l<=r
不知道重复操作执行多少次，但知道什么时候结束--->while循环
3.代码实现：
二分求上界：
1.上界：
找到首个 >x 的元素位置，如果不存在，返回 N+1
2.二分求上界步骤:
重复做的事情：
得到中间元素位置mid
a[mid]和 目标元素x 作比较
① a[mid] == x : 往a[mid]右边找，更新左端点
② a[mid] < x : 往a[mid]右边找，更新左端点
③ a[mid] > x : 保存答案，往a[mid]左边找，更新右端点
结束条件：直到子表不存在为止 即l>r
执行条件：子表存在 即 l<=r
不知道重复操作执行多少次，但知道什么时候结束--->while循环
3.代码实现：
STL二分算法
1.LOWER_BOUND()
lower_bound 找到首个 ≥x 的元素位置，如果不存在，返回 N+1
头文件：algorithm
2.UPPER_BOUND()
upper_bound 找到首个 >x 的元素位置，如果不存在，返回 N+1
头文件：algorithm
二分上下界应用：
计算 x 在有序序列中出现次数= x的上界 – x的下界
二分查找应用
结构体数组也可以使用二分查找
// 结构体：存储每个位置的瓶子数和原始位置编号
二分查找瓶子个数为x位置 结构体数组 先按照 瓶子个数 从小到大排序
问X是否在A数组里面出现 或者 X在A数组里面出现次数
---->a数组排序后 用 x的上界-x的下界可以求出x的个数
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
XP02 DAY03：
只要满足单调性 / 二段性就能使用二分
二分答案解题思路：
确定枚举思路，通过二分答案对枚举思路进行优化
1.确定枚举对象： 一般求什么就枚举什么；
2.确定枚举范围：枚举边界，可能的最小值和最大值；
3.确定 CHECK 函数写法！
通常根据限定内容来写check；check 需要先手动模拟，然后用代码实现模拟过程
4.判断答案是否满足单调性：
能否通过中间位置是否可行，去掉其中一半的可能性，缩小检查范围
5.对枚举答案进行二分：
①答案 越大越好：二分答案求上界；
②答案 越小越好：二分答案求下界；
二分答案求上界 答案越大越好
也可能 midmidmid为数组下标 是需要对a[mid]a[mid]a[mid]做检查的哦
二分答案求下界 答案越小越好
也可能 midmidmid为数组下标 是需要对a[mid]a[mid]a[mid]做检查的哦
注意：
数据类型不确定会不会超过int类型 就使用long long 类型
int 最大值: 2312^{31}231 -1 即 2147483647
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
XP02 DAY04：
一.进制转换：
1.进制：
十进制：逢10进1
数码：0~9
如：123
二进制：逢2进1
数码：0~1
如：1010
八进制：逢8进1
数码：0~7
如：72
十六进制：逢16进1
数码： 0 1 2 3 4 5 6 7 8 9 A B C D E F
如：AB
2.进制转换：
K进制 转10进制
①先标单位
②每个位置上数字*单位 累加求和
按权展开，累加求和
例题：
1011.110(2) 转10进制
答案：十进制为11.75 可以练习一下
10进制 转K进制
整数部分:除k取余，直到商为0，余数逆序排列;
小数部分:乘k取整，直到小数部分为0，每次取的整数顺序排列。
例题：
42.125(10) 转2进制
答案：2进制为101010.001 可以练习一下
二.前中后缀表达式：
1.概念
中缀表达式是指运算符在操作数中间：a + b
前缀表达式 (波兰式) 是一种没有括号的一种算术表达式，且运算符在操作数的前面： + a b
后缀表达式 (逆波兰式) 是一种没有括号的一种算术表达式，且运算符在操作数的后面： a b +
中缀--->前缀
a + b * c - ( d + e )
①对所有的运算按优先级增补括号 ((a + (b * c)) - (d + e))
②从内到外将运算符移动到两操作数之前：
( - ( + a ( * b c) ) ( + d e) )
③去掉括号：- + a * b c + d e
转换完成
中缀--->后缀
a + b * c - ( d + e )
①对所有的运算按优先级增补括号 ((a + (b * c)) - (d + e))
②从内到外将运算符移动到两操作数之后： ((a (b c *) +) (d e +) - )
③去掉括号：a b c * + d e + -
转换完成
后缀表达式求值：3 5 2 * +
运算规则：
1.从左往右扫描表达式；（操作数在哪边从哪边开始扫描）
2.遇到运算符，运算符放在左边的两个数中间进行运算(运算符左边第一个数字为右操作数，运算符左边第二个数字为左操作数)，并将计算结果作为下次计算的操作数。
后缀表达式转中缀表达式
①从左往右扫描表达式遇到运算符忍住不计算列式子+括号
②去除不影响运算优先级的括号
前缀表达式求值：+ 3 * 5 2
1.从右往左扫描表达式；（操作数在哪边从哪边开始扫描）
2.遇到运算符，运算符放在右边的两个数中间进行运算(运算符右边第一个数字为左操作数，运算符右边第二个数字为右操作数)，并将计算结果作为下次计算的操作数。
前缀表达式转中缀表达式
①从右往左扫描表达式 遇到运算符忍住不计算列式子+括号
②去除不影响运算优先级的括号
前缀转后缀： ①前缀转中缀；②中缀转后缀。
三. 原码、反码、补码
计算机中是以补码的方式存储
原码：
十进制转二进制
最高位 符号位 0 正数 1 负数
10001101
反码：
原码符号位不变 其余位取反
补码：
反码+1
四. 位运算：
1.按位与 &：
将两个二进制数低位对齐，不足高位补零。对两个数字按位进行比较
同1才1否则为0
按位或 |：
将两个二进制数低位对齐，不足高位补零。对两个数字按位进行比较，同0才0否则为1
按位非 ~：
将一个二进制数每一位取反，0 变 1， 1 变 0。
~x=-(x+1)
按位异或 ^：
消消乐 两位 相同时为0，不同时为1。
按位右移 >>:
运算规则， >> a 就将二进制数右移 a 位，高位补零，低位丢弃
按位左移 <<
运算规则: << a 就将二进制数左移 a 位，高位丢弃，低位补零
排列组合
加法原理 -- 每一类方法都可以独立完成任务
做一件事，完成它可以有 n 类办法。第一类办法有 m1m_1m1 种方法，第二类办法有 m2m_2m2 种方法 ... 在第 n 类办法有 mnm_nmn 种方法，那么完成这件事共有 N=m1m_1m1 +...+mnm_nmn 种不同的方法。
乘法原理 -- N个步骤都做了才可以完成任务
做一件事，完成它需要分成 n 个步骤。第一步有 m1m_1m1 种方法，第二步有 m2m_2m2 种方法 ... 在第 n 步办法有 mnm_nmn 种方法，那么完成这件事共有 N=m1m_1m1 *... * mnm_nmn 种不同的方法。
排列：--顺序重要
从 n 个不同元素中，任取 m(m≤n) 个元素，按照一定的顺序排成一列，叫做从 n 个不同元素中取出 m 个元素的一个排列。
AnmA{n}^{m}Anm:
站在位置角度思考： n∗(n−1)∗(n−2)∗ (n−m+1)n*(n-1)* (n-2)*~~~(n-m+1)n∗(n−1)∗(n−2)∗ (n−m+1)
Anm=n!(n−m)!A_{n}^{m} = \frac{n!}{(n-m)!}Anm =(n−m)!n!
组合：--顺序不重要
从 n 个不同元素中，任取 m(m≤n) 个元素组合
助记： 排列数 /"膨胀系数"
一个组合有m人 "膨胀系数" 为m!m!m!
***=Anmn!C_{n}^{m} = \frac {A_{n}^{m}}{n!} *** =n!Anm
***=n!m!(n−m)!C_{n}^{m}=\frac{n !}{m!(n-m)!} *** =m!(n−m)!n!
排列组合方法
1. 特殊优先
2. 捆绑法与插空法
3. 排除法
4. 隔板法
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
XP02 DAY05:动态规划基础
一.概念：
动态规划（DynamicProgrammingDynamic ProgrammingDynamicProgramming）是一种多阶段决策问题的方法。它通过将原问题分解为若干个子问题，并这些子问题只解决一次，将结果保存起来，避免重复计算，提高了算法效率。
动态规划能解决的问题类型：方案数问题、最优解问题等
二.解题步骤：
1.思考问题 -> 创建DP数组 (95%的问题 -> 问题问什么，DP数组就是什么含义)
2.求状态转移方程：
如果你是小码君，一觉醒来你出现在了某个位置
小码君脑容量有限，只能想起来最后一步怎么走的/最后一步做的什么选择
根据最后一步怎么走的/最后一步做的什么选择 把大问题转换为已经求得的小问题。
3.初始值：
问题足够小可以直接解决/不能用状态转移方程来推。
CODING
三.分类
1.方案数问题：
所有类 方案数都要
2.最优解问题：
所有类 取一个最优的
注意dp数组初始值：
极小值问题 dp数组初始值大的大
极大值问题 dp数组初始值小的小
3.经典例题：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
XP02 DAY06:栈 队列 递归
一. 栈
1.概念：
栈（stack）又名堆栈，是限定仅在表尾进行插入和删除操作的线性结构，特点为：先进后出（FILO）。
2.数组模拟栈--了解
标准模板库(Standard Template Library，STL)就是一些常用数据结构（栈、队列等）和算法（sort、swap等）的模板的集合。有了STL，不必再写太多的标准数据结构和算法，且可获得非常高的性能。
3.栈的 STL 模板
使用stack应先添加头文件"stack"
格式： stack<类型名> 栈名;
栈(STACK)常用函数:
① PUSH(X)：将X入栈(无返回值)
② POP()：弹出栈顶元素(无返回值)
③ TOP()：获得栈顶元素(有返回值)
④ EMPTY()：检测栈是否为空，返回TRUE为空，FALSE为非空(有返回值)
⑤ SIZE()：返回栈中元素个数(有返回值)
//无返回值直接调用，有返回值调用后保存/输出。
注意：栈无法直接遍历
例如：
4.栈的使用场景：看到先进后出/后进先出 时想到栈
二. 队列
1.概念：
队列（queue）是只允许在一端进行插入，而在另一端进行删除的线性结构。特点为：先进先出 (FIFO)。
2.数组模拟队列--省略
3. 队列的 STL 模板 (循环队列)
队列(queue)的定义：
使用queue应先添加头文件"queue"。
格式：queue<类型名> 队列名;
队列(QUEUE)常用函数：
① PUSH(X)：将X入队(无返回值)
② POP()：令队首元素出队(无返回值)
③ FRONT()：获得队首元素(有返回值)
④ BACK()：获得队尾元素(有返回值)
⑤ EMPTY()：检测队列是否为空，返回TRUE为空，FALSE非空(有返回值)
⑥ SIZE()：返回队列元素个数(有返回值)
//无返回值直接调用，有返回值调用后保存/输出。
例如：
4.队列的使用场景：看到先进先出 时想到队列
三. 递归
1.递归函数的概念：
在程序设计领域，递归是指函数（或方法）直接或间接调用自身的一种操作
递归必须要有一个终止条件，这又称作递归边界（递归出口），否则将无限死循环下去了！
2.递归适用场景：
当一个大问题无法直接得到答案，你看到大问题可以变成小问题，大问题和小问题解决方法相同，问题足够小可以直接解决--->想到递归
①问题足够小可以直接解决-->递归边界
②大问题可以变成小问题-->递归公式
因为解决方法一样，可以先写一个解决方法的函数框架
3.经典例题：
①斐波那契数列
斐波那契数列的第 n 项 我无法一口说出答案，但是可以变成稍小的问题：第n-1项 + 第n-2项；
第n-1项 可以变成第第n-2项 + 第n-3项； 大问题和稍小问题处理方法一样，问题足够小 第1项第2项可以直接说出答案1---->使用递归
先写递归函数的框架：给它对应项数n，它返回给我第n项的值 返回值为int类型。
主函数里面：
②辗转相除法求2个数字的最大公约数
Gcd(a,b) 即a和b的最大公约数
问Gcd(a,b) 我无法一口说出答案，但是
根据被除数和除数的最大公约数 等价于 除数和余数的最大公约数即 Gcd(a,b)等价于Gcd(b,a%b)
我可以把大问题变成稍小问题, 大问题和稍小问题处理方法一样，问题足够小即除数为0
因为 0和任何正整数x的最大公约数为x 即Gcd(x,0)为x 可以 直接说出答案x---->使用递归
或者 递归边界：
两个数字的最小公倍数= 两个数字的乘积 / 两个数字的最大公约数
注意：递归是双向过程，①大问题---->小问题 到达递归边界后触底反弹，②小问题--->大问题。
递归前输出为 大问题---->小问题时输出
递归后输出为 到达递归边界后小问题---->大问题时输出
比如 十进制转二进制
