算法设计策略杂谈（二）

算法设计中，二进制和状态压缩
是很常见的处理dp问题，搜索问题的关键

二分，序列问题，单调性也常常一起出现

二进制状态压缩

• 取出 $n$ 在二进制下的第 $k$ 位： $(n >>k) \ \& \ 1$
• 取出 $n$ 在二进制下的第 $0 \to k-1$ 位（后 $k$ 位）： $n \ \& \ \left((1<<k)-1\right)$
• 把整数 $n$ 在二进制表示下的第 $k$ 位取反： $n \oplus (1<<k)$
• 对整数 $n$ 在二进制表示下的第 $k$ 位赋值 $1$： $n \mid (1<<k)$
• 对整数 $n$ 在二进制表示下的第 $k$ 位赋值 $0$： $n \ \& \ (\text{~}(1<<k))$

位运算每一位都是相对独立的
一般来说，需要从高位到低位每个 bit 依次检查
决定该位填 0 或者填 1

如果这一位填的是 0，那么对于这个数 $val$，该位无贡献
否则的话，应该要将

val += (1 << bit)

Acwing998

const int maxn = 1e5 + 10;
pair<string, int> a[maxn];
int n, m;

inline int calc(int bit, int cur) {
    _rep(i, 1, n) {
        int x = a[i].second >> bit & 1;
        if (a[i].first == "AND") cur &= x;
        else if (a[i].first == "OR") cur |= x;
        else cur ^= x;
    }
    return cur;
}

void solve() {
    int val = 0, ans = 0;
    for (int bit = 29; bit >= 0; bit--) {
        int res0 = calc(bit, 0);
        int res1 = calc(bit, 1);

        if (val + (1<<bit) <= m && res0 < res1) {
            val += (1<<bit);
            ans += (res1<<bit);
        }
        else ans += res0<<bit;
    }
    printf("%d\n", ans);
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);

    _rep(i, 1, n) {
        char str[10];
        int x;
        scanf("%s%d", str, &x);
        a[i] = make_pair(str, x);
    }

    // then solve
    solve();
}

一个数在二进制下有多少个1

void bitcount(int x) {
    int cnt = 0;
    for (; x; x -= lowbit(x)) cnt++;
    return cnt;
}

状态压缩二维矩阵

Acwing116

typedef pair<int, int> PII;
const int maxn = 5;
char a[maxn][maxn];

int change[maxn][maxn], st = 0;

inline int _hash(int x, int y) { return 4*x + y; }
// decode (i, j) <-- (x/4, x%4)

void prework() {
    st = 0;
    _for(i, 0, 4) _for(j, 0, 4) {
            if (a[i][j] == '+') st += (1<<_hash(i, j));
    }

    // then prework change
    memset(change, 0, sizeof change);
    _for (i, 0, 4) _for(j, 0, 4) {
        _for(k, 0, 4) {
            change[i][j] += (1<<_hash(i, k));
            change[i][j] += (1<<_hash(k, j));
        }
        change[i][j] -= (1<<_hash(i, j));
    }
}

void solve() {
    vector<PII> ans;

    _for(val, 0, (1<<16)) {
        // enumerate solution val
        vector<PII> path;
        int cur = st;
        _for(i, 0, 16) if ((val>>i) & 1) {
            // i is counted
            int x = i / 4, y = i % 4;
            path.push_back(make_pair(x, y));
            cur ^= change[x][y];

            if (cur == 0 && (ans.empty() || ans.size() > path.size())) ans = path;
        }
    }

    printf("%d\n", (int)ans.size());
    for (auto x : ans) printf("%d %d\n", x.first + 1, x.second + 1);
}

void init() {
    memset(change, 0, sizeof change);
    st = 0;
}

int main() {
    freopen("input.txt", "r", stdin);
    init();

    // get data
    _for(i, 0, 4) scanf("%s", a[i]);

    // prework
    prework();

    // then solve
    solve();
}

状态依赖与递推

Acwing95

const int inf = 0x3f3f3f3f;
const int maxn = 10;
char _a[maxn][maxn];
int a[maxn][maxn], b[maxn][maxn];
int n, ans = inf;

void init() {
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    ans = inf;
}

void handle(int x, int y) {
    b[x][y] ^= 1;
    b[x-1][y] ^= 1;
    b[x][y-1] ^= 1;
    b[x+1][y] ^= 1;
    b[x][y+1] ^= 1;
}

bool ok() {
    _rep(i, 1, 5) _rep(j, 1, 5) if (b[i][j] == 0) return false;
    return true;
}

void solve() {
    for (int sta = 0; sta <= (1<<5); sta++) {
        int cnt = 0;
        memcpy(b, a, sizeof(a));

        for (int i = 1; i <= 5; i++) if (sta >> (i-1) & 1) {
            cnt++;
            handle(1, i);
        }

        _rep(i, 1, 4) _rep(j, 1, 5) {
            if (b[i][j] == 0) {
                cnt++;
                handle(i+1, j);
            }
        }

        if (ok()) chmin(ans, cnt);
    }
    if (ans > 6) ans = -1;
}

void dbg() {
    _rep(i, 1, 5) {
        _rep(j, 1, 5) printf("%d", a[i][j]);
        printf("\n");
    }
    printf("\n");
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d", &n);

    _rep(kase, 1, n) {
        init();
        _rep(i, 1, 5) scanf("%s", _a[i]+1);
        _rep(i, 1, 5) _rep(j, 1, 5) a[i][j] = _a[i][j] - '0';
        // dbg();

        // then solve
        solve();
        printf("%d\n", ans);
    }
}

计算几何问题中的精度处理

在解决计算几何问题的时候，常常涉及到四舍五入相关的输出
在处理此类问题， 特别是比如距离 dist 结果时
可以用以下代码

ll dx = ans1.first - ans2.first, dy = ans1.second - ans2.second;
double dist = (double)sqrt(dx*dx + dy*dy);
printf("%.0lf\n", dist);

序列问题

无长度限制的最大子段和

To the max

const int maxn = 100 + 10;
const int inf = 0x3f3f3f3f;
int n, a[maxn][maxn], S[maxn][maxn];
bool allnegative = true;
int res = -inf;

void prework() {
    _rep(i, 1, n) {
        _rep(k, 1, n) S[k][i] = S[k-1][i] + a[k][i];
    }
}

void solve() {
    if (allnegative) {
        _rep(i, 1, n) _rep(j, 1, n) chmax(res, a[i][j]);
        return;
    }

    _rep(l, 1, n) _rep(r, l, n) {
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += S[r][i] - S[l-1][i];

            if (sum < 0) sum = 0;
            else chmax(res, sum);
        }
    }
}

void init() {
    memset(S, 0, sizeof S);
    allnegative = true;
    res = -inf;
}

int main() {
    freopen("input.txt", "r", stdin);
    cin >> n;
    init();
    _rep(i, 1, n) _rep(j, 1, n) {
        scanf("%d", &a[i][j]);
        if (a[i][j] >= 0) allnegative = false;
    }

    // prework and solve
    prework();
    solve();
    printf("%d\n", res);
}