1 E

Theory&Thinkings #

  • 为什么要用枚举？
    • 解准确且全面
    • 实现简单，通过循环或递归实现
    • 执行效率提升空间通常较大

具体方法：

  1. 枚举对象
  2. 枚举过程
  3. 验证解

不是所有问题都有巧妙的解决方案，没有想到就要进一步做优化，对于枚举来说：压缩枚举空间。

枚举算法

也称之为穷举算法，就是按照问题本身的性质，一 一列举出该问题所有可能的解， 并在列举的过程中，逐一检验每个可能解是否是问题的真正解。若是则采纳这个解; 否则抛弃它。

  • 不能遗漏，否则可能导致结果不正确
  • 不要重复，否则可能导致效率比较低

枚举算法设计步骤

  1. 确定枚举对象 枚举对象也可以理解为是问题解的表达形式，一般需要 用若干参数 (p1, p2, ……, pk) 来描述
    1. 参数之间需要相互独立，而且参数数目越少，问题解搜索空间的维度也相应地小
    2. 每个参数的取值范围越小，问题解的搜索空间也越小
    3. 优化模型 针对问题特征，优化对象模型
  2. 逐一列举可能解 根据枚举对象的参数构造循环 (也可以递归)，一一 列举其表达式的每一种取值情况。
    1. 优化过程 针对对象特征，优化列举和验证过程
  3. 逐一验证可能解 根据问题解的要求，一一验证枚举对象表达式的每一 个取值，如果满足条件，则采纳它; 否则，抛弃之。

e.g.s #

数组配对 # 

给你一个长度为n的数组A和一个正整数k，问从数组中任选两个数使其和是k的倍数，有多少种选法？对于数组 a1=1 , a2=2 , a3=2 而言：

(a1,a2) 和 (a2,a1)被认为是同一种选法；

(a1,a2) 和 (a1,a3)被认为是不同的选法。
  • 朴素方法
    • 枚举对象：𝑂𝑏𝑗(𝑎𝑖,𝑎𝑗),1≤ 𝑖 < 𝑗≤ 𝑛
    • 逐一列举
    • 逐一验证
  • 存在问题：时间复杂度较高：𝑂(𝑛2)
    • 如果问题规模较大，求解问题需要的时间也呈指数级别增长
  • 尝试改进：如何减少问题空间？如何更加有效的枚举？
    • 利用桶思路，将原问题之间用 mod 运算降低到一个非常低的解空间中再进行枚举
    • 枚举对象：𝑂𝑏𝑗(𝑎𝑖,𝑎𝑗),1≤ 𝑖 < 𝑗≤ 𝑛
    • 逐一列举：
      • 预处理： (𝑎𝑖 + 𝑎𝑗)%𝑘 = 0
    • 逐一验证：(𝑎𝑖%𝑘 + 𝑎𝑗%𝑘)%𝑘 = 0
    • 求解细节：
      • 会变成两个单独数字的配对问题，存在两种情况
      • 两个数字在同一桶内：组合数公式
      • 两数字不在同一桶内：直接相乘，相当于组合公式
void work() {
    LL ans = 0;
    for (int i = 0; i < k; i++) {
        int j = (k - i) % k;
        if (j < i) break;
         // 避免重复 else if (j == i) // 0或者k/2
        ans += 1LL * b[i] * (b[i] - 1) / 2;
        else ans += 1LL * b[i] * b[j];
    }
    cout << ans << endl;
}

绳子切割问题 # 

有N条绳子，它们的长度分别为𝐿_𝑖 (≤1000)。如果从它们中切割出 K 条长度相同的绳子，这K条绳子每条最长能有多长？答案保留到小数点后2位。

枚举法的典型应用

我要枚举出一个最长长度出来，可以直接套用二分枚举的算法进行实现

  • 枚举对象：绳子长度
  • 枚举过程：二分枚举
  • 验证方法：到每个已知绳子中验证其切割结果是否为 k
int n, k; // 全局变量，数组长度和目标数值 int a[MAX_N]; //全局变量，待查找数组
int binarySearch() {
    int lb = 0;
    ub = n; // 初始化解的存在范围
    while (ub - lb > 0) {
        int mid = (lb + ub) / 2;
        if (a[mid] >= k) ub = mid; 
        // 解的范围更新为 [lb, mid] else
        lb = mid + 1;              
        // 解的范围更新为 [mid + 1, ub]
    }
    return lb; // lb即为答案
}

关于二分法的边界问题及两种写法_二分法边界处理-CSDN博客

二分枚举基本原理

一般化模型：

  • “求满足某个条件𝑪(𝒙) 的最小的𝒙”，其中𝐶(𝑥) 满足性质: 如果任意𝑥满足𝐶(𝑥)，则所有 的𝑥 ≥ 𝑥也满足𝐶(𝑥)
  • “求满足某个条件𝑪(𝒙) 的最大的𝒙”，其中𝐶(𝑥) 满足性质: 如果任意𝑥满足𝐶(𝑥)，则所有 的𝑥 ≤ 𝑥也满足𝐶(𝑥)
算法(模型1)
1. 设置x的初始范围，即下界lb和上界ub 
2. While (ub > lb)
1)𝑚𝑖𝑑 = (𝑙𝑏 + 𝑢𝑏)/2; 
2)if (C(mid))
更新上界: 𝑢𝑏 ← 𝑚𝑖𝑑; 
3)else
更新下界:𝑙𝑏 ← 𝑚𝑖𝑑+1

