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局
- 判斷要開的數組大小
- 給一個計分結果,分別輸出 11 分制下和 21 分制下的比賽結果
- 代碼
-
- 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
- ⭐保證字符串連接後的字典序最大
- 代碼
-
- string 類可以用 + 自動連接
- 以字符串形式讀入
- ❗把 > 改成 >= 在 oj 裡第二個 test 會超時
- 兩者區別在於 = 的情況返回 true 還是 false,和 sort 排序本身不穩定沒有關係~
- ⭐cmp 函數不簡單
- 必須滿足 Strict Weak Ordering
-
- 簡要參考STL sort 的 comp 函數注意事項-CSDN
- 詳細參考一次 stl sort 調用導致的進程崩潰- 博客
-
-
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 層循環
- 枚舉 Y(一堆數)
- 枚舉 X(1 個數):X 等於 Y 則 continue
- 枚舉數長:3 ~ 17
- X 的位置:1 ~ 數長
- X、Y 如果有一個 0,不能有前導 0
- X 為 0,X 不能在第一位;Y 為 0,X 必在第一位
- 構造優雅數,判斷是否在區間內
- 代碼
-
- 換個角度枚舉,很巧妙
- 一個數可由數字組成、數字長度、數字位置決定
-
附加知識點#
- 如果需要定義超大數組或者有其他函數需用到該數組,最好定義為全局變量,開辟堆空間
思考點#
- string str; //cin >> str 等價於 cin >> &str [0]
- ❓涉及到對象的,最好不要使用取址操作
- 這個之後注意
Tips#
課程速記#
- HZOJ-506
-
- 輸出時 1.0 提升類型
-