Bo2SS

Bo2SS

3 OJ題目講解

HZOJ-599:兩數之和 1#

圖片

範例輸入

6 15
1 5 6 7 10 26

範例輸出

1 4
  • 思路
方法說明時間複雜度空間複雜度
暴力兩層循環O(N^2)O(1)
暴力固定一個數,
另一數用二分去查找
O(NlogN)O(1)
哈希表遍歷第一遍,存
遍歷第二遍,找
O(N)O(N)
⭐雙指針兩邊指針加,
不斷更新
O(N)O(1)
  • 雙指針

  • 陣列有序

  • 同理,三數之和、四數之和...

    • 多一層循環
  • 代碼

  • 圖片

HZOJ-600:楊氏矩陣#

圖片

範例輸入

3 4
1 2 3 4
5 6 15 20
7 10 20 25
15

範例輸出

2 3
  • 思路
    • 從左下角出發或從右上角開始
      • 逐步移動橫坐標或縱坐標一個單位
      • 時間複雜度:O (n + m)
    • 和上一題的雙指針思想很相似~
      • 圖片
      • 二維空間和一維空間的轉換!
  • 代碼
    • 圖片
    • 提交還是有 2 個 test 超時,還有更快的方法嗎?
      • 沒有,是 OJ 平台的波動性導致的

HZOJ-477:元音字母#

圖片

範例輸入

ABCDEFGIKJUMNBZZ

範例輸出

44
  • 思路
    • 找到上一个元音字母的位置
    • 遍歷接下來的元音字母的位置
    • 計算距離,更新答案
  • 代碼
    • 圖片
    • s [i] 為 \0 時停止
    • last 初始為 - 1,可以在找到第一個元音時,不計算距離,只更新 last

HZOJ-479:乒乓球#

圖片

圖片

範例輸入

WWWWWWWWWWWWWWWWWWWW
WWLWE

範例輸出

11:0
11:0
1:1
21:0
2:1
  • 思路
    • 給一個計分結果,分別輸出 11 分制下和 21 分制下的比賽結果
      • 輸出每局得分幾比幾
    • 根據輸入數據每行最多 25 個字母,最多有 2500 行
      • 得到 2500 * 25 分,/11 或者 / 21
      • 得到 11 分制下最多6000局,21 分制下最多3000
      • 判斷要開的數組大小
  • 代碼
    • 圖片
    • cin 讀入規則
      • 遇到空格、換行符和制表符結束輸入,並在緩衝區中留下使輸入結束的結束符 (Enter、Space、Tab),作為下次 cin>> 開頭的忽略
      • 遇到 EOF 會返回 1

HZOJ-480:保齡球#

圖片

範例輸入

/ / / 72 9/ 81 8/ / 9/ / 8/

範例輸出

192
  • 思路
    • 關鍵就是紅框那段話
    • 三種計分情況
      • 直接清空:本輪 10 分 + 接下來 2 球得分
      • 間接清空:本輪 10 分 + 接下來 1 球得分
      • 沒清空:本輪得分
    • 一局十輪
    • 👌使用結構體
      • 字符數組:每輪對應的得分字符串 8/
      • 第一次後得分
      • 第二次後得分:本輪最終得分,這裡很巧妙,根據題意設置
      • Flag:屬於上述第幾種情況
  • 代碼
    • 圖片
    • 關鍵在理解規則,以及巧妙利用結構體!
    • s 數組開 4,本來最多是 2 個字符 +\0,但是因為字節對齊,開 3 開 4 一樣,這裡開 4
    • 在終端需使用 ctrl + d 結束 cin 所在的 for 循環

HZOJ-481:冰壺比賽#

圖片

範例輸入

8
5 20 18 19 3 15 13 3
20 2 17 12 5 18 10 11
20 3 4 1 2 11 9 2
1 15 19 9 8 14 11 10
15 2 10 1 19 14 3 18
15 17 21 19 24 32 19 26
-1

範例輸出

0:1
0:0
3:0
3:1
  • 思路
    • 誰能得分:所有冰壺離圓心最近的隊可以得分
    • 得多少分:在半徑 r 內,且在對方離圓心最近的冰壺構成的⚪內,得分隊有多少個冰壺
      • 圖片
      • 綠隊可得 2 分
      • 來自田船長之筆~
    • 最多 10 局,20 行 + 1
    • 先輸出每輪的比分,再輸出總比分
  • 代碼
    • 圖片
    • 利用 sort 更方便找獲勝方和計分,消耗不大

