C/C++藍橋杯算法真題打卡（Day3）

一、P8598 [藍橋杯 2013 省 AB] 錯誤票據 - 洛谷

算法代碼：

#include<bits/stdc++.h>
using namespace std;int main() {int N;cin >> N;  // 讀取數據行數unordered_map<int, int> idCount;  // 用于統計每個ID出現的次數vector<int> ids;                  // 用于存儲所有ID（方便排序）int num;// 讀取所有IDfor (int i = 0; i < N; i++) {while (cin >> num) {ids.push_back(num);  // 將ID存入vectoridCount[num]++;      // 統計ID出現的次數if (cin.get() == '\n') break;  // 換行時結束當前行的讀取}}// 對ID進行排序sort(ids.begin(), ids.end());int missing = -1, duplicate = -1;  // 斷號ID和重號ID// 查找重號for (auto& pair : idCount) {if (pair.second == 2) {duplicate = pair.first;  // 找到重號break;}}// 查找斷號for (int i = ids[0]; i <= ids.back(); i++) {if (idCount.find(i) == idCount.end()) {missing = i;  // 找到斷號break;}}// 輸出結果cout << missing << " " << duplicate << endl;return 0;
}

代碼思路

?1. 輸入處理

讀取數據行數?N。
使用?unordered_map<int, int>?統計每個ID出現的次數。
使用?vector<int>?存儲所有ID，方便后續排序。

?2. 讀取所有ID

使用?while (cin >> num)?逐行讀取ID，直到遇到換行符?\n?結束當前行的讀取。
將每個ID存入?vector<int> ids?中，并在?unordered_map<int, int> idCount?中統計其出現次數。

?3. 排序

對?vector<int> ids?進行排序，方便后續查找斷號和重號。

?4. 查找重號

遍歷?unordered_map<int, int> idCount，找到出現次數為2的ID，即為重號。

?5. 查找斷號

從最小ID（ids[0]）到最大ID（ids.back()）遍歷，檢查每個ID是否在?unordered_map<int, int> idCount?中。
如果某個ID不在?unordered_map?中，則說明它是斷號。

?6. 輸出結果

輸出斷號ID?missing?和重號ID?duplicate。

?代碼實現細節

?1. 頭文件

#include<bits/stdc++.h>
using namespace std;

使用萬能頭文件?bits/stdc++.h，包含所有標準庫。
使用?using namespace std，避免每次調用標準庫時需要寫?std::。

?2. 主函數

