BZOJ 1271 秦騰與教學評估：二分答案 + 奇偶性判定

題目大意

有 N 個評估小組，每組成員位置構成等差數列：S, S+D, S+2D, ..., S+KD ≤ E。
若某位置有奇數個成員，秦騰可突圍。已知全路徑上最多只有一個這樣的位置。求該位置及人數，或輸出 "Poor QIN Teng:("。

約束：N ≤ 200000，坐標 ≤ 2^31-1，總人數 ≤ 10^8。

關鍵觀察

• 函數 f(x) = [0, x] 區間內總人數 是單調遞增的。
• 若 f(x) 為奇數，則唯一的奇數點必在 [0, x] 內；若為偶數，則在 (x, MAX]。
• 利用二分查找定位最小的使 f(x) 為奇數的 x，即為目標位置。

算法流程

1. 讀入所有小組 (S_i, E_i, D_i)，記錄最大坐標 MAX = max(E_i)。
2. 二分 l=0, r=MAX：
   • mid = (l+r)/2
   • 計算 cnt = Σ max(0, (min(E_i,mid)-S_i)/D_i + 1) （S_i ≤ mid 才計數）
   • 若 cnt % 2 == 1 → r = mid；否則 l = mid+1。
3. 得到候選位置 ans = l。
4. 驗證：精確計算 ans 處成員數 c = Σ [S_i ≤ ans ≤ E_i && (ans-S_i)%D_i==0]。
   • 若 c 為奇數 → 輸出 ans c。
   • 否則 → 輸出 "Poor QIN Teng:("。

C++ 代碼

#include 
using namespace std;
typedef long long LL;
const LL INF = 2147483647;
const int MAXN = 200005;

LL S[MAXN], E[MAXN], D[MAXN];
int T, N;

bool check(LL x) {
    LL cnt = 0;
    for (int i=1; i<=N; ++i) if (S[i] <= x) {
        if (E[i] <= x) cnt += (E[i] - S[i]) / D[i] + 1;
        else cnt += (x - S[i]) / D[i] + 1;
    }
    return cnt & 1;
}

LL binary_search(LL l, LL r) {
    if (l == r) return l;
    LL mid = (l + r) >> 1;
    return check(mid) ? binary_search(l, mid) : binary_search(mid+1, r);
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &N);
        LL MAX = 0;
        for (int i=1; i<=N; ++i) {
            scanf("%lld%lld%lld", &S[i], &E[i], &D[i]);
            if (E[i] > MAX) MAX = E[i];
        }
        LL ans = binary_search(0, MAX);
        LL cnt = 0;
        for (int i=1; i<=N; ++i)
            if (S[i] <= ans && ans <= E[i] && (ans - S[i]) % D[i] == 0) ++cnt;
        if (cnt & 1) printf("%lld %lld\n", ans, cnt);
        else puts("Poor QIN Teng:(");
    }
    return 0;
}

複雜度

• 每次 check O(N)，二分 O(log MAX) ≈ 31 次。
• 總體 O(N log MAX)，N=2e5 極快。
• 需用 long long 防溢出。

總結

「最多一個奇數點」是關鍵提示，將問題轉化為單調謂詞上的二分。類似思想適用於「找唯一滿足條件的位置」、「中位數查找」等問題。