BestCoder Round #11 題解彙總：幾何、構造、滑動窗口

比賽概覽

BestCoder Round #11 包含三道題目，涵蓋幾何判斷、數字構造、滑動窗口計數，難度梯度合理，考察基礎算法靈活運用。

1001: 中點判斷

問題：給定矩形長寬 n, m 和點 (x, y)，判斷該點是否為矩形中心。

解法：中心點坐標為 (n/2, m/2)。判斷 2*x == n 且 2*y == m 即可。注意整數除法，直接用乘法避免精度問題。

if (2*x == n && 2*y == m) cout << "Yes" << endl;
else cout << "No" << endl;

1002: 奇數構造

問題：用 n 個數字 (0-9) 組成無前導零、末位為奇數的最大數，不能構造輸出 -1。

解法：

• 至少有一個奇數作為末位
• 除末位外至少有一個非零數字作為首位（n>1 時）
• 構造策略：選最小奇數作末位，其餘數字降序排列

sort(num+1, num+n+1, greater());
swap(num[pos_min_odd], num[n]); // 最小奇數放末尾
// 輸出 num[1]...num[n]

1003: 子串計數（滑動窗口）

問題：給定字符串 s 和整數 k，統計有多少子串滿足「每個字符出現次數 ≤ k」。

解法：雙指針滑動窗口維護以右端點結尾的最長合法子串。右指針擴展，當某字符計數超過 k 時，左指針收縮直到合法。每次右移時，新增的合法子串數 = 窗口長度。

int start = 0; long long ans = 0;
for (int i = 0; i < len; ++i) {
    cnt[s[i]]++;
    while (cnt[s[i]] > k) cnt[s[start++]]--;
    ans += i - start + 1;
}

時間複雜度 O(n)，空間 O(字符集大小)。關鍵洞察：以 i 結尾的合法子串恰好是 [start, i] 區間的所有後綴。

比賽心得

• 構造類題目需全面考慮邊界條件（如 n=1、全零、無奇數等）
• 滑動窗口「以右端點結尾」視角常比「以左端點開始」更易處理計數問題
• 幾何題優先用整數運算避免浮點誤差