1 编程能力提升

Euler-1：3 或 5 的倍数#

思路
- ①普通解法：遍历 1-1000，判断能不能被 3 或 5 整除，可以就加入 sum
  - 时间复杂度：O (N)
- ②更优解：直接计算 3 或 5 倍数的和
  - 利用等差数列，要注意有重复计算
    - 公式：（首项 + 末项） * 项数 / 2
  - 3~999 的 3 的倍数和 + 5~1000 的 5 的倍数和 - 15~985 的 15 的倍数和
  - 时间复杂度：O (1)
代码

Euler-2：偶斐波那契数#

思路
- 普通解法：用一个数组存储前面的值，递推，当是偶数时加入 sum
  - 空间复杂度：O (N)，需要大量的额外空间
- 更优解：就用两个变量来回倒（老师说的是 3 个，实际 a 用不到）
  - b、c：每次迭代，c = c + b; b = c - b;
  - 空间复杂度：O (1)
代码

Euler-4：最大回文乘积#

思路
- 判断回文数的思路
  - 两个指针分别从头尾对应判等
  - √更方便：把数字反过来，再做判等
    - 其实还可以只反过来一半位数即可，循环成立条件是翻转的数字 < 剩余翻转的数字
      - 但要注意：奇数位的情况；末尾含 0 的情况
- 枚举所有的 3 位数相乘，判断回文数，找最大
代码
- 使用 time *./a.out 分别计算两两组合的时间花费

time	① 只翻转一半位数	② 翻转全部位数
A 先判断回文数	0.013	0.017
B 先判断大小	0.005	0.005

- j 从 i 开始，可以避免重复乘积
- C++ 自带 max 函数
- 此外，利用短路原则还可以优化 B，速度还有提升：0.004s

Euler-6：和的平方与平方的和之差#

思路
- 简单循环：分别计算 1~100 的平方和、和，再用和的平方 - 平方和即可
代码

Euler-8：连续数字最大乘积#

思路
- 首先将数据复制，保存在本地为字符串
  - 检查复制后的格式：删掉空格、换行
  - 读入时用数组存储，读取每位时需转换为数字（- '0'）
- 滑动窗口法
  - 静态窗口：固定窗口大小
  - 动态窗口：一般称为双指针
- 解法：使用滑动窗口法 ——静态窗口
  - 只需考虑窗口进的数和出的数，可以减少运算次数
    - 出：除以
    - 进：乘以
    - 注意值是否为 0
- 代码
  - 前 13 位不含 0，可以直接计算 now
  - 注意窗口内 0 的情况
    - ❗定义一个 0 的计数器
    - ❌是否可以碰见 0 就将乘积变为 1？
      - 不行，需要存除除 0 以外数的乘积
    - ❌是否可以将 0 直接变为 1？可以减少判断次数，只需要对进来的值判断 0
      - 但这样是不可以的，因为有可能不满 13 位的两个 0 之间的数很大
      - 比如 11022340111111111111111111
  - 执行时报错：floating point exception
    - 除以 0 了可能会导致该错误
  - 错误地估计了上界，9^13 肯定超过了 int 类型的上界，所以使用 long long

Euler-11：方阵中的最大乘积#

思路
- 方向数组
  - 通过矩阵中的一个数的坐标，推算出某个方向的数的坐标
- 计算某个数各个方向的连续 4 个数的乘积，找出最大值
  - 计算问题：只需取连续的 4 个方向来计算。避免重复计算
  - 边界问题：①判断边界；√②边界补 0（至少 3 圈 0）。解决越界问题
代码
- 学会定义方向数组
  - 利用变量 l 控制某方向的第 l 位
- 在 C 语言循环中写声明变量的语句，编译器只会创建一次。如 32、33 行
  - 参考C 语言之重复声明变量-CSDN

Euler-14：最长考拉兹序列（记忆数组）#

斐波那契数列
- 两种方法：递归、递推
- 递归
  - 常规
    - 很慢，因为有重复计算，但有优化版👇
  - 使用记忆数组
    - 递归 + 记忆化 ≈ 递推
    - 记忆化前→后：1.804s→0.002s
- 递推：速度快，也占用空间，是不是可用 euler2 里的两个变量来回倒？
  - 数组存储；num [i] = num [i - 1] + num [i - 2];
