引入
贪心算法（英语：greedy algorithm），是用计算机来模拟一个「贪心」的人做出决策的过程。这个人十分贪婪，每一步行动总是按某种指标选取最优的操作。而且他目光短浅，总是只看眼前，并不考虑以后可能造成的影响。
可想而知，并不是所有的时候贪心法都能获得最优解，所以一般使用贪心法的时候，都要确保自己能证明其正确性。
适用范围
贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。
证明
贪心算法有两种证明方法：反证法和归纳法。一般情况下，一道题只会用到其中的一种方法来证明。
- 反证法：如果交换方案中任意两个元素/相邻的两个元素后，答案不会变得更好，那么可以推定目前的解已经是最优解了。
- 归纳法：先算得出边界情况（例如 \(n\) = 1）的最优解 \(F_1\)，然后再证明：对于每个 \(n\)，\(F_{n+1}\) 都可以由 \(F_{n}\) 推导出结果。
题目练习
A. 异或与乘积
时间：1s 空间：256M
题目描述：
小信有 \(n\) 个数的序列 \(a_i\)。现在他想做若干次操作，每次选择两个数，把他们异或起来，之后删除这两个数，并把他们异或后的结果加入序列。
小信进行若干次操作后，会把序列中剩下的数全部乘起来。小信想知道最后的结果最大是多少。注意，小信最多操作 \(n−1\) 次，在这之后序列会只剩下一个数。
由于答案可能很大，输出对 \(1000000007\) 取模后的结果。
输入格式：
第一行包含一个整数 \(n\)。
第二行包含 \(n\) 个整数 \(a_i\)。
输出格式：
输出一行表示答案对 \(1000000007\) 取模后的结果。
样例1输入：
4
1 2 1 2
样例1输出：
9
样例2输入：
2
3 3
样例2输出：
9
样例3输入：
2
1 3
样例3输出：
3
约定：
有 \(30\%\) 的数据，\(2 \le n \le 5\), \(1 \le a_i \le 10^9\)。
对于 \(100\%\) 的数据，\(2 \le n \le 10^5\), \(1 \le a_i \le 10^9\)。
分析：
我们需要找到两个数 \(a_i\) ^ \(a_j\) ＞ \(a_i\) * \(a_j\)， 去进行异或操作才对整体有帮助。
经过一些简单数学思想可证， 这两个数需满足以下两个要求 ：
-
有一个数为
1 -
另一个数为
偶数