知识点

例题

递归实现指数型枚举

利用位运算记录当前的状态，也可以用数组（需要恢复现场）

#include <iostream>
using namespace std;
int n;
void dfs(int u, int st) {
    if (u == n) {
        for (int i = 0; i < n; i++) {
            if (st >> i & 1) {
                printf("%d ", i + 1);
            }
        }
        putchar('\n');
        return ;
    }
    dfs(u + 1, st);    //选
    dfs(u + 1, st | (1 << u));    //不选
}
int main() {
    cin >> n;
    dfs(0, 0);
    return 0;
}

递归实现组合型枚举

同样利用位运算记录状态
注意剪枝的两个方向

#include <iostream>
using namespace std;
int n, m;
void dfs(int a, int sum, int st) {
    if (sum == m) {
        for (int i = 0; i < n; i++)
            if (st >> i & 1)
                printf("%d ", i + 1);
        putchar('\n');
        return ;
    }
    // 剪枝
    if (sum + n - a < m) return;
    if (a == n) return;
    dfs(a + 1, sum + 1, st | 1 << a);
    dfs(a + 1, sum, st);
}
int main() {
    cin >> n >> m;
    dfs(0, 0, 0);
    return 0;
}

递归实现排列型枚举

这里不能使用位运算记录结果的原因在于：位运算中的各个位没有顺序，而排列要求顺序
但是可以使用位运算记录某一个数有没有被用过，也可以用数组
当n较大时，位运算不再适用

#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> a;
void dfs(int u, int st) {
    if (u == n) {
        for (int i = 0; i < n; i++)
            printf("%d ", a[i]);
        putchar('\n');
        return ;
    }
    for (int i = 1; i <= n; i++) {
        if (!(st >> i & 1)) {
            a.push_back(i);
            dfs(u + 1, st | 1 << i);
            a.pop_back();
        }
    }
}
int main() {
    cin >> n;
    dfs(0, 0);
    return 0;
}

费解的开关

难点：一旦固定了第一行，最多只有一种满足题意的方案
一行只有5个灯，可以用位运算枚举
注意每次枚举时保存与恢复现场

#include <iostream>
#include <cstring>
using namespace std;
const int N = 6;
char g[N][N];    //注意不要用int
char backup[N][N];
int dx[5] = {0, -1, 0, 1, 0}, dy[5] = {0, 0, 1, 0, -1};
void turn(int x, int y) {
    for (int i = 0; i < 5; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 0 && a < 5 && b >= 0 && b < 5)
            g[a][b] = '0' + ('1' - g[a][b]);
    }
}
int work() {
    int ans = 0x3f3f3f3f;
    for (int i = 0; i < 1 << 5; i++) {
        memcpy(backup, g, sizeof g);    //保存现场
        int cnt = 0;
        for (int j = 0; j < 5; j++) {    //第0行
            if (i >> j & 1) {
                cnt++;
                turn(0, j);
            }
        }
        for (int i = 0; i < 4; i++) {    //1~3行由第0行唯一确定
            for (int j = 0; j < 5; j++) {
                if (g[i][j] == '0') {
                    cnt++;
                    turn(i + 1, j);
                }
            }
        }
        bool flag = true;    //检查最后一行是否全‘1’
        for (int i = 0; i < 5; i++) {
            if (g[4][i] == '0') {
                flag = false;
                break;
            }
        }
        if (flag) ans = min(ans, cnt);
        memcpy(g, backup, sizeof backup);    //恢复现场
    }
    if (ans > 6) return -1;
    return ans;
}
int main() {
    int n;
    cin >> n;
    while (n--) {
        for (int i = 0; i < 5; i++)
            cin >> g[i];
        cout << work() << endl;
    }
    return 0;
}

奇怪的汉诺塔

三塔：先将n-1个挪到B，再将1个挪到C，最后将n-1个挪到C
四塔：先将i个挪到一个塔B（四塔），再将n-i个挪到另一个塔D（三塔），最后将i个塔挪到塔D（四塔）
可以扩展到n盘m塔

#include <iostream>
#include <cstring>
using namespace std;
const int N = 15;
int t3[N], t4[N];
int main() {
    for (int i = 1; i <= 12; i++)    //三塔
        t3[i] = 2 * t3[i - 1] + 1;
    memset(t4, 0x3f, sizeof t4);
    t4[0] = 0;    //初始化！
    for (int i = 1; i <= 12; i++) {    //四塔，动态规划
        for (int j = 0; j < i; j++)
            t4[i] = min(t4[i], t4[j] + t3[i - j] + t4[j]);
        printf("%d\n", t4[i]);
    }
    return 0;
}

约数之和

如果 N = p1^c1 p2^c2 … pk^ck
约数个数： (c1 + 1) (c2 + 1) … (ck + 1)
约数之和： (p1^0 + p1^1 + … + p1^c1) … (pk^0 + pk^1 + … + pk^ck)
关键变成了如何求
mod运算只对加减乘有分配律，所以不能用公式法求等比数列之和
可以用分治

#include <iostream>
using namespace std;
typedef long long LL;
const int MOD = 9901;
int qmi(int a, int k) {    //快速幂
    a %= MOD;
    int res = 1 % MOD;
    while (k) {
        if (k & 1) res = (LL)res * a % MOD;
        a = (LL)a * a % MOD;
        k >>= 1;
    }
    return res;
}
int sum(int a, int k) {    //分治计算1+a+a^2+..+a^k
    if (k == 0) return 1;
    if (k % 2 == 1) return (1 + qmi(a, (k + 1) / 2)) % MOD * sum(a, k / 2) % MOD;
    else return (a % MOD * sum(a, k - 1) % MOD + 1) % MOD;
}
int main() {
    int a, b;
    cin >> a >> b;
    if (!a) {    //特判！！！
        cout << 0;
        return 0;
    }
    int res = 1;
    // 分解质因数
    for (int i = 2; i <= a / i; i++) {
        int cnt = 0;
        while (a % i == 0) {
            cnt++;
            a /= i;
        }
        if (cnt) res = res * sum(i, cnt * b) % MOD;
    }
    if (a > 1) res = res * sum(a, b) % MOD;
    cout << res;
    return 0;
}

分形之城

为了计算方便，从0开始计数！
由于每一等级都是由上一等级复制或旋转四次得到的，因此可以先求出在上一等级的坐标，再进行坐标变换。
具体变换的时候用旋转矩阵+画图模拟的方式，很难直接看明白 视频

#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;
PLL calc(int n, LL a) {    //坐标计算
    if (n == 0) return {0, 0};
    LL len = 1ll << (n - 1), cnt = 1ll << (2 * n - 2);
    PLL pos = calc(n - 1, a % cnt);    //递归
    LL x = pos.first, y = pos.second;
    int t = a / cnt;
    if (t == 0) return {y, x};
    else if (t == 1) return {x, len + y};
    else if (t == 2) return {x + len, len + y};
    return {2 * len - y - 1, len - x - 1};
}
int main() {
    int n;
    cin >> n;
    while (n--) {
        int n;
        LL a, b;
        cin >> n >> a >> b;
        auto coa = calc(n, a - 1), cob = calc(n, b - 1);
        LL dx = coa.first - cob.first, dy = coa.second - cob.second;
        printf("%.0lf\n", sqrt(dx * dx + dy * dy) * 10);    //欧几里得距离
    }
    return 0;
}