BestCoder Round #11 (Div. 2) 參賽心得與題目解析

比賽概況

BestCoder Round #11 Div. 2 於 2014 年舉行，對應 HDU 5054~5057 四道題目。作為 Div. 2 參賽者，僅完成部分題目，以下記錄各題核心思路與踩坑經驗，供同好參考。

題目列表

• HDU 5054 Alice and Bob
• HDU 5055 Bob and math problem
• HDU 5056 Boring count
• HDU 5057 Argestes and Sequence

重點題目解析

HDU 5054 / 1001 - 碰面問題

題意：兩人從 (0,0) 和 (n,m) 同時出發，以相同速度向對方起點移動，判斷是否能在坐標中點相遇。
解法：中點座標為 ((0+n)/2, (0+m)/2) 與 ((n+0)/2, (m+0)/2) 重合，僅需判斷 x == n-x && y == m-y，即 2x==n && 2y==m。注意浮點精度，使用 eps 比較。

HDU 5055 / 1002 - Bob and math problem

題意：給定 n 個數字（含正負），重新排列組成一個無前導零的整數，使其為奇數且盡可能大。若無解輸出 -1。
關鍵觀察：

• 末位必須是奇數，故至少需要一個奇數數字。
• 若 n=1 且該數為偶數，無解。
• 若所有非零數字均為偶數，無解。

貪心構造：從大到小排序數字，優先選最大的奇數作為末位，其餘按降序排列。需特別處理 5\n1 0 0 0 0（答案 -1）與 5\n1 1 0 0 0（答案 10001）等邊界情況。比賽時用 DFS 暴力搜索意外通過，事後補充貪心證明。

HDU 5056 / 1003 - Boring count

題意：給定小寫字母串 S，統計子串中每個字母出現次數不超過 K 的子串個數。
解法：雙指針/滑動窗口 O(n)。維护窗口 [l, r] 內字符計數，右端點 r 掃描，若某字符超限，移動 l 直到合法。以 r 結尾的合法子串數為 r-l+1，累加即得答案。
複雜度：O(|S|) 時間，O(1) 空間（26 個計數器）。

HDU 5057 / 1004 - Argestes and Sequence

題意：維護一個數列，支持區間操作與查詢。
嘗試：線段樹實現導致 MLE（記憶體限制嚴格）。嘗試用 unsigned short 壓縮節點內存，或改用 Splay / Treap 等動態結構。比賽未解出，賽後需補齊。

比賽感悟

• Div. 2 題目質量不錯，考察基礎演算法（雙指針、貪心、數位 DP、數據結構）。
• 邊界情況極易丟分，如 n=1、全零、前導零等，需構造極端測試數據自測。
• 內存限制緊時，需考慮數據類型優化（如 short 代替 int）、靜態數組池、或改用更省內存的結構。

附：部分參考代碼片段

// 1001 碰面判斷
while (~scanf("%d%d%lf%lf", &n, &m, &x, &y)) {
    double x1=x, y1=y, x2=n-x, y2=m-y;
    if (fabs(x1-x2)<=eps && fabs(y1-y2)<=eps) puts("YES");
    else puts("NO");
}

// 1002 奇數構造（貪心框架）
sort(a, a+n, greater<int>());
int last_odd = -1;
for (int i=n-1; i>=0; --i) if (a[i]&1) { last_odd=i; break; }
if (last_odd==-1 || (n>1 && last_odd==0 && a[0]==0)) { puts("-1"); continue; }
for (int i=0; i