思路
- 同样利用递归 + 记忆数组
- 注意题中注：序列开始生成后允许其中的项超过一百万
- 不需要额外的计数器，可在每次计算下一个数时 + 1
代码
- 详见标注
  - num 数组长度越大，速度越快，空间消耗也越大
  - 用 t 记录函数结果，好在存进数组前做一个判断
  - main 函数里把 func (ans) 值先存一下可以加快速度

Euler-13：大和（大整数加法）#

思路
- 参照大整数加法
代码
- 参照大整数加法

➕大整数加法#

大整数：用 long long 也存不下，一般用字符串存储
⭐数组方法
- 两个数组倒着存储大数，数组第 0 位存储大数的位数👉
  - 如果不倒着存储，在最高为进位时不好处理？也可以直接输出不处理
  - 但是不倒着存储，会有低位对齐的问题，不好处理
- 对每个索引里的值求和，和的位数取两个大数的最大位数👉
- 处理进位，如果是最后一位进位，记得将和的位数 + 1👉
- 倒着输出
代码
- 可以不处理最高位进位的情况，最高位有进位时直接第一次输出一个两位数
  - 例如：输入 888 + 222；输出 11 1 0
  - 不过对于多个数相加可能普适性不好！一个索引存储 1 位数字最保险

Euler-25：一千位的斐波那契数（大整数加法）#

思路
* 两个变量里的大整数循环加即可
* int num [2] = {1}; // 剩下的自动填充 0
代码

✖ 大整数乘法#

思路
- 类同大整数加法
- 每一位的乘积结果相加的位置：i + j - 1
代码
- 答案数组的元素类型至少是 int
- 答案数组的长度取可能结果短的长度
- 乘积运算累加的位置要注意～
可尝试做欧拉计划 16、20 题

➗大整数除法#

除数和被除数都是大整数
思路
- 首先判断被除数是否大于除数
- 然后用待除数一直减除数，直到不能减为止，最多减 9 次
- 除数也可能是大整数，所以待除数也是大整数：这个会导致代码很复杂
可尝试 hzoj 475、476 题

Euler-15：网格路径（递推、通式）#

思路
- 方法一：递推（动态规划）
  - 当前方案数 = 上面来的方案数 + 左边来的方案数
  - 补 0 大法：从 (1, 1) 点开始存
  - 注意边界：对于 2 * 2 的网格，左上角和右下角为点 (1, 1)、点 (3, 3)
  - PS：也可以用递归 + 记忆化，有些相似
- 方法二：通式做，排列组合！
  - 对于 2 * 2 的网格
  - 往下和往右走的总步数是 4，其中往下走 2 步，往右走 2 步
  - 其实就是排列组合，C (4) 2 = 4! / [2! * (4 - 2)!]
  - 所以本题就是 C (40) 20
代码
- 方法一要记得特殊判断第一个点 (1, 1)
- 方法二边乘边除就不会越界，先乘再除不会有小数情况

Euler-18：最大路径和（树塔问题）#

思路
- 递推（动态规划）
  - 自上而下
    - dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + num[i][j]
    - 遍历最后一行，输出最大值
  - 自下而上
    - dp[i][j] = max(dp[i + 1][j + 1], dp[i + 1][j]) + num[i][j]
    - 最后不需要遍历，最上头就是最大值
- 补 0！
代码
- 第 i 行有 i 个值
- 自上而下、自下而上方法的主要区别在于最大值的位置确定

HZOJ-590：树塔狂想曲#

样例输入

样例输出

17
22
-1

思路
- ❌每次特殊处理一个点后，重新计算
- 记录每一个点对应的最大路径和与次大路径和
  - 经过某个点能获得的最大值：自上而下 + 自下而上 - 当前值
  - 时间、空间开销都是 O (N^2)
  - 思路图如下
代码
- 找到经过某一点的最大路径和的规律
- 次大值更新的情况要考虑周全
- 记录最大值坐标和次大值即可
- 判断 ban 掉的是不是最大点或者左上第一个点
- 使用了 scanf
  - 比 cin 快，具体见附加知识点 2

Euler-22：姓名得分#

思路
- 先处理 txt 文件
  - 字母都是大写
  - 全局替换 "," 为空格 " "，方便数据读入

:%s /","/ /g

- 读入字符串→sort 按字典序排序→计算每个姓名的字母值，乘以其排序后的位置，获得得分→累加得分
代码
- cin 的返回值
  - istream & 类型
  - 大多数情况下其返回值为 cin 本身（非 0 值），只有当遇到 EOF 输入时，返回值为 0
  - 参考关于 C++ cin 的返回值
