Recent Contest #1 (Mar 2014) 題解匯總

比賽回顧

這是一次校內訓練賽，包含多道不同類型的題目，涉及模擬、概率、結論題、組合數學等。以下是各題關鍵思路與代碼片段。

A 題：大模擬

題意理解有誤導致失分。核心是計算總花費，每次可選擇「返回基地補給」或「原地等待」，取較小值累加。

#include <stdio.h>
#include <iostream>
using namespace std;
int events[100005];
int main() {
    int t; scanf("%d", &t);
    for (int i = 1; i <= t; i++) {
        long long n, a, b, s;
        cin >> n >> a >> b;
        s = a * 2 + b;
        for (int j = 0; j < n; j++) cin >> events[j];
        for (int j = 1; j < n; j++) {
            double back = a * 2 + b;
            double stay = (events[j] - events[j-1]) * b;
            s += (back > stay) ? stay : back;
        }
        cout << "Case #" << i << ": " << s << endl;
    }
    return 0;
}

E 題：水概率題

直接公式 1.0 / ((m+1)*k + 1)，輸出 8 位小數。

#include <iostream>
#include <iomanip>
using namespace std;
int main() {
    int t; cin >> t;
    for (int cas = 1; cas <= t; cas++) {
        int m, k; cin >> m >> k;
        double ans = 1.0 / ((m+1)*k + 1);
        cout << "Case #" << cas << ": " << fixed << setprecision(8) << ans << endl;
    }
    return 0;
}

B 題：結論題

答案為 max( sum(max(0, a[i]-a[i-1])), sum(max(0, a[i-1]-a[i])) ) + abs(a[0]-a[n-1]) + 1。來源於 TJU 結論，暴力驗證 1 萬組小數據無誤，但證明不明。

#include <iostream>
#define LL long long
using namespace std;
int a[1000005];
int main() {
    int t; scanf("%d", &t);
    for (int cas = 1; cas <= t; cas++) {
        int n; cin >> n;
        LL l = 0, r = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            if (i && a[i] > a[i-1]) l += a[i] - a[i-1];
            if (i && a[i] < a[i-1]) r += a[i-1] - a[i];
        }
        cout << "Case " << cas << " " << max(l, r) + abs(a[0] - a[n-1]) + 1 << endl;
    }
    return 0;
}

G 題：難點——部分錯排與大模數組合數

求 C(n, k) * D(n-k) mod m，其中 D 為錯排數。m 不一定質數，需分解質因子 p_i^e_i，分別求模 p_i^e_i 意義下的組合數與錯排數，再用 CRT 合併。利用階乘去除質因子後的周期性預處理，實現 O(m log n) 計算。代碼較長，核心包括：Pollard-Rho 分解、模質數冪階乘預處理、Lucas 定理推廣、錯排數周期性。

// 核心框架：分解 m -> 對每個 p^e 計算 C(n,k) mod p^e -> CRT 合併 -> 乘錯排數周期結果
// 詳細代碼見原文，涉及 extend_gcd, 快速冪, 階乘質因子計數, 周期性預處理等。

心得

比賽中 A 題理解失誤，G 題過於複雜未解出。事後研究發現 G 題是組合數學與數論的綜合大題，需扎實的模質數冪組合數與 CRT 功底。結論題（B）雖能 AC 但缺乏證明，後續需補強數學嚴謹性。