分治

分治的核心一句话：把大问题拆成形式完全一致的小问题，直到问题足够简单。 听起来简单，但「怎么拆」往往才是难点。

CF 1385D a-Good String

Problem - D - Codeforces

每次折半：左边一半全部改成 c，右边一半递归下去变成 c+1 开头的 good string；再和反过来的方案取 min。原题「折半」表达得很明显，不往分治想确实不应该。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;

int solve(string& s, int l, int r, char c) {
    if (l == r) return (s[l] != c);   // 一个字符：不是 c 就改 1 次，是 c 就不用改
    int mid = (l + r) / 2;

    int cnt1 = 0;                      // 方案1：左半全变 c，右半递归
    for (int i = l; i <= mid; i++) if (s[i] != c) cnt1++;
    cnt1 += solve(s, mid + 1, r, c + 1);

    int cnt2 = 0;                      // 方案2：右半全变 c，左半递归
    for (int i = mid + 1; i <= r; i++) if (s[i] != c) cnt2++;
    cnt2 += solve(s, l, mid, c + 1);

    return min(cnt1, cnt2);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        cin.ignore();
        string s; getline(cin, s);
        cout << solve(s, 0, n - 1, 'a') << endl;
    }
    return 0;
}

P1228 地毯填补（棋盘覆盖）

P1228 地毯填补问题 - 洛谷

这道题即使我知道是分治标签也无从下手，光看样例示意图就足够眼花。后面发现核心在于人为构造出「虚拟的公主格」：

不是去填补空缺，而是主动制造特殊点，让问题始终保持在「一个特殊点」这个可控状态。

中心那块地毯的三个延伸部分，恰好为其他三个区域「创造」了继续递归的条件。没有公主格的区域，也能靠虚拟格无缝套进同一个分治框架。这其实是经典的棋盘覆盖问题（Golomb, 1954）：一个 2^n × 2^n 的棋盘去掉一格，能用 L 型骨牌完美覆盖。

难点：人为构造虚拟公主格这个想法我想不到。分治本身不难，难在「如何让每个子问题的形态保持一致」。

分治求等比数列和

对于 $S(p, c) = 1 + p + p^2 + \dots + p^c$（模 MOD），分治可以在 $O(\log c)$ 内求出：

  • $c$ 为奇数：$S(p,c) = (1 + p^{(c+1)/2}) \cdot S(p, (c-1)/2)$
  • $c$ 为偶数：$S(p,c) = (1 + p^{c/2}) \cdot S(p, c/2 - 1) + p^c$

配合快速幂，就能处理「质因数分解后，每个因子次幂求和再相乘」这一类问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
using ll = long long;
const int MOD = 9901;

ll qpow(ll base, ll exp) {
    ll res = 1; base %= MOD;
    while (exp > 0) {
        if (exp & 1) res = res * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return res;
}

// 分治求 1 + p + p^2 + ... + p^c (mod MOD)
ll sum(ll p, ll c) {
    if (c == 0) return 1;
    if (c & 1) {   // c 为奇数
        return (1 + qpow(p, (c + 1) >> 1)) % MOD * sum(p, (c - 1) >> 1) % MOD;
    } else {       // c 为偶数
        return ((1 + qpow(p, c >> 1)) % MOD * sum(p, (c >> 1) - 1) % MOD + qpow(p, c)) % MOD;
    }
}

总结

分治的关键不是「递归自己调自己」，而是：

  1. 子问题形式完全一致，否则没法递归下去。
  2. 必要时主动构造条件（虚拟公主格）让子问题统一。
  3. 递归树对称时，往往能写出 $O(\log n)$ 甚至 $O(\log^2 n)$ 的漂亮算法。