• 进阶:/
• 6、全排列 next_permutation 康托展开STL 常见算法
• 7、回溯
• 2、C++ 输入输出（包括流、文件） • 8、DFS、BFS、hash表
• 3、C++常用泛型：list vector stack map • 9、数学上的有：辗转相除（两行
•
9、数学：线段交点、多角形面积公式 等
排列组合
排列组合
公式
二项式定理
a的n次幂，超范围处理
较小的数可以直接相乘求出幂指数，一旦指数超出范围，则溢出 处理方式1：在程序运行中对p取余（p常取一个质数），结果为a^n取余。 处理方法2：当指数过大时，方法1不能解决，使用分治法
例题：素数计算超范围
例题：最大买不到的数目
出现连续4次(a次)能买到，之后的就都可以 买到，最大不能买到的数字就是这之前的数
比酒量
利用浮点数近似相等
通分，转为整数运算
保留分数形式， 不进行运算！
有理数是整数和分数的集合。 有理数：整数或有限小数或无限循环小数； 无理数：无限不循环小数 任何一个有理数，都可以表示成 分数 形式
整数的基本性质
• 素数、和数、整除、余数、最大公约数、最
小公倍数
• 互质的两个数的最大公约数是1，两个数如果
数论和组合数学知识
高华玲 主讲 2018.12.3
穷举法（暴力破解）
穷举法（暴力破解）
穷举法（暴力破解）
浮点数不能直接使用==来判断。 因为计算机中是二进制表示，有可能是无限循环小数，导致 不能精确相等。
乘以10，避免小数
注意：啤酒2.3，饮料1.9，啤酒比饮料的少，求啤酒的数量。 答案有两组，应该取11，30这一组，啤酒的数量为11.
练习平台界面
基本概念
• 进制转换——十六进制 八进制 二进制 十进制 关系 • 全排列 • 序列求和，圆的面积，Fibonacci数列 • 回文数 • 杨辉三角 • 数列 • 字母图形
练习
蓝桥杯省赛知识点
• 刷题OJ：
• 4、暴力穷举
• 基础:https:///auth/login• 5、递归
字
高僧斗法-博弈论、递归
高僧斗法-续
解答--数论知识
剩余两堆相等的情况，就可以胜利，这样可以 学对方的取法。 对方必输的棋局：是一个集合，比如3，3，0； 1，2，3； 例子：
尼姆：利用整数性质 在二进制的纵行上的和为偶 数，则必赢。 把3变成1即可。
Nimm.java
学习社区：CSDN
• 练习： • /oj/problemset.html • 总结：
较小可以直接搜索尝试，如果数很大使用： 辗转相除法
a、b的最大公约数【a，b】， 转化为【b-a，a】的最大公约数， 进而转化为【b%a，a】的最大公约数。
一般的写法
辗转相除法
递归的写法
最小公倍数
• 思路1： 从较大的数b（例如b>a）开始找，然后查找2b，直到一个能
够整除a的数结束。
• 思路2：最小公倍数=a*b/最大公约数
https:///linmengmeng_1314/article/details/79533129
• 2018第九届蓝桥杯B组决赛(国赛)题解 • https:///nka_kun/article/details/80488297 • https:///weixin_37609825/article/details/81392687
内），素数等
国赛知识点
• 1、hash表
• 6、熟悉动态规划的各个典型：LCS、最
• 2、大数（高精度）加减乘除
长递增子串、三角剖分、记忆化dp
• 3、线段树
• 7、博弈类算法：博弈树，二进制法等。
• 4、并查集
• 8、双向广度搜索、A*算法，最小耗散
优先
•
5、图论相关算法：最短路(Floyd、 Dijstra,BellmanFord)、最小生成树 (prim,kruscal要用并查集)