UVa AOAPC Volume 1 字符串專題 9 道經典題目完整解析與 AC 代碼

專題概覽

AOAPC（算法競賽入門經典）Volume 1 字符串章節共 9 道題，涵蓋回文/鏡像判斷、矩陣字符串搜索、模式替換、敏感詞統計、編碼解碼、單詞提取排序、前綴碼判斷、自動編輯等核心技能。本文提供統一風格的題意提煉、算法思路、關鍵代碼與避坑指南。

1. 401 - Palindromes：回文與鏡像雙重判定

任務：判斷字符串是普通回文、鏡像字符串、鏡像回文、還是都不是。鏡像映射表固定（如 A↔A, 3↔E, 2↔S, 5↔Z, 8↔8...）。

關鍵點：

• 構建 char mirror[256] 查表 O(1) 判斷鏡像字符
• 雙指針同時檢查回文（s[i]==s[j]）與鏡像（s[i]==mirror[s[j]]）
• 中間字符也要檢查鏡像性（如單字符 "3" 是鏡像但非回文）

2. 10010 - Where's Waldorf?：矩陣 8 方向字符串搜索

任務：在 m×n 字符矩陣中尋找 k 個查詢詞，允許 8 方向（橫豎斜），大小寫不敏感，輸出首次出現的 1-based 座標。

優化技巧：

• 預處理：矩陣與查詢詞統一轉小寫
• 8 方向向量 dx[8]={-1,-1,-1,0,0,1,1,1}, dy[8]={-1,0,1,-1,1,-1,0,1}
• 對每個起始位置嘗試 8 方向，邊界檢查用 0 <= x+len*dx < m
• 多測試用例間輸出空行，最後一組不輸出

3. 10361 - Automatic Poetry：標記區間交換重組

任務：輸入兩行，第一行含兩對 <...>，第二行以 ... 結尾。輸出：第一行去標記；第二行將 ... 替換為 <第三段><第二段><第一段><第四段>。

核心邏輯：

1. 掃描記錄 p1< p2> p3< p4> p5. 五個關鍵位置
2. 提取四段：s1=p1+1..p2-1, s2=p2+1..p3-1, s3=p3+1..p4-1, s4=p4+1..end
3. 輸出 1：拼接 s1 s2 s3 s4（去標記）
4. 輸出 2：s3 s2 s1 s4 替換 ...

4. 537 - Artificial Intelligence?：物理公式 P=UI 求解

任務：給定 P、U、I 中任意兩個（含單位 m/k/M），求第三個。公式 P=U*I。

解析關鍵：

• 以 = 定位數值，解析浮點數（含小數點）
• 單位換算：m=1e-3, k=1e3, M=1e6
• 根據已知量組合分支計算：P=U*I, U=P/I, I=P/U
• 輸出格式：Problem #n\nX=%.2fUnit\n，單位固定（W/V/A）

5. 409 - Excuses, Excuses!：敏感詞全詞匹配計數

任務：給 m 個敏感詞、n 個句子，找出包含敏感詞最多的句子（大小寫不敏感，全詞匹配，重複計數）。

關鍵難點：

• 全詞匹配：左右必須非字母（或邊界），如 "home" 不匹配 "homework"
• 實現：句子轉小寫，對每個敏感詞 strstr 循環查找，檢查前後字符
• 統計每句計數，輸出最大計數對應的原始句子

6. 10878 - Decode the tape：二進制編碼解碼

任務：輸入多行，每行 10 字符（_、o、.），o=1, _=0，忽略 .，按位權 128,64,8,4,2,1（注意順序）解碼為 ASCII 字符。以全 _ 行結束（兩行）。

簡潔實現：

while (gets(line)) {
    if (line[0]=='_' && ...) break;
    int val = 0, bit = 128;
    for (int i=1; i<9; ++i) { // 只看 8 個有效位
        if (line[i]=='o') val += bit;
        bit >>= 1;
    }
    putchar(val);
}

7. 10815 - Andy's First Dictionary：單詞提取、去重、字典序排序

任務：讀取所有輸入行，提取單詞（連續字母，大小寫不敏感），轉小寫，去重，字典序輸出。

工程實現：

• 全文讀入，非字母替換為空格
• strtok 分割單詞存入 vector
• sort + unique 或 set 去重排序
• 數據量陷阱：題目說 5000 詞，實際測試數據可達 2-3 萬，必須用 O(n log n) 排序，不可用冒泡

8. 644 - Immediate Decodability：前綴碼判斷

任務：每組最多 10 個二進制碼字，判斷是否存在一個是另一個的前綴（即非即時可解碼）。以 9 結束組，EOF 結束。

暴力可行：n≤10，兩兩 strncmp 比較長度較短者即可。或構建 Trie 樹插入檢查（練手用）。

9. 10115 - Automatic Editing：多規則順序字符串替換

任務：給 t 組替換規則 (from, to)，對目標串依次應用每條規則：從左到右找到所有非重疊匹配並替換，規則間順序執行。

實現要點：

• 對每條規則，在當前串中反覆 find 並 replace，注意替換後位置後移 to.length()
• C 風格需手動實現 strstr + 內存移動（memmove）擴縮字符串
• 測試自造用例覆蓋：替換後長度增/減、重疊匹配不重複替換、規則鏈式作用

通用避坑清單

1. 輸入處理：gets/getline 讀整行，scanf 後記得 getchar() 吃掉換行
2. 多測試用例格式：組間空行，最後一組無尾隨空行
3. 大小寫不敏感：統一 tolower 處理
4. 邊界條件：空串、單字符、全匹配、無匹配
5. 性能：字符串操作用 string 或預分配緩衝區，避免 O(n²) 拷貝

總結

這 9 題橫跨字符串處理的查找、匹配、替換、編碼、排序、統計全谱系。掌握它們，意味著你已具備了解決 80% 以上 ACM 字符串題的核心工具箱。建議：手寫一遍每道題的核心函數，體會指針/迭代器邊界、內存移動、狀態機設計的細微差別——這才是從「會做」到「精通」的分水嶺。