- string 类
  - 重载好了小于号，可以直接 sort，从小到大排序
  - 不支持 scanf
  - 可以使用.size () 获得字符串长度 = 字符数 = 字节数
- 终止条件可以使用.size ()，也可以使用 name [i] 判断是不是 "\0"
- 两个函数可以直接用两个 for 循环代替

Euler-32：全数字的乘积#

思路
- 全数字概念：xx * xxx = xxxx，存在 1~9 每个数字一次
  - 没有 0！
- 避免重复计算
  - 第一个数字比第二个数字小
  - 第一个数字：范围 1~100，当其为 100 时，第二个数字至少为 100，三数位数和超过 9
  - 第二个数字：停止条件为三个数字位数之和大于 9
  - 使用 log10 判断位数：log10下取整+ 1
    - 对于正数转 int 和下取整效果一样，下取整后得到 double 还需要转 int
- 如何判断全数字
  - <9 不需要判断，只有 = 9 才判断，>9 停止
  - 使用 num [10] 存储 9 个数字的状态
- 乘积可从多个乘法等式中得到，但只求和一次
  - 使用标记数组，如果之前存过，就跳过
代码

Euler-33：消去数字的分数#

思路
- 有趣
- 有四个非平凡的例子，求四个分数的乘积化为最简分数后的分母值
  - 不考虑平凡解，即有 0 存在，不用考虑太细，可以直接要求每位都不为 0
- 分子分母都是两位数，分母比分子大
  - 分子：11 - 99；分母：分子 + i
- 四种抹除方式
  - 分子 1 = 分母 1；分子 1 = 分母 2；分子 2 = 分母 1；分子 2 = 分母 2
  - 抹除前后判等：十字相乘
代码
- 十字相乘法判断分数相等
- 通过公约数来得到最简分数

Euler-36：双进制回文数#

思路
- 前导 0：如 0012332100，不作为回文数

int num;
cin >> num;
// 00123 正常读入为 123

- 十进制、二进制都可整合成 N 进制
代码

Euler-30：各位数字的五次幂#

思路
- 重点：五次幂之和的最大范围？

设一个 X 位数
其最大五次幂之和为 9^5 * X
X 位数上界为 10^X
估计两个值的交点，即 9^5 * X = 10^X，X 大约为 5.xxx
所以 X 最大为 6

- - 枚举 10 ~ 1000000
- ⭐提前算好 1 ~ 9 的五次幂，存起来！
代码
- 关键在于枚举范围！
- 提前存储 1 ~ 9 五次幂和，避免重复计算

Euler-34：各位数字的阶乘#

思路
- 重点：阶乘和的最大范围？

（同上一题）
设一个 X 位数
其最大阶乘和为 9! * X
X 位数上界为 10^X
估计两个值的交点，即 9! * X = 10^X，X 大约为 6.xxx
所以 X 最大为 7

- - 枚举 10 ~ 10000000
- 同样，⭐提前算好 1 ~ 9 的阶乘，存起来！
代码

附加知识点#

全局变量都会自动初始化为 0
scanf 比 cin 快，参考
- cin、cout 的性能可能会很慢，因为它们需要保持与底层 C 库同步
  - 关闭同步会快，但还是不如 C 的输入输出函数
- 算法竞赛的时候用 cin、cout 输入输出比用 scanf、printf 慢多少？- 知乎
- 在 C++ 程序中使用 scanf () 比使用 cin 更快吗？- 腾讯云

思考点#

Tips#
使用语言为 C++，但与 C 有区别的只涉及到 cin、cout
time ./a.out 可以显示代码执行时间

Bo2SS

1 编程能力提升

Euler-1：3 或 5 的倍数#

Euler-2：偶斐波那契数#

Euler-4：最大回文乘积#

Euler-6：和的平方与平方的和之差#

Euler-8：连续数字最大乘积#

Euler-11：方阵中的最大乘积#

Euler-14：最长考拉兹序列（记忆数组）#

Euler-13：大和（大整数加法）#

➕大整数加法#

Euler-25：一千位的斐波那契数（大整数加法）#

✖ 大整数乘法#

➗大整数除法#

Euler-15：网格路径（递推、通式）#

Euler-18：最大路径和（树塔问题）#

HZOJ-590：树塔狂想曲#

Euler-22：姓名得分#

Euler-32：全数字的乘积#

Euler-33：消去数字的分数#

Euler-36：双进制回文数#

Euler-30：各位数字的五次幂#

Euler-34：各位数字的阶乘#

附加知识点#

思考点#

Tips#

课程速记#