第26次的云智計劃總結
這是第 \(26\) 次的云智計劃，這次考得不太好，只有 \(50 + 40 + 0 + 100 = 190\), 我們一個一個分析哈~~
第一道題是什么原因呢？因為算法是 \(O(nlog_n)\) , 由于 \(\sum n \le 10^6\) 時限是 \(1000ms\)，這本來是分分鐘就能過的，但是，它由于要用到 \(or\) 這個時間復雜度就多乘了一個 \(w\) ，這個 \(w\) 可是約等于 \(8\) 納，然而，我又沒有關同步流，就 \( TLE\) 得只剩 \(50 pts\) 了，我下次一定要關同步流了！雖然你關了同步流不一定能過，但是這分數肯定比不關同步流來的高呀，再說了，不會造極限數據嗎？
第二題又是什么原因呢？那叫一個純屬手欠！為啥？我本來是放棄去打 \( T2\) 滿分的，只想要 \(40\) 的，數組范圍只開到了 \(400\) 可后來想到了 \(100\) 的做法，結果范圍沒改回來.... 下次這種小問題一定要好好檢查！
第三題其實是大于 T4 ，大概有紫題的難度，不會，也沒有看 T4 ，亂寫了一個，但還是一分不得，還浪費了一個多小時。
第四道題真的不難，只有藍減的難度，最后半個小時多一點就想出來了可能是因為以前見過吧....
總結一下，是因為 \(T3\) 磕的時間太久，\(T1\)，\(T2\) 都沒來得及去細細檢查，本來能拿 \(300\) 的結果，不僅 \(T3\) 一分不得， \(T1, T2\) 還丟了 \(110\) 分，就算 \(T3AC\) 也補不回來。
這是通過 \(deepseek\) 的幫助列的比賽通用檢查表：
信息學競賽終極代碼檢查表
| 階段 | 大類別 | 細分類別 | 具體檢查項 | 注意事項/技術方案 | 完成 |
|---|---|---|---|---|---|
| Ⅰ. 編碼規范 (5min) | 1.1 格式控制 | 縮進 | □ 統一4空格縮進（禁用Tab） | IDE設置：強制空格替代Tab | □ |
| 行寬 | □ 單行≤100字符 | 字符串常量允許120字符 | □ | ||
| 花括號 | □ Stroustrup風格：if(){ 換行對齊 |
禁止Allman風格（獨占行） | □ | ||
| 1.2 命名規范 | 變量 | □ 小駝峰命名法（nodeCount） |
禁止拼音（shuzu） |
□ | |
| 常量 | □ 全大寫+下劃線（MAX_DEPTH=1000） |
宏定義也必須大寫 | □ | ||
| 函數 | □ 動詞開頭+名詞（calculateDiameter()） |
避免solve()等模糊命名 |
□ | ||
| 1.3 注釋管理 | 函數頭 | □ 注釋參數含義/返回值/功能 | 示例：// @brief: DFS遍歷樹// @param u: 當前節點, fa: 父節點 |
□ | |
| 關鍵邏輯 | □ 復雜算法步驟注釋 | 示例：// 此處使用Manacher算法擴展中心 |
□ | ||
| 調試注釋 | □ 刪除所有//DEBUG標記代碼 |
保留條件編譯塊：#ifdef LOCAL_DEBUG |
□ | ||
| Ⅱ. 邏輯健壯性 (15min) | 2.1 數據類型 | 整型選擇 | □ 1e5 * 1e5用long long |
宏全局覆蓋：#define int long long |
□ |
| 浮點處理 | □ 避免除法轉浮點 | 必須時用整數分母：a/(double)b → a*1.0/b |
□ | ||
| 精度控制 | □ 比較用abs(a-b)<EPS |
定義const double EPS=1e-9 |
□ | ||
| 2.2 內存管理 | 靜態數組 | □ int arr[100005] → int arr[100010] |
+5~10冗余 | □ | |
| 動態容器 | □ vector.reserve(n+5) |
減少擴容次數 | □ | ||
| 棧溢出 | □ DFS遞歸層>1000時改非遞歸 | Windows默認棧1MB | □ | ||
| 2.3 邊界檢查 | 輸入邊界 | □ n=0, n=1, n=1e5 |
數據生成器必含n=0 |
□ | |
| 循環邊界 | □ for(int i=0;i<n;)是否含等號 |
畫5元素示意圖驗證 | □ | ||
| 越界訪問 | □ dp[i][j]中j可能超界？ |
檢查二維數組第二維大小 | □ | ||
| 2.4 性能優化 | STL傳遞 | □ 函數參數用const vector<int>& |
禁止vector<int>值傳遞 |
□ | |
| 冗余拷貝 | □ 刪除臨時容器tmp=vec |
用swap移動語義 |
□ | ||
| 復雜度匹配 | □ n=1e5時O(n2) → TLE |
檢查雙重循環層數 | □ | ||
| Ⅲ. 調試驗證 (10min) | 3.1 對拍系統 | 暴力程序 | □ bf.cpp確保正確性 |
哪怕寫O(n!)爆搜也要實現 | □ |
| 數據生成器 | □ 覆蓋：升序/降序/全0/全負數/大數/RBT退化鏈 | 樹圖結構用鏈式/星形/菊花圖 | □ | ||
| 腳本監控 | □ Windows: @echo off循環檢測□ Linux: while ./gen | ./std; do; done |
輸出錯誤數據時暫停 | □ | ||
| 3.2 特殊測試 | 極限數據 | □ n=100000測TLE□ int_max=2147483647測溢出 |
計時命令：time ./std < data.in |
□ | |
| 浮點特測 | □ 1e18+1-1e18==0? 驗證大浮點精度損失 |
改用整數運算規避 | □ | ||
| 3.3 靜態查錯 | 符號檢查 | □ =→== □ |→| |
重點查if/while條件 | □ | |
| 初始化驗證 | □ 多組數據全局變量重置 | 使用初始化函數：void init(){ memset(head,-1,sizeof(head)); } |
□ | ||
| Ⅳ. 提交終檢 (5min) | 4.1 I/O安全 | 文件重定向 | □ 注釋freopen("in.txt","r",stdin) |
保留條件編譯：#ifndef ONLINE_JUDGE |
□ |
| 讀寫同步 | □ 添加ios::sync_with_stdio(false) |
必須搭配cin.tie(0) |
□ | ||
| 4.2 輸出規范 | 行末空格 | □ 最后一行無換行？ □ 用 i<n-1?" ":"\n"控制空格 |
Linux換行\n，禁止\r\n |
□ | |
| 精度輸出 | □ printf("%.6f",ans)保持6位小數 |
C++默認四舍五入 | □ | ||
| 4.3 編譯安全 | 頭文件 | □ 檢查#include<bits/extc++.h>是否允許 |
備用標準頭文件列表 | □ | |
| 編譯命令 | □ 本地測試與提交環境一致：g++ -std=c++17 -O2 |
禁止開-D_GLIBCXX_DEBUG |
□ | ||
| 禁用標識符 | □ 篩查：x1,y1,time,pipe,next |
用nxt,tm,pnt替代 |
□ | ||
| Ⅴ. 致命錯誤專項 | 5.1 內存越界 | 數組索引 | □ 訪問[0]或[n-1]時i-1變負？□ 樹鏈剖分 son[u]未判空？ |
防御性判斷：if(i>=0 && i<n) |
□ |
| 5.2 整型溢出 | 乘積溢出 | □ a*b可能>1e18？→ (ll)a*b |
中間變量強制轉型 | □ | |
| 位運算 | □ 1<<60 → 用1LL<<60 |
移位超32位必須long long | □ | ||
| 5.3 多線程問題 | 靜態變量 | □ 多組數據中static int cnt殘留值 |
全局變量必須顯式重置 | □ | |
| 隨機種子 | □ srand(time(0))導致對拍失敗 |
固定種子：srand(42) |
□ | ||
| 5.4 輸出崩潰 | 緩沖區未刷新 | □ printf后無fflush(stdout)？ |
交互題必須刷新 | □ | |
| 無效指針 | □ 訪問已釋放內存（C風格鏈表） | STL容器替代手工內存管理 | □ |
超高頻錯誤專項檢查
| 錯誤類型 | 檢查方案 | 應急方案 | 案例 |
|---|---|---|---|
| long long遺漏 | 查找[^l]long\s+int |
全局替換：sed -i 's/int main/long long main/g' |
ans未改LL，WA在99%測試點 |
| 數組開小 | 對拍滿數據n=100000觀察是否RE |
定義const int MAXN=1e5+100; |
vector未reserve導致隨機崩潰 |
| 多組數據殘留 | 構造連續2組相同輸入比對輸出差異 | 重寫初始化函數clear() |
鄰接表head數組未置-1 |
| 浮點截斷錯誤 | printf("%.0f", 5.0)→5 vs (int)round(5.0) |
統一轉整數：(int)(ans+0.5) |
floor(0.29 * 100)=28 |
| 迭代器失效 | 遍歷中修改vector/map |
用臨時容器存儲變更 | for(auto it:mp) mp.erase(it);崩 |
| 無解分支遺漏 | 構造無解數據測試 | 函數末尾加throw或assert(0) |
SPJ報"No Solution" |
競賽急救包代碼片段
// 內存檢測（僅調試用，提交前注釋掉！）
#define _GLIBCXX_DEBUG
// 棧空間擴展（64MB）
#include <sys/resource.h>
void init_stack() {
const rlim_t kStackSize = 64 * 1024 * 1024;
struct rlimit rl;
getrlimit(RLIMIT_STACK, &rl);
if (rl.rlim_cur < kStackSize) {
rl.rlim_cur = kStackSize;
setrlimit(RLIMIT_STACK, &rl);
}
}
// 多組數據初始化宏
#define reset_all() do{ \
memset(head, -1, sizeof(head)); \
edge_cnt = 0; \
} while(0)
浙公網安備 33010602011771號