HDU 4869 Turn the pokers：推理法維護可行區間

HDU 4869 Turn the pokers - 推理法維護上下界

題意同 209354。本文給出另一種推導視角：直接維護正面牌數的上下界 up, down。

推導邏輯

設當前可行正面數區間為 [down, up]，步長 2（奇偶性固定）。新操作翻 x 張牌。考慮兩種極端情況：

• 盡量減少正面數：翻盡可能多的正面牌 → down' = down - x（若 x ≤ down），否則需翻背面牌導致奇偶翻轉。
• 盡量增加正面數：翻盡可能多的背面牌 → up' = up + x（若 up+x ≤ m），否則受 m 限制且奇偶調整。

具體更新公式（見代碼）：分情況討論 x 與 down、up、m-down、m-up 的大小關係，並處理奇偶性。

代碼實現

int up = x[0], down = x[0];
for (i=1; i= down && x <= up) down = ((down&1)^(x&1));
    else if (x < down) down = down - x;
    else down = x - up;
    // 更新 up
    if (x >= down2 && x <= up2) up = m - ((up2&1)^(x&1));
    else if (x < down2) up = m - (down2 - x);
    else up = m - (x - up2);
}
// 最後 Σ C(m, k) , k=down..up step 2

優勢

無需顯式維護奇偶標誌，直接在區間端點上運算，代碼緊湊。