NOIP 2014 非官方題解：兩天六題完整思路與代碼框架

NOIP 2014 非官方題解：兩天六題完整思路與代碼框架

NOIP 2014 提高組試題回顧，涵蓋模擬、樹上統計、背包、圖論、多項式驗譱等核心考點。本文提供各題核心思路、關鍵算法與複雜度分析。

Day 1

T1 珠心算測驗（模擬）

直接按題意模擬加減乘除運算，注意大數處理（高精度或模多質數）。考察基本編程能力，無算法難點。

T2 圖上最短路（樹上距離統計）

關鍵洞察：n 點 n-1 邊無向圖必為樹。求所有距離為 2 的點對 (u,v) 的權值乘積和與最大值。
方法一（ydc）：枚舉中間點 i，其鄰居兩兩距離為 2。對鄰居權值數組求 Σaᵢaⱼ (i≠j) 及最大乘積。
Σaᵢaⱼ = (Σaᵢ)² - Σaᵢ²，或累加 aᵢ·(sum-aᵢ)。
最大乘積 = 最大值 × 次大值。
復雜度 O(n)。
方法二：枚舉點，DFS 找孫子節點，統計乘積。需注意避免重複計算。

T3 廣播（完全背包變種）

n 種廣播，每種有覆蓋範圍、成本、可用次數。目標覆蓋 [1,m] 區間，最小成本。
狀態：dp[i] 覆蓋到 i 的最小成本。
轉移：對每種廣播，dp[j] = min(dp[j], dp[max(0,j-len)] + cost)。
完全背包優化 O(nm)。記憶化搜索 O(nm²) 可得部分分。

Day 2

T1 路由器（網格圖最短路/模擬）

網格地圖，路由器只能放路口。求最少路由器覆蓋所有道路。本質為最小點覆蓋或貪心放置，注意邊界條件。

T2 旅行（反圖 BFS + 狀態過濾）

有向圖求 1→n 最短路，但部分點不可經過。
正解：
1. 建反圖，從 n 反向 BFS/SPFA 求所有能到達 n 的點。
2. 預處理：刪除不符合條件的點（如死胡同、不可達點）。
3. 正圖上從 1 BFS/SPFA 求最短路。
關鍵：反圖預處理縮小搜索空間。

T3 多項式（拉格朗日定理 + 模質數驗證）

給定多項式 f(x)，求 x∈[1,m] 使 f(x)≡0 (mod P) 的所有解。n,m ≤ 10⁵。
暴力 O(nm) 過不了。
策爺做法（O(n√(nm))）：
1. 取質數 P ≈ √(nm)。
2. 對 x∈[0,P-1] 驗證 f(x)≡0 (mod P)，得 ≤n 個模 P 解（拉格朗日定理）。
3. 每個模 P 解在 [1,m] 中對應 ≤ m/P 個候選，逐個驗證（高精度或多質數取模）。
4. 總驗證次數 ≤ n·m/P，總復雜度 O(nP + n·m/P) = O(n√(nm))。
高精度位數過長會 TLE，建議用多質數取模（如 3 個 10⁹ 級質數）避免高精度開銷。

總結與心得

NOIP 2014 整體偏向基礎算法綜合應用，重點考察：樹論、背包、圖論預處理、數論在算法中的應用。T3 是區分度最大的題目，需要數學洞察與工程落地能力並重。