您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

Codeforces Round #305 Div.1 A/B/C 解題報告：枚舉、單調棧、狀壓容斥

編輯：關於C++

A. Mike and Frog：枚舉解二元一次方程

兩個線性同餘方程：
h₁(t) = (x₁ t + y₁) mod m, h₂(t) = (x₂ t + y₂) mod m
求最小 t 使 h₁(t)=a₁ 且 h₂(t)=a₂。
解法：先找各自循環節，得等差數列 t₁ = p₁ k + b₁, t₂ = p₂ k + b₂。合併為一個兩元一次方程，枚舉較小循環節內的解（最多 p₂ 次），檢查是否滿足另一方程。複雜度 O(m)。

B. Mike and Feet：單調棧求每個元素作為最小值的最大擴展區間

數組 a[i]，對每個 i 求最大區間 [L,R] 使 a[i] 為區間最小值。
單調棧：維持遞增棧，入棧時彈出 ≥ 當前元素，彈出時其右邊界 = 當前位置-1，左邊界 = 新棧頂位置。
得到 L[i], R[i] 後，a[i] 可作為長度 len ∈ [1, R[i]-L[i]+1] 區間的最小值。用差分/前綴最大值標記各長度的最大最小值。
複雜度 O(n)，優於線段樹 O(n log n)。

C. Mike and Foam：狀壓 + 容斥（同 CF 547C）

動態集合加刪，查詢互質對數。
數值 ≤ 5×10⁵ ⇒ 質因子 ≤ 6 ⇒ 狀壓枚舉子集 (2⁶=64)。
維護 cnt[mask] = 能被該質因子乘積整除的個數。
加入 v：互質對增量 = size - queryNotCoprime(v)，更新 cnt。
移除對稱。
複雜度 O(q·2ᵏ)，極快。

代碼關鍵片段（B題單調棧）


vector st;
for (int i = 0; i < n; i++) {
    while (!st.empty() && a[st.back()] >= a[i]) {
        int idx = st.back(); st.pop_back();
        R[idx] = i - 1;
        L[idx] = st.empty() ? 0 : st.back() + 1;
    }
    st.push_back(i);
}
while (!st.empty()) {
    int idx = st.back(); st.pop_back();
    R[idx] = n - 1;
    L[idx] = st.empty() ? 0 : st.back() + 1;
}