HZOJ-484:柱狀統計圖#

圖片

範例輸入

ABC ABC.DEF()G GCC XY
354342aaaCaa aaaaaaaabcdbcd

範例輸出

    *
    *
    *
* * *       *
* * * * * * *                                 * *
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
  • 思路
    • 簡單:統計大寫字母的個數
    • 難點:每行不要有多餘的空格;按列輸出
    • 流程
      • 需根據最大的字符出現次數統計行數
      • 外層循環:從 mmax 到 1,在滿足條件的字符位置上輸出 *
        • 先得到每行最後一個輸出 * 的字符,從 Z 到 A 判斷是否滿足條件
      • 內層循環:從 A 到 ind,需統計每一行最後一個字符是哪些
    • 注意 * 和空格的輸出條件
      • 就是判斷字符的統計數是否大於在該行輸出 * 需滿足的數量
  • 代碼
    • 圖片
    • 邏輯要理清~
    • num 數組開 130 位很巧妙,與 ASICII 碼範圍對應,統計時不需要判斷
    • 首位判斷:避免有多餘的空格

HZOJ-485:均分紙牌#

圖片

範例輸入

4
9 8 17 6

範例輸出

3
  • 思路
    • 只能移到相鄰牌堆
    • 先算平均數,得到每堆牌的預期數量
    • 從一個方向湊到平均數即可
      • 從左往右
      • 不夠借,右邊變負數也沒問題
      • 本質和兩種方向湊一樣!
  • 代碼
    • 圖片
    • 最後一堆牌不用考慮
    • 只需更新右邊一個數,公式無論加減都成立

HZOJ-503:獨木舟(自己做)#

圖片

範例輸入

100
9
90
20
20
30
50
60
70
80
90

範例輸出

6
  • 思路
    • 排序再遍歷判斷
  • 代碼

HZOJ-504:刪數⭐#

圖片

範例輸入

179566
4

範例輸出

15
  • 思路
    • 大整數
    • 精髓:越靠前的數越小,整體才會小
      • 大數在前、小數在後情況,刪掉大數
      • 而直接刪除大數是不行的
      • 單調棧知識?參考什麼是單調棧?- 五分鐘學算法
    • 流程:
      • 掃一下大整數,得到字符串
        • 使用 string 類,可以比較方便地刪數
        • string.replace()
      • 遍歷每兩位
      • 循環刪的次數 s 次
      • 輸出
        • 忽略前導 0,必須要有 flag,只是判斷前導 0,不省略其他 0
    • 延伸:刪字母使字典序盡可能小
  • 代碼
    • 圖片
    • ind 默認為最後一位!即最大數,因為是從小到大排列的
    • str.replace 操作,參考std::string::replace-cplusplus
    • 處理前導 0 操作:定義 flag

HZOJ-505:最大整數#

圖片

範例輸入

3
121 12 96

範例輸出

9612121
  • 思路
    • ⭐保證字符串連接後的字典序最大
      • 保證任意 2 個元素的連接,都是前面的字典序大於後面的
      • 使用 sort
    • 不行的方法
      • 按字典序排序 121 12 96 👉 9612112
      • 高幾位相同判斷長度,短的放前 129 12 96 👉 9612129
  • 代碼

HZOJ-508:兩人過河#

圖片

範例輸入

4
1
5
2
10

範例輸出

17
  • 思路
    • 先排序
    • 四種情況
      • 1 人
      • 2 人
      • 3 人:最快的人當工具人
      • 4 人
        • ①傳手電的速度保證最快
        • ②過橋效率最高(當次快很快、次慢很慢的時候)
        • 每次找過兩個人的最快情況
        • 圖片
  • 代碼
    • 圖片
    • 妙在 2 人 2 人地計算,兩種方式取最小

HZOJ-509:智力大衝浪#

圖片

範例輸入

10000
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10

範例輸出

9950
  • 思路
    • 排序:扣錢數、時間←結構體
      • 先按扣錢數排序(多在前),再按時間排序(少在前)
    • 時段標記數組:記錄某時段佔用情況
      • 對於每個任務盡可能靠後去完成
  • 代碼

HZOJ-518:金幣#

圖片

範例輸入

10

範例輸出

30
  • 思路
    • 兩層循環:給多少錢(1 ~ x);天數(1 ~ i)
  • 代碼

HZOJ-513:樓層編號#

