2023 国庆集训 Day 4A 笔记

RyanLi · 2023-10-07 16:41:10 · 个人记录

更佳的阅读体验：2023 国庆集训 Day 4A 笔记，本文同步发表于洛谷博客。

以下内容为个人总结，如有错误或您有不同见解，欢迎指出。

状压 DP

洛谷 P4363 - 一双木棋

只需要将当前局面下所放棋子的轮廓线压入状态即可，DP 初值为 f[整个棋盘] = 0。
状压当前的轮廓线，依据这一步该谁下进行 min / max 搜索。

洛谷 P5369 - 最大前缀和

统计每个子集作为最大前缀和的次数。
如果某个前缀和是最大前缀和，那么这个前缀的所有后缀和都 > 0，后面的所有前缀和都 \le 0。
设 f[S] 为将 S 排列成所有后缀 > 0 的方案数，g[S] 为将 S 排列成所有前缀 \le 0 的方案数。
答案即为 \sum sum[S]f[S]g[U-S]，U 为全集。

洛谷 P5492 - 随机算法

求图上最大独立集。
设 f[S] 为 S 内随机一个排列的正确方案数。
枚举 S 排列的第一个元素 x，加入 x 会导致删除 x 及与其相邻的点集 c_x。
那么如果 max⁡[S]=max⁡[S-c_x ]+1，就令 f[S] 加上 f[S-c_x] 。

int ctz[1 << N];
long long f[1 << N], g[1 << N];
long long c[N];
const long long p = 998244353;

cin >> n >> m;

for (int i = 0; i < m; i++) {
    cin >> x >> y;
    c[x] |= 1 << y;
    c[y] |= 1 << x;
}

for (int i = 0; i < n; i++) {
    ctz[1 << i] = i;
}

for (int S = 1; S < 1 << n; S++) {
    int x = ctz[S & -S];
    g[S] = max(g[S - (1 << x)], g[S - (1 << x) - (c[x] & S)] + 1);
}

f[0] = 1;
for (int S = 1; S < 1 << n; S++) {
    for (int x = 0; x < n; x++) {
        if (~S >> x & 1) <=> if (!(S >> x & 1))
            continue;
        if (g[S - (1 << x) - (c[x] & S)] + 1 < g[S])
            continue;
        f[S] = (f[S] + f[S - (1 << x) - (c[x] & S)]) % p;
    }
}

cout << f[(1 << n) - 1] /n! << endl;

图上拓扑序计数

给定一张 DAG，求其合法拓扑序个数。n \le 20，m \le \frac{n(n - 1)}{2}。

设 f(S) 表示 S 诱导子图的拓扑序个数。
转移时，枚举 S 中拓扑序最靠前的节点 i：f(S) = \sum_{i \in S, ind_i = 0}f(S-\{i\}) 。其中 ind_i=0 表示 i 在 S 中没有入度（而非整个图中）。

// topo count

long long f[1 << N];

bool valid(int x, int s) {
    // s 没有连向 x 的边
}

for (int s = 1; s < 1 << n; ++s) {
    for (int x = 0; x < n; ++x) {
        if (~s >> x & 1) continue;
        if (valid(x, s)) f[s] += f[s - (1 << x)];
    }
}

边子集拓扑序计数

给定一张有向图（不保证是 DAG）。设其边集为 E 。对于 T \subseteq E 定义 f(T) 为保留 T 时整张图的拓扑序数量，求 ∑_{T \subseteq E}f(T)。n \le 20，m \le n(n-1) 。

设 g(S) 表示 S 诱导子图的答案，我们输出 g(U)。
与其统计每个边集 T 的拓扑序方案数，不如统计每种拓扑序能在多少种 T 下合法。
转移时仍然枚举 S 中拓扑序最靠前的节点 i 。
要想让 i 最靠前合法，就需要让 i 在 S 内的 ind=0。换句话说，不能保留从 S-\{i\} 连向 i 的边，而 i 连向 S-\{i\} 的边可以任意保留。
所以 g(S) = \sum_{i \in S} f(S-\{i\}) 2^{cnt_{i,S-\{i\}}}，其中 cnt_{i,S-{i}} 表示 i 连向 S-\{i\} 的边数。

// topo count with edge subset

long long count[N][1 << N];

cin >> n >> m;

for (int i = 0; i < m; ++i) {
    cin >> x >> y;
    for (int s = 1; s < 1 << n; ++s)
        if (s >> y & 1) ++count[x][s];
}

for (int s = 1; s < 1 << n; ++s)
    for (int x = 0; x < n; ++x) {
        if (~s >> x & 1) continue;
        f[s] += f[s - (1 << x)] << count[x][s - (1 << x)];
    }

洛谷 P2831 - 愤怒的小鸟

每个优的抛物线至少经过两只猪。用 \begin{cases} y_1 = ax_1^2 + bx_1 \\ y_2 = ax_2^2 + bx_2 \end{cases} 可解出一组 (a, b)。共有 O(n^2) 组。预处理出每两只猪 (i, j) 形成的抛物线能消灭哪些猪 c[i][j] 。
设 f[S] 为消灭 S 集合猪最少需要多少只小鸟。枚举第一条抛物线，则 f[S] = \min⁡(f[S-c[i][j]]+1)。
固定 i 为 S 中的最小元，则只需枚举 j 即可。
复杂度为 O(n2^n)。

洛谷 P3959 - 宝藏

对于 v 相等的部分分，可以使用贪心求解。
状态中需记录当前层数。设 f[x][i][S] 为 x 的子树编号集合为 S，x 在第 i 层的最小子树代价。
得到转移方程 f[x][i][S] = \min⁡(f[x][i][T]+f[y][i+1][S-T]+dis(x,y) \times i)。
取答案时枚举每个点作为起始点。