枚举

有些问题无法通过数学方法或简单计算直接得出，但可以用穷举法暴力枚举，例如， ```cpp 求n以内最大的回文数 ``` 没有一种方法可以直接计算得到答案，但是可以通过枚举+检查的方式求出。可以依次枚举从1到n-1的所有数字，找到其中回文且最大的就是结果。按照这个思路，问题变成了 ```cpp 判断一个数是否是回文的 ``` 这样问题得以解决。 ### 优化 枚举法是一种简单、粗暴的算法思想，使用时要想方设法进行优化，舍弃一些不可能成为答案的枚举。例如 ```cpp 百钱买百鸡问题：公鸡5元一只，母鸡3元一只，小鸡1元3只。现在有100元钱买100只鸡，问有多少种方法 ``` 显然，枚举公鸡、母鸡、小鸡的数目可以求出答案。但不够优。 枚举了公鸡、母鸡，由于鸡总数为100，所以小鸡数目就确定了，只需检查在这个情况下总价钱是否为100就可以了。(甚至，枚举任意一种鸡的数目，其他两种都是可以确定的) 有时，调整枚举顺序也可以优化，例如上面回文的例子，从后往前枚举显然是更优的选择。 预处理是枚举法常见的优化策略，在枚举前记录一些对答案有价值的信息，枚举时根据信息减少枚举量。例如区间求和，求一个数组任意[l,r]区间的和，直接枚举需要O(n)。可以在存储时记录前缀和(从某个位置开始往左全部数字的和) |下标| 0 |1 |2 |3 |4 |5 |6 |7 | | -----------:| -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | |数值| 1 | 2 |3 |4 |5 |6 |7 |8 | |前缀和sum| 1 | 3 |6 |10 |15 |21 |28 |36 | 有了前缀和，任意区间[l,r]的和可以用sum[r]-sun[l-1]得到,时间复杂度O(1)