HDU 4768 Flyer：二分查找唯一的「倒楣」學生

問題描述

有 N 個社團（N ≤ 20000）派發傳單，第 i 個社團派發給編號為 `A_i, A_i+C_i, A_i+2*C_i, ... ≤ B_i` 的學生。學生編號範圍 1 到 2^32。已知最多只有一個學生收到奇數張傳單（即「倒楣」學生），求其編號及收到的傳單數；若無則輸出 "DC Qiang is unhappy."。

核心觀察：奇偶性與前綴和

定義 `f(x)` 為編號 ≤ x 的學生收到的傳單總張數。因只有最多一個學生收到奇數張，`f(x)` 的奇偶性在該學生編號處發生翻轉。因此可對學生編號進行二分查找：若 `f(mid)` 為奇數，說明目標在左半邊（含 mid）；否則在右半邊。

計算 f(x) 的方法

每個社團派發的是等差數列。對於給定 `x`，第 i 個社團派發張數為：

if (x < A_i) 0
else min(x, B_i) = k, 張數 = (k - A_i) / C_i + 1

累加所有社團即得 `f(x)`。時間 O(N)，二分共 log(2^31) ≈ 31 輪，總複雜度 O(N log MAX)，完全可行。

二分查找代碼（C++）

#include <cstdio>
using namespace std;
#define ll long long
const int L = 20005;
ll a[L], b[L], c[L];
int n;

ll solve(ll mid) {
    ll sum = 0;
    for (int i = 0; i < n; i++) {
        ll k = min(mid, b[i]);
        if (k >= a[i]) sum += (k - a[i]) / c[i] + 1;
    }
    return sum;
}

int main() {
    while (~scanf("%d", &n)) {
        for (int i = 0; i < n; i++) scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);
        ll l = 0, r = 1LL << 31;
        while (l < r) {
            ll mid = (l + r) / 2;
            if (solve(mid) % 2) r = mid;
            else l = mid + 1;
        }
        if (l == (1LL << 31)) {
            puts("DC Qiang is unhappy.");
        } else {
            // 修正邊界：找到最小的使 f(x) 為奇數的 x
            while (solve(l) % 2 == 0) l--;
            printf("%lld %lld\n", l, solve(l) - solve(l - 1));
        }
    }
    return 0;
}

異或替代方案（較慢但思路簡單）

利用異或性質：若某數出現奇數次，所有編號異或後結果即為該編號。再遍歷統計出現次數。但雙重循環 O(N * 平均張數) 可能超時，二分法更優。

總結

本題巧妙利用「奇偶性單調性」將問題轉化為二分查找。關鍵在於快速計算前綴和 `f(x)`，並正確處理邊界條件。