BestCoder Round #32 完整題解

A 題：城市排序

每個城市有 a, b 兩屬性，按 a-b 降序排序，相同按 b 升序，再同按 id 升序。

struct City { int a, b, id; };
bool cmp(City x, City y) {
    int d1 = x.a - x.b, d2 = y.a - y.b;
    if (d1 != d2) return d1 > d2;
    if (x.b != y.b) return x.b < y.b;
    return x.id < y.id;
}

B 題：區間和查詢（雜湊優化）

給定序列，問是否存在連續子段和為 K。前綴和 + 雜湊表 O(N)，避免 set 常數過大 TLE。

// 核心：自定義雜湊表，開放定址法
const int MOD = 1000007;
int head[MOD], nxt[MAXN], state[MAXN], hn;

int hash_idx(long long x) { return (x % MOD + MOD) % MOD; }

void insert(long long x) {
    int h = hash_idx(x);
    for (int i = head[h]; ~i; i = nxt[i]) if (state[i] == x) return;
    state[hn] = x; nxt[hn] = head[h]; head[h] = hn++;
}

bool query(long long x) {
    int h = hash_idx(x);
    for (int i = head[h]; ~i; i = nxt[i]) if (state[i] == x) return true;
    return false;
}

// 正反兩遍掃描處理正負號交替
// 完整代碼見原文

C 題：括號序列計數（卡特蘭數變體）

給定部分括號序列，補全長度為 N 的合法序列數。組合數公式：C(q, p+q) - C(q-1, p+q)，模 1e9+7。

ll C(int m, int n) {
    if (m < 0 || m > n) return 0;
    return fact[n] * inv_fact[m] % MOD * inv_fact[n-m] % MOD;
}
// ans = (C(q, p+q) - C(q-1, p+q) + MOD) % MOD;

D 題：整數拆分 DP

將 N 拆分為若干不同正整數之和的方案數模 M。DP[i][j]：用 1~i 拆分 j 的方案數。轉移：DP[i][j] = DP[i-1][j] + DP[i-1][j-i]。最大項數約 √(2N)。

int max_k = (sqrt(8*n + 1) - 1) / 2;
for (int i = 1; i <= n; i++)
    for (int k = 1; k <= min(i, max_k); k++)
        dp[k][i] = (dp[k][i-1] + dp[k-1][i-k]) % m;