4小時編碼練習計劃，專注于貪心算法和復雜模擬題，旨在鍛煉您的算法思維、代碼實現能力和耐心。

下午 (4小時): 貪心思維與代碼實現力

今天的重點是兩種在算法競賽和工程中都至關重要的能力：貪心選擇和復雜邏輯的精確實現。貪心算法考察的是能否洞察問題的本質，做出局部最優決策；而復雜模擬題則考驗代碼的組織能力、細節處理和調試耐心，這同樣是CCF認證考試中的高頻考點。

練習計劃概覽

• 總時長:?約 4 小時

• 核心目標:

  1. 理解貪心算法的本質：在每一步選擇中都采取當前狀態下最好或最優的選擇，從而希望導致全局結果最好或最優。

  2. 學習并實踐經典的貪心模型，如區間調度問題。

  3. 挑戰一道需求復雜、規則繁多的CCF真題，鍛煉將大段文字描述轉化為精確代碼邏輯的能力。

  4. 提升代碼調試能力和處理繁雜邏輯時的耐心與細致度。

---

第一部分：貪心算法——洞察局部最優解 (約 1.5 小時)

貪心算法的核心在于“貪”。它不從整體最優上加以考慮，所做的選擇只是在某種意義上的局部最優解。關鍵在于，你需要判斷并證明這種局部最優選擇能否導向全局最優。

題目編號	題目名稱	核心知識點	練習目標
P1803	凌亂的yyy / 線段覆蓋	貪心,?排序,?區間問題	經典必做題。這是最經典的貪心問題之一：活動選擇問題。學習如何通過對區間的某個關鍵屬性（如結束時間）進行排序，然后進行貪心選擇，以達成覆蓋最多線段（或安排最多活動）的目標。
CCF202303-2	墾田計劃	貪心,?二分答案	在有限資源下，如何分配資源以最小化總體耗時。這是一個“二分答案 + 貪心驗證”的經典模型。貪心體現在：當我們確定一個目標天數后，總是優先在“性價比”最高（縮短一天耗費資源最少）的田地上投入資源。

題解

//P1803-先處理數據，然后貪心計算。#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int main(){int n;cin >> n;int now = 0;int cnt = 0;vector<pair<int,int>> v;    while(n--){int start,end;cin >> start >> end;v.push_back(make_pair(start,end));}sort(v.begin(),v.end(),[](auto a,auto b){return a.second < b.second;});for(auto p : v){if(p.first>=now){now = p.second;cnt++;}}cout << cnt;return 0;
}

//29-2 使用二分限定范圍，然后用貪心判斷這個各個情況下的可行性和結果#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n, m, k;cin >> n >> m >> k;vector<pair<int, int>> areas(n); // {time, cost}for(int i = 0; i < n; i++){cin >> areas[i].first >> areas[i].second; // time, cost}// 二分查找最優答案int left = k, right = 0;for(int i = 0; i < n; i++){right = max(right, areas[i].first);}while(left < right){int mid = (left + right) / 2;long long need = 0;// 計算達到mid天數需要的總資源for(int i = 0; i < n; i++){if(areas[i].first > mid){need += (long long)(areas[i].first - mid) * areas[i].second;}}if(need <= m){right = mid;} else {left = mid + 1;}}cout << left << endl;return 0;
}

練習建議:

• P1803: 解決此題的關鍵在于想清楚應該按什么標準進行排序。按開始時間？按區間長度？還是按結束時間？嘗試思考不同排序策略的優劣，并理解為什么“按結束時間升序排序”是正確的貪心策略。

• CCF202303-2: 這類問題直接貪心不好做，但可以思考：如果我猜最終答案是?T?天，我能否用現有的?m?個資源實現這個目標？這個“能否實現”的子問題就可以用貪心來快速判斷。這是一種非常重要的思想。

---

第二部分：復雜模擬——代碼實現的試金石 (約 2 小時)

這類題目通常沒有復雜的算法，但規則繁多、細節量大，極其考驗代碼的組織能力、細心程度和調試能力。在CCF認證中，這類題目通常是區分選手代碼硬實力的關鍵。

（請從以下兩題中精選一題進行攻克）

題目編號	題目名稱	核心知識點	練習目標
選項A： CCF202305-3	解壓縮	字符串處理,?位運算,?模擬	完美復刻您提到的“耐心編碼實現”目標。需要嚴格按照題目給定的、包含多種情況的壓縮格式進行字節流解析。這道題將極大地鍛煉您對題意的精確理解和代碼的嚴謹性。
選項B： CCF202303-3	LDAP	字符串解析,?遞歸/棧,?模擬	類似于“JSON查詢”，本題需要解析一種帶有邏輯與/或的嵌套查詢語言。您需要設計數據結構來存儲用戶信息，并使用遞歸或棧來解析查詢表達式，是練習復雜邏輯和數據處理的絕佳選擇.

