第 12 屆浙江省大學生程式設計競賽部分題解（A、G、H、J、L、D）

A. Ace of Aces — 眾數唯一性判斷

統計每個 ID 的票數，找最大值；若最大值唯一輸出該 ID，否則輸出 Nobody。O(N) 哈希表即可。

G. Lunch Time — 三類菜品中位數價格求和

每類菜品按價格排序，取中位數（偶數取較大者），輸出總價與菜名。O(N log N) 排序。

H. May Day Holiday — 連續假期天數計算

五一假期 5 月 1 日~5 日，結合周末（周六日）計算連續放假天數。核心是求某年 5 月 1 日星期幾，利用蔡勒公式或累積天數模 7。預計算 1928~9999 年答案，O(1) 查詢。

J. Convert QWERTY to Dvorak — 鍵盤映射轉換

建立 QWERTY→Dvorak 字符映射表（含大小寫、符號），逐字符轉換輸入流。注意 Caps Lock 壞鍵不處理大小寫切換。

L. Demacia of the Ancients — 隊伍等級計算

統計 MMR > 6000 的成員數，即為隊伍等級。O(N) 計數。

D. Beauty of Array — 所有連續子數組不同元素和的總和

核心公式：對每個值 v，考慮其出現位置 p₁ < p₂ < … < p_k。
子數組包含 v 的條件是左端點 ≤ p_i 且右端點 ≥ p_i。
用「間隔法」：在數組首尾添加虛擬位置 0 和 n+1，相鄰兩次出現間的子數組**不包含** v。
總子數組數 = n(n+1)/2。
v 的貢獻 = v × (總子數組數 − Σ C(間隔長度, 2))。
O(N) 預處理位置向量，O(不同值數) 計算。

代碼片段（D 題核心）

vector pos[MAXV];
long long ans = 0;
for (int v = 1; v <= maxVal; ++v) if (!pos[v].empty()) {
    long long total = 1LL * n * (n + 1) / 2;
    long long without = 0;
    int last = 0;
    for (int p : pos[v]) {
        int gap = p - last - 1;
        without += 1LL * gap * (gap + 1) / 2;
        last = p;
    }
    without += 1LL * (n - last) * (n - last + 1) / 2;
    ans += 1LL * v * (total - without);
}