重要干货
1.计算运行时间
2.枚举子集
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
进制数
* 10转2
逢2取余，逆序排列
十进制小数转换成二进制小数采用”乘2取整，顺序排列“
* 10转8
逢8取余，逆序排列
十进制小数转换成八进制小数采用”乘8取整，顺序排列“
0.125∗8=1.0⋅⋅⋅00.125*8=1.0 ···00.125∗8=1.0⋅⋅⋅0
枚举算法
三要素：枚举对象、枚举范围、判定条件
特点：简单粗暴
三位偶数
> 题目描述
> 给出一个正整数 n 和一个长度为 n 的数组 a。其中每个元素是一个数字（0−9）。数组中可能存在重复元素。
> 你需要找出 所有 满足下述条件且 互不相同 的整数：
> ① 该整数由 a 中的三个元素按 任意 顺序 依次连接 组成。
> ② 该整数不含 前导零
> ③ 该整数是一个 偶数
> 你需要输出所有 互不相同 的整数按 递增顺序 排列。
> 输入格式
>
> > 第一行输入一个整数 n ，(3<=n<=100 )
> > 第二行输入n个整数到数组 a 中。(0<=a[i]<=9)
> 输出格式
>
> > 输出所有互不相同的整数按 递增顺序 排列，每个数字之间使用空格分隔。
> 样例组输入#1
>
> > 3
> > 2 0 1
>
> 样例组输出#1
>
> > 102 120 210
枚举元组
> 题目描述
> nnn 元组是指由 nnn 个元素组成的序列。例如 (1,1,2)(1,1,2)(1,1,2) 是一个三元组、(233,254,277,123)(233,254,277,123)(233,254,277,123) 是一个四元组。
> 给定 nnn 和 kkk，请按字典序输出全体 nnn 元组，其中元组内的元素是在 [1,k][1, k][1,k] 之间的整数。
> 「字典序」是指：优先按照第一个元素从小到大的顺序，若第一个元素相同，则按第二个元素从小到大……依此类推。详情参考样例数据。
> 输入格式
> > 仅一行，两个正整数 n,kn, kn,k。
> 输出格式
> > 若干行，每行表示一个元组。元组内的元素用空格隔开。
> 样例 #1
> > 样例输入 #1
> >
> > > 2 3
> > 样例输出 #1
> >
> > > 1 1
> > > 1 2
> > > 1 3
> > > 2 1
> > > 2 2
> > > 2 3
> > > 3 1
> > > 3 2
> > > 3 3
> 样例 #2
> > 样例输入 #2
> >
> > > 3 3
> > 样例输出 #2
> >
> > > 1 1 1
> > > 1 1 2
> > > 1 1 3
> > > 1 2 1
> > > 1 2 2
> > > 1 2 3
> > > 1 3 1
> > > 1 3 2
> > > 1 3 3
> > > 2 1 1
> > > 2 1 2
> > > 2 1 3
> > > 2 2 1
> > > 2 2 2
> > > 2 2 3
> > > 2 3 1
> > > 2 3 2
> > > 2 3 3
> > > 3 1 1
> > > 3 1 2
> > > 3 1 3
> > > 3 2 1
> > > 3 2 2
> > > 3 2 3
> > > 3 3 1
> > > 3 3 2
> > > 3 3 3
> 提示
> 对于 100%100\%100% 的数据，有 n≤5,k≤4n\leq 5, k\leq 4n≤5,k≤4。
代码如下:
全排列
代码如下：
重难点：二进制枚举
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
埃氏
时间复杂度：O(nloglogn)O(nlog^{log^n})O(nloglogn)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
经典例题
01.最长山脉
> 题目描述
> 给出一个正整数 n 和一个长度为 n 的数组 a。
> 如果满足下面条件，我们称之为山脉：
> 存在下标 i(0<i<n)i(0<i<n)i(0<i<n)，满足 a[0]<a[1]<...<a[i?1]<a[i]a[0]<a[1]<...<a[i?1]<a[i]a[0]<a[1]<...<a[i?1]<a[i] 并且 a[i]>a[i+1]>...>a[n−1]a[i]>a[i+1]>...>a[n-1]a[i]>a[i+1]>...>a[n−1]。
> 换句话说：iii这个位置是最大值，两侧依次递减。比如 111 222 555 333 111 就是一个长度为 5 的山脉。
> 请你找出最长的山脉，如果不存在输出 0。
> 输入格式
>
> > 第一行输入一个整数 nnn ，(3<=n<=105)(3<=n<=10^5)(3<=n<=105)
> > 第二行输入n个整数，a[0],a[1],a[2].....a[n−1]a[0],a[1],a[2].....a[n-1]a[0],a[1],a[2].....a[n−1]。(0<=a[i]<=104)(0<=a[i]<=10^4)(0<=a[i]<=104)
> 输出格式
>
> > 输出最长的山脉，如果不存在输出 0。
> 样例组输入#1
>
> > 7
> > 2 1 4 7 3 2 5
> 样例组输出#1
>
> > 5
接下来是正解：
02.# [COCI2008-2009 #2] PERKET
> 题目描述
> Perket 是一种流行的美食。为了做好 Perket，厨师必须谨慎选择食材，以在保持传统风味的同时尽可能获得最全面的味道。你有 nnn 种可支配的配料。对于每一种配料，我们知道它们各自的酸度 sss 和苦度 bbb。当我们添加配料时，总的酸度为每一种配料的酸度总乘积；总的苦度为每一种配料的苦度的总和。
> 众所周知，美食应该做到口感适中，所以我们希望选取配料，以使得酸度和苦度的绝对差最小。
> 另外，我们必须添加至少一种配料，因为没有任何食物以水为配料的。
> 输入格式
> > 第一行一个整数 nnn，表示可供选用的食材种类数。
> > 接下来 nnn 行，每行 222 个整数 sis_isi 和 bib_ibi ，表示第 iii 种食材的酸度和苦度。
> 输出格式
> > 一行一个整数，表示可能的总酸度和总苦度的最小绝对差。
> 样例 #1
> > 样例输入 #1
> >
> > > 1
> > > 3 10
> > 样例输出 #1
> > > 7
> 样例 #2
> > 样例输入 #2
> > > 2
> > > 3 8
> > > 5 8
> > 样例输出 #2
> >
> > > 1
> 样例 #3
>
> > 样例输入 #3
> >
> > > 4
> > > 1 7
> > > 2 6
> > > 3 8
> > > 4 9
> > 样例输出 #3
> >
> > > 1
> 提示
>
> > 数据规模与约定
> > 对于 100%100\%100% 的数据，有 1≤n≤101 \leq n \leq 101≤n≤10，且将所有可用食材全部使用产生的总酸度和总苦度小于 1×1091 \times 10^91×109，酸度和苦度不同时为 111 和 000。
> 说明
* 本题满分 707070 分。
* 题目译自 COCI2008-2009 CONTEST #2 PERKET，译者 @mnesia。
03.水仙花数
> 【模拟枚举】水仙花数
> 题目描述
> 水仙花数是指一个 3 位数，它的每个位上的数字的 3次幂之和等于它本身。例如：
> 13+53+33=1531^3 + 5^3 + 3^3 = 15313+53+33=153，小码君对水仙花数很感兴趣，他想知道100至999范围内的所有水仙花数，从小到大输出所有的水仙花数
> 提示
> 数据范围：
> > 找出100至999范围内的所有水仙花数
> 样例说明：
> > 100至999范围内的水仙花数依次输出，每一个数占一行，第一个数为153
> 输入格式
>
> > 无输入
> 输出格式
>
> > 从小到大输出所有的水仙花数，每一个水仙花数占一行
04.找钱
> 题目描述
>
> > 将 n 元人民币换成 1 元、2 元、5 元的零钱，编程计算共有多少种方法？
> 输入格式
>
> > 输入一行，包含一个整数 n。(0<n<1000)
> 输出格式
> 输出一行，包含一个整数。
> 样例组输入
>
> > 5
> 样例组输出
>
> > 4
代码如下：
05.统计质数个数
06.统计三元组数量
> 题目描述
> 给出一个长度为 n 的数组，以及 a，b ，c 三个整数。请你统计满足下面条件的三元组数量。
> 三元组 (arr[i]，arr[j]，arr[k]) 需要满足下列全部条件:
> 0 <= i < j < k < arr.length
> |arr[i] - arr[j]| <= a
> |arr[j] - arr[k]| <= b
> |arr[i] - arr[k]| <= c
> 注意：其中 |x| 表示 x 的绝对值。
> 输入格式
>
> > 第一行输入四个整数，n，a，b，c 。n ≤ 100，0 ≤ a，b，c ≤ 1000。
> > 第二行输入 n 个整数，0 ≤ arr[i] ≤ 1000。
> 输出格式
>
> > 输出一个整数，满足条件的三元组数量。
> 样例组输入
>
> > 5 7 2 3
> > 3 0 1 1 9 7
> 样例组输出
>
> > 4
