<style> .reveal p{text-align:left;}</style> # 枚举优化  --- ## 1、枚举与数据范围 在noi竞赛中，一般规定数据范围从小到大，例如： ```c 30%的数据：n <= 1,000 60%的数据：n <= 100,000 100%的数据：n <= 10,000,000 ``` 入门组有时候对数据规模要求不大，直接枚举往往就能拿到所有的分数 提高组枚举往往只能满足30%的数据，而对于更多的数据，枚举会由于性能太差导致超时。 **注意：** 如果每道题都能通过枚举算法拿到30分，肯定能拿到奖项的哦！！！ --- ## 2、优化思路 维度、状态函数、判定函数等三个环节都可以优化。 根据乘法原理，总运算次数为维度数 * 状态函数里的运算次数 + 维度数 * 判定函数里的运算次数，如果状态函数里有循环运算、或者判定函数里有循环运算，总运算次数就会比较大。 --- 可能的优化点： - 减少维度、压缩维度区间。（剪枝） - 直接压缩状态区间（二分）。 - 通过预定义去掉状态映射、判定、求解里的循环（预定义）。 - 状态递推，由之前的状态运算得到（动态规划）。 --- ## 3、比较常用的技巧有： - 桶数组 - 前缀和 - 差分 - 二分 - 数学分析 - ... --- ### 3.1 桶数组 当需要对某个状态判定是否存在、次数、排序的时候，如果状态空间在某个范围以内，就可以使用桶数组。 |例题| |---| |[YBTJ1130 找第一个只出现一次的字符](/http://39.99.183.126:8888/p//YBTJ1130)| 又例如砝码称重题目（[题目详情 - 砝码称重 - whoj](http://39.99.183.126:8888/http://39.99.183.126:8888/p//356)）中，总重量<=1000克，就可以用to[1005]作为桶数组，下标表示某个总重量，初始值为0表示不能被砝码组合而成，值为1表示能被砝码组合而成。 于是，枚举过程就可以分成两个部分： 第一部分：预处理，通过筛法把所有可以组合的重量都设置到桶数组里，值为1。 第二部分：枚举，枚举桶数组，对值为1的进行计数。 --- ## [前缀和与差分](/blog/2/64707b8118d26a69f823902b#1685093249823) ### 3.2 前缀和 前缀和指对于序列计算前n项的和，例如对于序列a[]，定义前缀和s[i]=a[1]+...+a[i]，在计算前缀和的时候可以通过递推： --- ```c++ for(...) s[i] = s[i-1] + a[i]; ``` 也可以直接替换原序列： ```c++ for(...) a[i] += a[i-1]; ``` 前缀和是一个强力的预处理工具，主要用来求区间和，例如求序列a里面［L, R］区间的和，就可以通过前缀和快速求解： `sum = s[R] - s[L-1];` --- ### 3.3 差分序列 差分序列：对于序列a[]，定义d[i] = a[i] - a[i-1]。 差分序列可以递推生成： ```c++ for(...) d[i] = a[i] - a[i-1]; ``` 也可以直接覆盖原序列： ```c++ for(int i=n; i>=1; i--)//注意大到小 a[i] -= a[i-1]; ``` --- 差分序列是前缀和的反作用，对于序列a[]、前缀和s[]、差分序列d[]： a是s的差分序列，d是a的差分序列 s是a的前缀和，a是d的前缀和 **简单的说，对序列a的差分序列d求前缀和，就回到了a**。 在预处理里，差分序列主要用来进行区间操作，例如：对序列a进行区间操作，对[L, R]内的每个元素都加上x。 --- * 朴素方法－循环操作： ```c++ for(int i=L; i<=R; i++) a[i] += x; ``` --- * 差分方法： 1、先求差分 2、对差分做两端操作 d[L] += x; d[R+1] -= x; 3、前缀和算回原序列 ```c++ for(...) a[i] = a[i-1] + d[i]; ``` 当有多个区间操作时，差分＋前缀和具备巨大的优势。 --- ### 3.4 二分求解 如果状态对于某个判定（例如check(x)）具有单调性，比如说能提炼出以下的特征： * 假设check(x)为真，则比x大（或小）的都为真。 * 假设check(x)为假，则比x小（或大）的都为假。 这样就可以使用二分来快速逼近，因为每次判定都可以排除掉一半的状态，这也是一种剪枝技巧。 二分的具体细节会在专门知识点里描述。 --- ### 3.5 数学分析 数学分析一般是指对状态进行数学运算，压缩状态空间，以减少枚举次数的一种方法。 例如－求正浮点数x最近（一样近取小的）的整数： * 朴素方法：枚举1..n * 数学分析法-四舍五入公式： ```c++ int k = x + 0.5 - 1e-9; ``` --- 数学分析法没有一概而论，一般都是针对枚举的维度、状态、维度与状态之间的关系等进行深入分析，挖掘出状态区间的规律，最后达到剪枝的目的。 --- |例题| |---| |[**abc343c** C - 343](/http://39.99.183.126:8888/p//abc343c)| |练习题| |---| |[**WHJ2024A** 三角形个数(triangle)](/http://39.99.183.126:8888/p//WHJ2024A)|