圖片

範例輸入

14 3

範例輸出

12
  • 思路
    • 枚舉虛假樓層(1 ~ m),可以做為真實樓層編號存在則加一
    • 有非暴力解法
  • 代碼
    • 圖片
    • ans 記得初始化~
    • if 裡只有 ++ 操作時,可以整合

HZOJ-514:火柴棒等式#

圖片

範例輸入

14

範例輸出

2
  • 思路
    • 每個數對應的火柴數是固定的
    • 範圍估計(最多 24 根火柴)
      • 111 + 111 左邊最大的數?
      • 其實還可以和 0、1 搭配
      • 範圍會更大:0 ~ 2000
      • 加數 1、加數 2 可重複
    • 暴力枚舉
      • 枚舉兩個加數,看和是否滿足要求👈中轉函數 + 苦力函數
  • 代碼
    • 圖片
    • 枚舉👉中轉👉苦力

HZOJ-515:比例簡化#

圖片

範例輸入

1498 902 10

範例輸出

5 3
  • 思路
    • 範圍不大,L 上限是 100
    • 從小往大枚舉
      • 兩層循環
      • 不需要判斷互質,如果存在,則前面肯定有滿足條件的互質的答案
    • 枚舉→判斷→保留→給出最貼合答案的
  • 代碼

HZOJ-516:奶牛碑文#

圖片

範例輸入

6
COOWWW

範例輸出

6
  • 思路
    • 方法一:直接枚舉,三層循環?❌過於暴力,O (N ^ 3)
    • 方法二:空間換時間
      • 對於每個 O,能組成的 COW 數 = 前面 C 的數量 * 後面 W 的數量
      • 掃兩遍數組,記錄 O (N)
        • 前綴和:到這個位置為止,有多少個 C
        • 後綴和:到這個位置為止,有多少個 W
      • 再掃一遍數組,找 O O (N)
        • ans + 前 C 數 * 後 W 數
      • 時間:O (N) 空間:O (N)
    • 引申:統計 PUSH,時間複雜度 O (N ^ 2)
      • 掃兩遍,統計前綴和 P,後綴和 H
      • 找到 U 後,再找 S,計數
      • 參考後面代碼裡的 “同時找” 技巧,應該也能省一個後綴和數組空間,找到 S 後找 U
  • 代碼
    • 圖片
    • 統計後綴和 “同時找” O,節省了後綴和數組的空間 0
    • int 型相乘要注意溢出問題

HZOJ-517:三角形個數#

圖片

範例輸入

10

範例輸出

2
  • 思路
    • 關鍵在於不能有重複的三角形
      • 確定枚舉方式,按大小邊來枚舉
      • 短邊 i:1 ~ n / 3
      • 中邊 j:i ~ (n - i) / 2
      • 長邊:判斷 n - i - j < i + j,成立則 ans++
    • 定了大小邊,可以避免重複
  • 代碼
    • 圖片
    • 枚舉最短邊→次短邊,保證不會重複

HZOJ-519:優雅數#

圖片

範例輸入

110 133

範例輸出

13
  • 思路
    • 優雅數:只有一個數字不一樣,其餘都一樣
    • 枚舉題
    • ❌如果直接枚舉,再判斷是不是優雅數,量太大!10 ^ 16
    • 先枚舉優雅數YYXYYYYY,再判斷是否在區間
      • 5 層循環
      1. 枚舉 Y(一堆數)
      2. 枚舉 X(1 個數):X 等於 Y 則 continue
      3. 枚舉數長:3 ~ 17
      4. X 的位置:1 ~ 數長
        • X、Y 如果有一個 0,不能有前導 0
        • X 為 0,X 不能在第一位;Y 為 0,X 必在第一位
      5. 構造優雅數,判斷是否在區間內
  • 代碼
    • 圖片
    • 換個角度枚舉,很巧妙
    • 一個數可由數字組成、數字長度、數字位置決定

附加知識點#

  • 如果需要定義超大數組或者有其他函數需用到該數組,最好定義為全局變量,開辟堆空間

思考點#

  • string str; //cin >> str 等價於 cin >> &str [0]
  • ❓涉及到對象的,最好不要使用取址操作
    • 這個之後注意

Tips#


課程速記#

  • HZOJ-506
    • 圖片
    • 輸出時 1.0 提升類型
載入中......
此文章數據所有權由區塊鏈加密技術和智能合約保障僅歸創作者所有。