AcWing 1064. 小国王
原题链接
简单
不预处理 match[][] 745ms
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 12, M = 1 << N, K = N * N;
int n, cnt;
ll f[N][M][K];
int cnt2[M]; // cnt2[i]:i 的二进制表示中 1 的个数
bool st[M]; // st[i]:i 的二进制表示中是否有连续的 1
int lowbit(int x) { // 返回 x 的二进制表示中最后 1 位 1
return x & -x;
}
int get(int x) { // 返回 x 的二进制表示中 1 的个数
int res = 0;
while (x) x -= lowbit(x), res++;
return res;
}
bool check(int x) { // 判断 x 的二进制表示中是否有连续的 1
return x & (x >> 1);
}
int main() {
scanf("%d%d", &n, &cnt);
// 预处理
for (int i = 0; i < 1 << n; i++) cnt2[i] = get(i); // M * logx
for (int i = 0; i < 1 << n; i++) st[i] = check(i);
f[0][0][0] = 1;
for (int i = 1; i <= n + 1; i++)
for (int j = 0; j < 1 << n; j++) { // j 表示第 i 行的状态
if (st[j]) continue;
for (int k = 0; k <= cnt; k++) { // k 表示已经用掉的国王的个数
for (int a = 0; a < 1 << n; a++) { // a 表示第 i - 1 行状态
if (st[a]) continue;
if (cnt2[j] + cnt2[a] > k) continue;
if (j & a || j & (a >> 1) || a & (j >> 1)) continue;
f[i][j][k] += f[i - 1][a][k - cnt2[j]];
}
}
}
printf("%lld", f[n + 1][0][cnt]);
return 0;
}
预处理 match[][] 97ms
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 12, M = 1 << N, K = N * N;
int n, cnt;
ll f[N][M][K]; // f[i][j][k]:前 i - 1 行已经摆好 且第 i 行的状态为 j 已经用的国王数为 k 的方案数
int cnt2[M]; // cnt2[i]:i 的二进制表示中 1 的个数
vector<int> state; // 存放所有二进制表示中不含有连续的 1 的数
vector<int> match[M]; // match[i]:存放所有不与 i 冲突的状态
int lowbit(int x) { // 返回 x 的二进制表示中最后 1 位 1
return x & -x;
}
int get(int x) { // 返回 x 的二进制表示中 1 的个数
int res = 0;
while (x) x -= lowbit(x), res++;
return res;
}
bool check(int x) { // 判断 x 的二进制表示中是否有连续的 1
return x & (x >> 1);
}
int main() {
scanf("%d%d", &n, &cnt);
for (int i = 0; i < 1 << n; i++) cnt2[i] = get(i); // 预处理 cnt2[] O(M * logx)
for (int i = 0; i < 1 << n; i++) // 预处理 state[] O(M)
if (!check(i)) state.push_back(i);
for (auto x : state)
for (auto y : state) {
if (x & y || x & (y >> 1) || y & (x >> 1)) continue;
match[x].push_back(y);
}
f[0][0][0] = 1;
for (int i = 1; i <= n + 1; i++)
for (auto j : state) // j 表示第 i 行的状态
for (int k = 0; k <= cnt; k++) // k 表示已经用掉的国王的个数
for (auto a : match[j]) { // a 表示第 i - 1 行状态
if (cnt2[j] + cnt2[a] > k) continue;
f[i][j][k] += f[i - 1][a][k - cnt2[j]];
}
printf("%lld", f[n + 1][0][cnt]);
return 0;
}