状压一类杂题
P1896 [SCOI2005] 互不侵犯
先预处理出一行的所有可能状态 \(S\)，应当满足 \(S \& (S ≫ 1) = 0\)，因为不能有相邻的国王。用 \(f(i, S, j)\) 表示考虑了前 \(i\) 行，第 \(i\) 行的状态是 \(S\)，当前已经放了 $$ 个国王的方案数。转移直接枚举第 \(i − 1\) 行的状态 \(T\)，检查 \(S \& T，S \& (T ≫ 1)，(S ≫ 1) \& T\) 是否都为 \(0\) 即可。
int f[N][N * N][M], ans;
int cnt, p[M], bit[M], n, K;
signed main()
{
cin >> n >> K;
for (rint i = 0; i < (1 << n); i++)
{
if (i & (i >> 1)) continue;
p[++cnt] = i;
// 辅助检查 S & T，S & (T >> 1)，(S >> 1) & T 是否都为 0
bit[cnt] = __builtin_popcount(i);
}
f[0][0][1] = 1;
for (rint i = 1; i <= n; i++)
for (rint j = 1; j <= cnt; j++)
for (rint k = 1; k <= cnt; k++)
if (!(p[j] & p[k] || (p[j] >> 1) & p[k] || p[j] & (p[k] >> 1)))
for (rint l = bit[j] + bit[k]; l <= K; l++)
f[i][l][j] += f[i - 1][l - bit[j]][k];
for (rint i = 1; i <= cnt; i++) ans += f[n][K][i];
cout << ans << endl;
return 0;
}
P5933 [清华集训2012] 串珠子
\(f(S)\) 表示点集 \(S\) 的连通图方案数，不能转移。正难则反，考虑反向计算，设 \(g(S)\) 表示不连通图方案数，\(h(S)\) 表示总方案数，显然有 \(f(S) + g(S) = h(S)\)，\(h(S)=\prod_{u,v∈S}(c_{u,v}+1)\)
对于 \(g(S)\)，取一个 \(p ∈ S\)，这个是什么无所谓，可以用 \(lowbit\) ，或者 \(highbit\)，\(randbit\) 也行。为了统一使用了 \(lowbit\)。枚举 \(p\) 所在的连通块 \(p ∈ T ⊊ S\)，有
\[g(S)=\sum_{T}f(T)h(S-T) \]按照 \(S\) 从小到的的顺序转移先计算 \(g\) 再计算 \(f\)
复杂度 \(O(3^n+2^nn^2)\)
int n, c[M][M];
int f[N], g[N], h[N];
signed main()
{
cin >> n;
for (rint i = 0; i < n; i++)
for (rint j = 0; j < n; j++)
cin >> c[i][j];
for (rint S = 0; S < (1 << n); S++)
{
h[S] = 1;
for (rint j = 0; j < n; j++)
if (S >> j & 1)
for (rint k = j + 1; k < n; k++)
if (S >> k & 1)
h[S] = h[S] * (c[j][k] + 1) % mod;
// 任意选取, lowbit 即可, P 直接表示为 (S & -S)
int T = S ^ (S & -S);
for (rint j = T; j; j = (j - 1) & T)
g[S] = (g[S] + f[S ^ j] * h[j]) % mod;
f[S] = (h[S] - g[S] + mod) % mod;
}
cout << f[(1 << n) - 1] << endl;
return 0;
}
P7519 [省选联考 2021 A/B 卷] 滚榜
\(b\) 的分配是贪心的，每次给出最小的 \(b\)，只要 \(∑b ≤ m\) 就是合法的方案。
当前选手想当 rank 1 只要比上一名选手高即可，这是因为上一名选手是当前的 rank 1。
考虑把 \(∑b\) 类似背包设计进状态，贡献拆分计算
\(b\) 的分配方式如下，如果 \(a_i ≥ a_i−1\)，则 \(b_i = b_{i−1}\)，如果 \(a_i < a_i−1\)，则 \(b_i = b_i−1 + a_i − a_{i−1}\)。综合即为
\[b_i = b_i−1 + max(0, a_i − a_{i−1}) \]那么有
\[∑b =∑max(0, ai − a_{i−1})(n − i + 1) \]\(f(S, i, j)\) 表示，当前使用过的集合是 \(S\)，最后一个选的是 \(i\)，以及当前对 \(∑b\) 的贡献是 \(j\)。转移的时候枚举接下来选哪一个人，计算贡献。
复杂度 \(O(2^n n^2m)\)
int n, m;
int a[N];
int f[1 << N][N][M], ans;
int id, dl;
int lb(int x)
{
return __lg(x & (-x));
// 带个 log 可以投影到二进制然后参与状压
}
signed main()
{
cin >> n >> m;
for (rint i = 0; i < n; i++) cin >> a[i];
for (rint i = 1; i < n; i++) if (a[i] > a[id]) id = i;
for (rint i = 0; i < n; i++)
{
dl = max(0ll, a[id] - a[i] + bool(id < i));
if (n * dl <= m)
f[1 << i][i][n * dl] = 1;
}
for (rint S = 1; S <= (1 << n) - 1; S++)
{
int cnt = __builtin_popcount(S);
for (rint _s = S, i = lb(_s); _s; _s &= _s - 1, i = lb(_s))
for (rint k = 0; k <= m; k++)
if (f[S][i][k])
for (rint T = S ^ ((1 << n) - 1), j = lb(T); T; T &= T - 1, j = lb(T))
{
dl = max(0ll, a[i] - a[j] + bool(i < j));
if (k + dl * (n - cnt) <= m)
f[S | (1 << j)][j][k + dl * (n - cnt)] += f[S][i][k];
}
}
for (rint i = 0; i < n; i++)
for (rint j = 0; j <= m; j++)
ans += f[(1 << n) - 1][i][j];
cout << ans << endl;
return 0;
}
P6622 [省选联考 2020 A/B 卷] 信号传递
这个题 zyk 上课并没有讲但是推荐了，但这个题厉害的地方在于，它结合了以上两个题的思想并需要进行空间卡常。需要用到串珠子中辅助数组的思想以及滚榜中贡献拆分的思想。
首先是贡献拆分，对于 \(u\) 到 \(v\)，其贡献为 \(v ≥ u ? v - u : k(v+u)\)。贡献分到各个点上累加。最终坐标为 \(u\) 的点，序列中每有一条 \(u\) 到 \(v\) 的边，若 \(u≤v\) 则贡献 \(k\)，否则贡献 \(-1\)，反之亦然。最终总贡献等于每个点的贡献分别乘其坐标再求和。
仍然设 \(f(S)\) 表示答案，不好更新，设 \(g(i,S)\) 表示 \(i\) 前为 \(S\) 时的答案，那么更新时直接加就可以。
按照 \(S\) 从小到的的顺序转移，中间其他转移方程式简单的，先计算 \(g\) 再计算 \(f\)，复杂度 \(O(m2^m)\)，时间允许通过，然而空间不允许。
空间卡常方面，可以折半，直接暴力折半可做但是并不好写。对于 \(i∈S\) 的 \(g\) 没有计算的必要，对于这些不存储空间就够用了。注意不能开 \(long\) \(long\)，用 \(int\) 卡满空间。
int n, m, k;
int x = -1, y;
int f[N], g[M][M], h[M][N >> 1];
int lb(int x)
{
return x & (-x);
}
signed main()
{
cin >> n >> m >> k;
while (n--)
{
cin >> y;
y--;
if (~x) g[x][y]++;
x = y;
}
for (rint i = 0; i < m; i++)
{
for (rint j = 0; j < m; j++)
if (i ^ j)
h[i][0] += g[j][i] * k - g[i][j];
for (rint j = 1; j < (1 << m) >> 1; j++)
{
int t = __lg(lb(j)) + (__lg(lb(j)) >= i);
h[i][j] = h[i][j ^ lb(j)] + g[i][t] * (1 + k) + g[t][i] * (1 - k);
}
}
for (rint i = 1; i < (1 << m); i++)
{
f[i] = inf;
for (rint j = i, k; k = lb(j); j ^= k)
f[i] = min(f[i], f[i ^ k] + h[__lg(k)][((i ^ k) & (k - 1)) | (i ^ k) >> (__lg(k) + 1) << __lg(k)] * __builtin_popcount(i));
}
cout << f[(1 << m) - 1] << endl;
}
一些常用
for (rint s = 0; s < (1 << n); s++)
{
for (rint i = 0; i < n; i++)
if (s >> i & 1) // 判断第 i 位是不是 1
for (rint t = 0; t < (1 << n); t++)
if (t & s == t) // 判断 t 是 s 的子集 O(4^n)
if (!((s << 1) & s)) //s 中没有相邻的比特位为 1
for (rint t = s; t >= 0; t = (t - 1) & s) //可以不重不漏的枚举每一个子集
// O(3^n)
(x >> (i - 1)) & 1 // 取出第 i 位
x ^= (1 << (i - 1)) // 将 x 第 i 位取反
x |= (1 << (i - 1)) // 将 x 第 i 位变成 1
x &= (~(1 << (i - 1))) // 将 x 第 i 位变成 0
x = x & (x - 1) // 将 x 最靠右的 1 去掉
x & (-x) //取 出 x 最靠右的 1
S ^ T // S - T
__builtin_popcount(s) // 求二进制下 s 中 1 的个数
}