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#

課程速記#