題解

//30-3 重難點就在理解那三四版的內容，然后轉化成代碼，注意邊界處理，實則主要是耗時和注意力。#include <iostream>
#include <cstdio>
#include <string>using namespace std;
typedef long long LL;
const int N = 5e6 + 10;char str[N], ret[N];
int s, cnt, i;int tran(string str, int t) { // t進制轉十進制int ret = 0;for (int i = 0; i < str.size(); i++) {if (isdigit(str[i])) ret = ret * t + str[i] - '0';else ret = ret * t + str[i] - 'a' + 10;}return ret;
}string twostr(char c1, char c2) { // 16進制轉2進制string ret = "00000000";int a = isdigit(c1) ? c1 - '0' : c1 - 'a' + 10, b = isdigit(c2) ? c2 - '0' : c2 - 'a' + 10; // 改為數字for (int i = 3; i >= 0 && a; i--) { // 前四位ret[i] = a % 2 + '0';a /= 2;}for (int i = 7; i >= 4 && b; i--) { // 后四位ret[i] = b % 2 + '0';b /= 2;}return ret;
}int main() {cin >> s;for (int i = 0; i < (s - 1) / 8 + 1; i++) scanf("%s", str + i * 16);for (i = 0; i < s * 2; i += 2) { // 引導域string ss; ss += str[i]; ss += str[i + 1];if (tran(ss, 16) < 128) break; // 最高位為0，退出}for (i += 2; i < s * 2; i += 2) {string ss = twostr(str[i], str[i + 1]);if (ss[6] == '0' && ss[7] == '0') { // 字面量int le = tran(ss.substr(0, 6), 2), p, ct; // 獲取字面量長度-1的值if (le >= 60) { // le+1>=61int dx = le - 59; // 存儲字面量長度的字節數string lee;for (p = i + dx * 2; p > i; p -= 2) { // 小端序拼接lee += str[p]; lee += str[p + 1];}le = tran(lee, 16); // 獲取字面量長度-1的值i += dx * 2;}for (p = i + 2, ct = 0; ct < le + 1; p += 2, ct++) { // 存儲字面量字節ret[cnt++] = str[p];ret[cnt++] = str[p + 1];}i = p - 2;}else { // 回溯引用int l, o;if (ss[6] == '0' && ss[7] == '1') { // 01形式l = tran(ss.substr(3, 3), 2) + 4;ss = ss.substr(0, 3); ss += twostr(str[i + 2], str[i + 3]);i += 2;o = tran(ss, 2);}else { // 10形式l = tran(ss.substr(0, 6), 2) + 1;ss.clear(); ss += str[i + 4]; ss += str[i + 5]; ss += str[i + 2]; ss += str[i + 3];i += 4;o = tran(ss, 16);}int pcnt = cnt / 2; // 存一下現在的字節數for (int p = 2 * (pcnt - o), ct = 0; ct < l; p += 2, ct++) { // 從第pcnt-o個字節開始，輸出l個字節if (o < l && p == 2 * pcnt) p = 2 * (pcnt - o); // 如果o<l，且到了末尾，回到起點，反復輸出ret[cnt++] = ret[p];ret[cnt++] = ret[p + 1];}}}for (int i = 0; i < cnt; i++) {if (i && i % 16 == 0) cout << endl;cout << ret[i];}return 0;
}

練習建議:

• 先規劃再動手: 在寫代碼之前，花15-20分鐘仔細閱讀題目，用紙筆把所有規則、分支和狀態轉移想清楚。可以為不同的功能模塊設計獨立的函數（如“解析一個元素”、“處理一次查詢”），讓主邏輯更清晰。

• 分步驗證: 不要試圖一次性寫完所有代碼。可以先實現最核心、最簡單的部分（例如，只處理一種類型的元素或一種查詢），驗證無誤后，再逐步添加其他復雜情況。

• 利用樣例: 充分利用題目給出的樣例，一步步手動模擬程序執行過程，對比自己的輸出和預期輸出，可以幫助快速定位邏輯錯誤。

---

目標達成自查 (約 0.5 小時)

完成以上練習后，進行復盤和總結：

1. 關于貪心算法:

   • 我解決貪心問題的一般思路是什么？（例如：排序 -> 循環 -> 按規則選擇）

   • 墾田計劃?這道題，為什么不能直接貪心，而要結合二分？（因為貪心的“性價比”會隨著目標天數的改變而改變，沒有一個固定的貪心標準）

2. 關于復雜模擬:

   • 在處理?解壓縮?或?LDAP?時，我遇到了哪些困難？（例如：邊界條件、狀態管理、字符串處理的細節）

   • 我是如何組織我的代碼來避免邏輯混亂的？（例如：使用結構體、類、輔助函數）

   • 如果再做一次，哪些地方可以改進，從而更快更準確地完成編碼？