算法(模型2)
1. 设置x的初始范围，即下界lb和上界ub 
2. While (ub > lb)
1)𝑚𝑖𝑑 = (𝑙𝑏 + 𝑢𝑏)/2; 
2)if (C(mid))
更新下界: 𝑙𝑏 ← 𝑚𝑖𝑑; 
3)else
更新上界:𝑢𝑏 ← 𝑚𝑖𝑑−1

移除石头——最重要枚举问题 # 

有一条河，河中间有一些石头，石头的数量以及相邻两块石头之间的距离已知。现在可以移除一些石头，假设最多可以移除m块石头（注意：首尾两块石头不可以移除，且假定所有的石头都处于同一条直线），问最多移除m块石头后相邻两块石头之间的最小距离的最大值是多少？
  • 传统的贪心策略，二叉树搜索策略要么不可行，要么复杂度过高，需要一种高效的遍历算法——二分枚举
  • 问题建模:
    • 求满足条件𝑪(𝒅) 的最大值𝑑，其中𝑪(𝒅) 描述为:𝑪 𝒅 ≔ 最多移除 m 个石头后最近两个石头的距离不小于 d
  • 问题转换：
    • 求满足条件𝑪(𝒅) 的最大值𝑑，其中𝑪(𝒅) 描述为:𝑪 𝒅 ≔ 最多移除 m 个石头后任意相邻两个石头的距离不小于 d
  • 算法思路：
    • 应用贪心思想
    • 循环依次考虑相邻石头，如果距离小于 d，则去掉一个石头;
    • 如果任意相邻石头的距离都不小于 d，则返回 true;
    • 如果移除的石头个数大于 m，则返回 false

函数求根问题 # 

有形如：𝑎𝑥^3+𝑏𝑥^2+𝑐𝑥+𝑑=0 的一元三次方程。给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值≥1。请设计算法求解三个实根。

输入格式
多组输入(不超过20组数据，读入以EOF结尾)
每组输入四个数字，a，b，c，d (4个数绝对值小等于30)

输出格式
每组输出一行结果，由小到大输出3个根(保留两位有效数字)

Problem A. 优美的立方质数 # 

题目描述
如果一个质数能被表示为三个不同的质数的和的形式，那么我们称它为立方质数。现在给你一个数n，判断它是不是立方质数。

输入数据
正整数n，n<=1000

输出数据
Yes或者No

Problem B. 课堂作业 -6-2 木棍切割问题 #

Problem C. 李老师的幸运数字 # 

题目描述
李老师的lucky number 是3，5和7，他爱屋及乌，还把所有质因数只有3，5，7的数字认定为lucky number，比如9, 15, 21, 25等等。请聪明的你帮忙算一算小于等于x的lucky number有多少个？

输入数据
一个正整数x，3=<x<=1000000000000

输出数据
小于等于x的lucky number的个数。

Problem D. 思维之花 - 简单背包 # 

题目描述
李老师正准备暑假旅行，他有一个容量为L的行李箱和n个物品（n不超过20），每个物品都有自己的体积，物品可以放入行李箱，但行李箱中物品的总体积不能超过行李箱容量，李老师现在想知道他有多少种携带物品的方案（一个物品都不带也算一种方案）

输入数据
第一行为两个正整数n和L，分别代表物品总数和行李箱容量，n<=20，L<=1e9 接下来一行为n个正整数vi，代表第i个物品的体积，vi<=1e8

输出数据
方案数

Problem E. 课堂作业 -7-2 石头移除问题 # 

题目描述
有一条河，河中间有一些石头，已知石头的数量和相邻两块石头之间的距离。现在可以移除一些石头，问最多移除m块石头后（首尾两块石头不可以移除），相邻两块石头之间的距离的最小值最大是多少。

输入数据
第一行输入两个数字，n（2<=n<=1000）为石头的个数，m（0<=m<=n-2）为可移除的石头数目 随后n-1个数字，表示顺序和相邻两块石头的距离d（d<=1000）

输出数据
输出最小距离的最大值

Problem F. 数对选择 # 

题目描述
给你一个长度为n的数组和一个正整数k，问从数组中任选两个数使其和是k的倍数，有多少种选法。 对于数组a1=1 , a2=2 , a3=2而言：
(a1,a2)和(a2,a1)被认为是同一种选法；
(a1,a2)和(a1,a3)被认为是不同的选法。

输入数据
第一行有两个正整数n，k。n<=1000000，k<=1000000 第二行有n个正整数，每个数的大小不超过1e9

输出数据
选出一对数使其和是k的倍数的选法个数
  • Q：为什么使用 1LL 进行处理？
    • 在这段代码中，乘以 LL 的目的是为了确保在进行乘法运算时使用长整型（long long）进行计算，避免整数溢出问题。
    • 具体来说，1LL 是一个将数字 1 转换为长整型的方式。在这里，1LL * (bucket[i] * (bucket[i] - 1) / 2) 和 1LL * (bucket[i] * bucket[j]) 中的乘法运算都会使用长整型进行计算。
    • 这是因为当进行乘法运算时，如果操作数中有一个是长整型，那么结果也将是长整型。在某些情况下，特别是当计算的结果可能超过整数范围时，使用长整型是很重要的，以防止溢出。如果不使用 1LL 进行转换，整个表达式的结果可能会被截断为普通整型，导致错误的结果。