int main() {int N;cin >> N;

讀取數據行數?N。

?3. 數據存儲

unordered_map<int, int> idCount;
vector<int> ids;
int num;

unordered_map<int, int> idCount：用于統計每個ID出現的次數。
vector<int> ids：用于存儲所有ID，方便后續排序。

?4. 讀取所有ID

for (int i = 0; i < N; i++) {while (cin >> num) {ids.push_back(num);idCount[num]++;if (cin.get() == '\n') break;}
}

逐行讀取ID，存入?vector<int> ids?中。
使用?unordered_map<int, int> idCount?統計每個ID出現的次數。
當遇到換行符?\n?時，結束當前行的讀取。

?5. 排序

sort(ids.begin(), ids.end());

對?vector<int> ids?進行排序，方便后續查找斷號和重號。

?6. 查找重號

int missing = -1, duplicate = -1;
for (auto& pair : idCount) {if (pair.second == 2) {duplicate = pair.first;break;}
}

遍歷?unordered_map<int, int> idCount，找到出現次數為2的ID，即為重號。

?7. 查找斷號

for (int i = ids[0]; i <= ids.back(); i++) {if (idCount.find(i) == idCount.end()) {missing = i;break;}
}

從最小ID（ids[0]）到最大ID（ids.back()）遍歷，檢查每個ID是否在?unordered_map<int, int> idCount?中。
如果某個ID不在?unordered_map?中，則說明它是斷號。

?8. 輸出結果

cout << missing << " " << duplicate << endl;

輸出斷號ID?missing?和重號ID?duplicate。

?9. 返回

return 0;

程序正常結束。

?示例運行

?輸入

2
7 9
5 6 8 11 9

?輸出

10 9

?總結

代碼通過?unordered_map?統計ID出現次數，結合排序和遍歷，高效地找到斷號和重號。
時間復雜度為?O(n)，其中?n?是ID的總數。
代碼邏輯清晰，適合處理題目描述中的場景。

還有另一種形式（不排序，直接使用哈希表）：

#include <iostream>
#include <unordered_set>
using namespace std;int main() {int N;cin >> N;  // 讀取數據行數unordered_set<int> idSet;  // 用于存儲所有IDint minID = INT_MAX, maxID = INT_MIN;  // 記錄最小ID和最大IDint num;// 讀取所有IDfor (int i = 0; i < N; i++) {while (cin >> num) {idSet.insert(num);  // 將ID存入哈希表minID = min(minID, num);  // 更新最小IDmaxID = max(maxID, num);  // 更新最大IDif (cin.get() == '\n') break;  // 換行時結束當前行的讀取}}int missing = -1, duplicate = -1;  // 斷號ID和重號ID// 查找重號unordered_set<int> seen;for (int id : idSet) {if (seen.count(id)) {duplicate = id;  // 找到重號break;}seen.insert(id);}// 查找斷號for (int i = minID; i <= maxID; i++) {if (idSet.find(i) == idSet.end()) {missing = i;  // 找到斷號break;}}// 輸出結果cout << missing << " " << duplicate << endl;return 0;
}

二、P8775 [藍橋杯 2022 省 A] 青蛙過河 - 洛谷?

算法代碼：?

#include <bits/stdc++.h>
#define N 100005
using namespace std;int n, T, h[N], ans;int main() {// 讀取河的寬度 n 和需要去學校的天數 Tscanf("%d%d", &n, &T);// 將 T 乘以 2 得到實際過河的次數T <<= 1;// 讀取每塊石頭的高度for (int i = 1; i < n; ++i) scanf("%d", &h[i]);// 使用滑動窗口的方法來找到滿足條件的最小跳躍能力for (int i = 1, j = 0, sum = 0; i < n; i++) {// 擴展窗口的右邊界，直到累加的高度大于等于 Twhile (j < n && sum < T) sum += h[++j];// 記錄當前窗口的長度，即跳躍能力ans = max(ans, j - i + 1);// 縮小窗口的左邊界，減去左邊石頭的高度sum -= h[i];}// 輸出滿足條件的最小跳躍能力printf("%d\n", ans);return 0;
}

規律：

????????對于一個跳躍能力?y，青蛙能跳過河?2x?次，當且僅當對于每個長度為?y?的區間，這個區間內?h?的和都大于等于?2x

????????這個問題涉及到對青蛙跳躍能力和石頭高度分布的分析。我們需要理解為什么對于一個跳躍能力?y，青蛙能夠跳過河?2x次，當且僅當對于每個長度為?y?的區間，這個區間內石頭高度?h?的和都大于等于?2x。

1.?問題背景

青蛙需要往返?2x?次，每次跳躍必須落在石頭或岸上。
每塊石頭的高度?h[i]表示這塊石頭可以被踩的次數。
跳躍能力?y?表示青蛙一次跳躍的最大距離。

2.?跳躍能力?y?的含義

如果青蛙的跳躍能力是?y，那么它每次跳躍的距離不能超過?y。
這意味著青蛙在跳躍時，只能選擇距離當前位置不超過?y?的石頭。

3.?為什么需要每個長度為?y?的區間和 ≥2x

必要性：
- 如果存在一個長度為?y的區間，其石頭高度和 <2x，那么青蛙在這個區間內無法完成?2x?次跳躍。
- 因為青蛙每次跳躍必須落在石頭上，而石頭的高度限制了可以被踩的次數。
- 如果某個區間的石頭高度和不足 2x，青蛙在這個區間內無法完成足夠的跳躍次數。
充分性：
- 如果每個長度為?y?的區間的石頭高度和 ≥2x，那么青蛙可以在每個區間內完成足夠的跳躍次數。
- 因為青蛙的跳躍能力是?y，它可以在每個區間內自由選擇石頭進行跳躍，而不會受到石頭高度不足的限制。

4.?具體分析

青蛙的跳躍路徑：
- 青蛙需要從起點跳到終點，再跳回起點，重復?x?次。
- 每次跳躍的距離不能超過?y。
區間的劃分：
- 將河分成若干個長度為?y?的區間。
- 每個區間內的石頭高度和必須≥2x，因為青蛙需要在這些區間內完成?2x2x?次跳躍。
石頭高度的作用：
- 每塊石頭的高度?h[i] 表示這塊石頭可以被踩的次數。
- 如果某個區間的石頭高度和<2x，那么青蛙在這個區間內無法完成 2x?次跳躍。

5.?舉例說明

假設：

河的寬度?n=5。
需要去學校的天數?x=1，實際過河次數 2x=2。
石頭高度?h=[3,1,2,1]。

跳躍能力?y=2：

區間劃分：
- 區間 1: 位置 1 和 2，高度和 3+1=4≥2。
- 區間 2: 位置 2 和 3，高度和 1+2=3≥2。
- 區間 3: 位置 3 和 4，高度和 2+1=3≥2。
每個區間的石頭高度和都?≥2，因此青蛙可以完成?2?次跳躍。

跳躍能力 y=1：

區間劃分：
- 區間 1: 位置 1，高度和 3≥2。
- 區間 2: 位置 2，高度和 1<2。
- 區間 3: 位置 3，高度和 2≥2。
- 區間 4: 位置 4，高度和 1<2。
存在區間的石頭高度和?<2，因此青蛙無法完成?2?次跳躍。

6.?總結

對于一個跳躍能力?y，青蛙能夠跳過河 2x?次，當且僅當對于每個長度為?y?的區間，這個區間內石頭高度?h?的和都大于等于 2x。
這是因為青蛙的跳躍能力限制了它每次跳躍的距離，而石頭的高度限制了它可以在每塊石頭上踩的次數。
如果某個區間的石頭高度和不足2x，青蛙在這個區間內無法完成足夠的跳躍次數。
如果每個區間的石頭高度和都 ≥2x，青蛙可以在每個區間內自由選擇石頭進行跳躍，完成?2x次跳躍。

代碼思路：

這段代碼的目的是通過滑動窗口的方法，找到小青蛙的最小跳躍能力?y，使得它能夠完成?2x?次往返跳躍。以下是代碼的詳細思路：

1.?輸入處理

讀取河的寬度?n?和需要去學校的天數?T：
- 使用?scanf("%d%d", &n, &T);?讀取輸入。
- 河的寬度?n?表示從起點到終點共有?n?個位置（包括起點和終點）。
- T?是小青蛙需要去學校的天數，實際過河次數是?2T（往返各一次）。
將?T乘以 2：
- 使用?T <<= 1;?將?T左移一位，相當于?T=2T，表示實際過河次數。

2.?讀取石頭高度

讀取每塊石頭的高度：
- 使用?for (int i = 1; i < n; i++) scanf("%d", &h[i]);?讀取每塊石頭的高度。
- 數組?h?的下標從 1 開始，表示從起點到終點之間的?n?1塊石頭的高度。
- h[i]表示距離起點?i的位置的石頭高度。

3.?滑動窗口尋找最小跳躍能力

初始化滑動窗口：
- 使用?for (int i = 1, j = 0, sum = 0; i < n; ++i)?初始化滑動窗口。
- i是窗口的左邊界，表示當前跳躍的起點。
- j是窗口的右邊界，表示當前跳躍的終點。
- sum 是窗口內石頭高度的累加和。
擴展窗口的右邊界：
- 使用?while (j < n && sum < T) sum += h[++j];?擴展窗口的右邊界。
- 不斷將右邊界?j向右移動，累加石頭的高度，直到累加的高度?sum大于等于?T。
- 這一步的目的是找到一個窗口，使得窗口內的石頭高度總和足夠支持?2T?次跳躍。
記錄窗口的長度：
- 使用?ans = max(ans, j - i + 1);?記錄當前窗口的長度。
- 窗口的長度?j?i+1表示當前跳躍能力?y。
- 通過取最大值，確保找到最小的跳躍能力。
縮小窗口的左邊界：
- 使用?sum -= h[i];?縮小窗口的左邊界。
- 將左邊界?i?向右移動，減去左邊石頭的高度，繼續尋找更小的跳躍能力。

4.?輸出結果

輸出滿足條件的最小跳躍能力：
- 使用?printf("%d\n", ans);?輸出結果。
- ans 是滿足條件的最小跳躍能力?yy。

代碼的核心思想：

滑動窗口：
- 通過滑動窗口的方法，動態調整窗口的左右邊界，找到一個最小的窗口長度?y，使得窗口內的石頭高度總和至少為?T。
- 窗口的長度?y?表示小青蛙的跳躍能力。
跳躍能力的定義：
- 跳躍能力?y?表示小青蛙一次跳躍的最大距離。
- 通過滑動窗口找到的?y是最小的跳躍能力，使得小青蛙能夠完成?2T?次跳躍。

代碼的優化點：

滑動窗口的邊界處理：
- 窗口的右邊界?j?不能超過?n，否則會越界。
- 窗口的左邊界?i?逐步向右移動，確保窗口長度最小。
時間復雜度：
- 滑動窗口的時間復雜度是?O(n)，因為每個石頭最多被訪問兩次（一次擴展右邊界，一次縮小左邊界）。
- 這種方法在?n≤10**5 的規模下非常高效。