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

BZOJ 2241 打地鼠：線性篩 + 二階差分 O(n^3) 驗證構造

編輯：C++ 入門

題目大意

m×n 洞穴矩陣，每洞有若干地鼠。選 r×c 錘子擊打，每次擊打範圍內所有洞必須有地鼠，每洞每次減 1。求最小擊打次數（即最大可行錘子面積）。

關鍵性質：非單調但「積性」

不滿足單調性：1×8 可行 1×4，但 1×3 不可行 → 不能二分
但滿足：若 r×c 可行，則 r×c' (c'|c) 可行；若 r×c 不可行，則 r×c' (c|c') 不可行
即：固定 r 時，可行的 c 集合對因數封閉 → 適合線性篩

驗證算法：貪心 + 二階差分 O(1) 修改

固定錘子 r×c，從左上到右下貪心擊打：位置 (i,j) 擊打次數 = 當前 (i,j) 地鼠數。用二階差分維護區間扣減：

擊打 [i, i+r-1] × [j, j+c-1] 次數 v：
diff[i][j]     -= v
diff[i+r][j]   += v
diff[i][j+c]   += v
diff[i+r][j+c] -= v

最終還原：先列前綴和，再行前綴和（或相反），檢查所有位置是否為 0。

線性篩框架

bool check(int r, int c) { /* 二階差分驗證 */ }

bool sieve_row(int r) {  // 固定 r，篩選 c
    for (int c = 1; c <= n; ++c) if (!vis[c]) {
        vis[c] = check(r, c) ? 0 : 1;
        for (int p : primes) {
            if (c * p > n) break;
            if (vis[c] || vis[p]) vis[c*p] = 1;
            if (c % p == 0) break;
        }
    }
}

完整代碼片段

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int M = 110;
int m, n, a[M][M], diff[M][M], sum;
int primes[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
int vis[2][M], timer;

bool check(int r, int c) {
    if (sum % (r*c)) return false;
    memcpy(diff, a, sizeof a);
    for (int i=1; i<=m; ++i)
        for (int j=1; j<=n; ++j) {
            if (diff[i][j] < 0) return false;
            if (i<=m-r+1 && j<=n-c+1) {
                int v = diff[i][j];
                diff[i][j] -= v;
                diff[i+r][j] += v;
                diff[i][j+c] += v;
                diff[i+r][j+c] -= v;
            }
            if (diff[i][j] > 0) return false;
        }
    return true;
}

// 線性篩主邏輯...
int main() {
    cin >> m >> n;
    for (int i=1; i<=m; ++i)
        for (int j=1; j<=n; ++j)
            scanf("%d", &a[i][j]), sum += a[i][j];
    // 二階差分預處理：a[i][j] = 原始差分
    for (int i=m; i>=1; --i) for (int j=n; j>=1; --j) a[i][j] -= a[i-1][j];
    for (int i=m; i>=1; --i) for (int j=n; j>=1; --j) a[i][j] -= a[i][j-1];
    // 線性篩求解...
    cout << ans << endl;
    return 0;
}