嗯，所有需要的代码（包括全部7个例题及注释中的实现）都有，还附赠了两三个练习。希望能对需要的人有帮助（只要不是淹没到百度里根本搜不出来就好了）

---

前言

先确认我们说的是同一个东西 论文开头为 网上应该都下得到吧，就不放链接了 有论文的话我就不赘述原文了，大概说明原题是什么，再放个人代码 其实代码很多是%了各位dalao码出来的，所以代码中我也会说一些我发现的好的地方 csdn的代码片有点反人类啊，实在不行的话，麻烦各位自行用编辑器自动缩进了 若能在oj上找到的我也尽量直接贴上oj题号 还会有很少的练习题

某日update 【例7】完成！对于进制的理解可以更深一些

---

前言正文 引例 题目描述代码 例1 题目描述代码 棋盘问题 POJ1321练习 题目描述代码 例2伪 题目描述代码 关于注释中的递推程序题目实现 例3 题目描述代码 例4POJ1185 题目描述代码 骑士练习 题目描述 骑士 knightpasccpp 输入数据输出数据样例 输入knightin输出knightout输入knightin输出knightout 数据范围 分值 与时间限制 代码 例5 题目描述代码 例6 题目描述代码 例7COGS 1520 题目描述代码 后记

---

正文

【引例】

题目描述

在 n*n(n≤20)的方格棋盘上放置 n 个车(可以攻击所在行、列)，求使它们不能互相攻击的方案总数。

代码

#include <cstdio> #include <cstring> const int maxn = 10; int f[1<<maxn + 10] = {0}, lim; inline int lowbit(int x){return -x&x;} int main (){ int n; scanf ("%d", &n); f[0] = 1, lim = (1<<n); for (int s = 1, lk; s < lim; ++s){ for (int k = s; k > 0; k -= lk){ f[s] += f[s ^ (lk = lowbit(k))]; //这种打法应该很有效率啦 } } printf ("%d\n", f[lim - 1]); return 0; }

---

【例1]

题目描述

在 n*n(n≤20)的方格棋盘上放置 n 个车，某些格子不能放，求使它们不能互相攻击的方案总数。

代码

#include <cstdio> #include <cstring> const int maxn = 10; int f[1<<maxn + 10], out[maxn], lim; inline int lowbit(int x){return -x&x;} int main (){ freopen ("1.in", "r", stdin); int n, m; scanf ("%d%d", &n, &m); for (int i = 1, x, y; i <= m; ++i){ scanf ("%d%d", &x, &y); out[x] |= 1 << --y; //这行在网上看到的有些代码打得奇奇怪怪的... } f[0] = 1, lim = (1 << n) - 1; for (int s = 1, st, h, lk; s < lim; ++s){ st = s, h = 0; while (st) st -= lowbit(st), ++h; for (int j = s ^ out[h]; j > 0; j -= lowbit(j)){ f[s] += f[s ^ (lk = lowbit(j))]; } } printf ("%d\n", f[lim - 1]); return 0; }

---

poj1321好像是例1的一点点拓展，这个练习是临时加的

棋盘问题 POJ1321(练习)

题目描述

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。 具体输入输出什么的自己去看就好了，中文题

代码

#include <cstdio> #include <cstring> const int maxn = 10; char tmps[maxn]; int lim, f[maxn][1<<maxn], c[1<<maxn], rs[75], rst, out[maxn]; inline int Cal(int x){ int ans = 0; while (x){if(x & 1) ++ans; x >>= 1;} return ans; } inline int lowbit(int x){return -x & x;} int dp(int rti, int rts){ if (f[rti][rts]) return f[rti][rts]; if (!rti) return 0; for (int s = out[rti] ^ rts; s > 0; s -= lowbit(s)) f[rti][rts] += dp(rti - 1, lowbit(s) ^ rts); return f[rti][rts] += dp(rti - 1, rts); } int main (){ freopen ("p1321.in", "r", stdin); for (int s = 0; s < (1 << maxn); ++s) c[s] = Cal(s); int n, k, ans; while (scanf ("%d%d", &n, &k), n > 0){ rst = ans = 0; memset(out, 0, sizeof out), memset(f, 0, sizeof f); for (int i = 1; i <= n; ++i){ scanf ("%s", tmps); for (int j = 0; j < n; ++j) if (tmps[j] == '.') out[i] |= 1 << j; }lim = 1 << n; for (int s = 0; s < lim; ++s) if (c[s] == k) rs[rst++] = s; f[0][0] = 1; for (int i = 0; i < rst; ++i) ans += dp(n, rs[i]); printf ("%d\n", ans); } return 0; }

---

【例2】(伪)

题目描述

为什么说是伪呢，因为我强行改题目，就求方案数就好吧 给出一个 n*m 的棋盘(n、m≤80,n*m≤80)，要在棋盘上放 k(k≤20)个棋子，使得任意两个棋子不相邻。求方案数

代码

关于注释中的递推程序

#include <cstdio> const int maxn = 1010; int g[maxn]; int main (){ int m, d; scanf ("%d%d", &m, &d); for (int i = 1; i <= d; ++i) g[i] = 1; for (int j = d + 1; j <= m + d + 1; ++j) g[j] = g[j - d - 1] + g[j - 1]; printf ("%d", g[m + d + 1]); return 0; }

题目实现

#include <cstdio> typedef long long ll; const int maxnum = 150, maxn = 10, maxk = 25; int num = 0, s[maxnum], c[maxnum]; ll f[maxn][maxnum][maxk]; template <typename T> inline void Swap(T &a, T &b){int t = a; a = b, b = t;} inline int cal(int x){ int ans = 0; while (x){if (x & 1) ++ans; x>>=1;} return ans; } int main (){ freopen ("2.in", "r", stdin); freopen ("2.out", "w", stdout); int n, m, k; scanf ("%d%d%d", &n, &m, &k); if (m > n)Swap(n, m); int collim = 1 << m; for (int i = 0; i < collim; ++i) if (!(i & (i << 1))) s[++num] = i, c[num] = cal(i); //, f[1][num][c[num] = cal(i)] = 1; f[0][1][0] = 1; for (int i = 1; i <= n; ++i) for (int j = 1; j <= num; ++j){ for (int pn = c[j]; pn <= k; ++pn) for (int p = 1; p <= num; ++p){ if (!(s[j] & s[p])) f[i][j][pn] += f[i - 1][p][pn - c[j]]; } } ll ans = 0; for (int i = 1; i <= num; ++i) ans += f[n][i][k]; printf ("%lld", ans); return 0; }

---

【例3】

题目描述

在 n*n(n≤10)的棋盘上放 k 个国王(可攻击相邻的 8 个格子)，求使它们无法互相攻击的方案数。

代码

#include <cstdio> typedef long long ll; const int maxn = 13, maxnum = 150, maxk = 25; ll f[maxn][maxnum][maxk]; int s[maxnum], c[maxnum], num = 0; inline int cal(int x){ int ans = 0; while (x){if (x & 1) ++ans; x >>= 1;} return ans; } int main (){ freopen ("3.in", "r", stdin); //freopen ("3.out", "w", stdout); int n, k; scanf ("%d%d", &n, &k); int lim = 1 << n; for (int i = 0; i < lim; ++i) if (!(i & (i << 1))) s[++num] = i, c[num] = cal(i); f[0][1][0] = 1; for (int i = 1; i <= n; ++i) for (int j = 1; j <= num; ++j) for (int pn = c[j]; pn <= k; ++pn) for (int p = 1; p <= num; ++p) if (!(s[j] & s[p]) && !((s[j] << 1) & s[p]) && !((s[j] >> 1) & s[p])) f[i][j][pn] += f[i - 1][p][pn - c[j]]; ll ans = 0; for (int i = 1; i <= num; ++i) ans += f[n][i][k]; printf ("%lld", ans); return 0; }

---

【例4】(POJ1185)

题目描述

给出一个 n*m(n≤100,m≤10)的棋盘，一些格子不能放置棋子。求最多能在棋盘上放置多少个棋子 ， 使得每一行每一列的任两个棋子间至少有两个空格

代码

#include <cstdio> const int maxn = 105, maxm = 12, maxs = 65; char tmps[maxm]; int out[maxn], f[maxn][maxs][maxs], s[maxs], c[maxs], num = 0, lim; inline int Cal(int x){ int ans = 0; while (x){if (x & 1) ++ans; x >>= 1;} return ans; } int main (){ int n, m; scanf ("%d%d", &n, &m); for (int i = 1; i <= n; ++i){ scanf ("%s", tmps); for (int j = 0; j < m; ++j) if (tmps[j] == 'H') out[i] |= 1 << j; } lim = 1 << m; for (int i = 0, ci; i < lim; ++i) if (!(i & (i << 2)) && !(i & (i << 1))) s[++num] = i, c[num] = Cal(i); for (int i = 1; i <= num; ++i) if (!(s[i] & out[1])){ f[1][i][1] = c[i]; for (int j = 1; j <= num; ++j) if (!(s[j] & s[i]) && !(s[j] & out[2])) f[2][j][i] = c[i] + c[j]; } for (int i = 3, mx; i <= n; ++i) for (int j = 1; j <= num; ++j) if (!(s[j] & out[i])) for (int k = 1; k <= num; ++k) if (!(s[j] & s[k]) && !(s[k] & out[i - 1])){ mx = 0; for (int l = 1; l <= num; ++l) if (!(s[l] & out[i - 2])) if (!(s[j] & s[l]) && !(s[k] & s[l]) && f[i - 1][k][l] > mx) mx = f[i - 1][k][l]; f[i][j][k] = mx + c[j]; } int ans = 0; for (int j = 1; j <= num; ++j) if (!(s[j] & out[n])) for (int k = 1; k <= num; ++k) if (!(s[j] & s[k]) && !(s[k] & out[n - 1]) && f[n][j][k] > ans) ans = f[n][j][k]; printf ("%d", ans); return 0; }

---

【骑士】(练习)

强行夹在中间233

题目描述

骑士 （knight.pas/c/cpp ）

国际象棋中骑士的移动规则和中国象棋中的马是类似的，它先沿着一个方向移动两格， 再沿着与刚才移动方向垂直的方向移动一格。路径上的棋子并不会影响骑士的移动，但是如 果一个骑士走到了一个放有棋子的格子，它就会攻击那个棋子。现在有一个 n*n 的棋盘，有 k 个骑士需要被摆到棋盘上去。那么使所有骑士互不攻击的摆放方式一共有多少种呢？

输入数据

一行:两个整数，n，k

输出数据

一行:一个整数，为摆放的方式数

样例

输入:knight.in

3 2

输出:knight.out

28

输入:knight.in

4 4

输出:knight.out

412

数据范围 ，分值 与时间限制

第一次用这个表格

数据编号数据范围时间限制单个测试点分值总分值1~151≤n≤41.0s34516~205≤n≤61.0s52521~257≤n≤85.0s630

对于所有的数据，0<=k<=n 保证答案不超过 double 的精度。

代码

#include <cstdio> #include <cstring> typedef long long ll; const int maxn = 9, maxm = 260;//maxm is cal_ed ll f[2][1<<maxn][1<<maxn][maxn]; int cal[1<<maxn], nx[1<<maxn][maxm], num[1<<maxn]; inline int Cal(int x){ if (cal[x]) return cal[x]; int tx = x, ans; for (ans = 0; x; ){ if (x & 1) ++ans; x >>= 1;} return cal[tx] = ans; } int main (){ freopen ("knight.in", "r", stdin); freopen ("knight.out", "w", stdout); int n, pk, lim; scanf ("%d%d", &n, &pk); if (n == 1){printf ("%d", pk <= 1 ? 1 : 0); return 0;} lim = 1 << n; for (int i = 0; i < lim; ++i){ f[0][i][0][Cal(i)] = 1; for (int j = 0; j < lim; ++j) if (!((i << 2) & j) && !((i >> 2) & j)){ f[1][j][i][Cal(j) + Cal(i)] = 1; nx[i][++num[i]] = j; } } for (int i = 3, k, l, rt; i <= n; ++i){ rt = (i ^ 1) & 1; memset(f[rt], 0, sizeof f[rt]); for (int j = 0; j < lim; ++j) for (int pn = cal[j]; pn <= pk; ++pn) for (int nk = 1; nk <= num[j]; ++nk){ k = nx[j][nk]; for (int nl = 1; nl <= num[k]; ++nl){ l = nx[k][nl]; if (!((l << 1) & j) && !((l >> 1) & j)){ f[rt][j][k][pn] += f[rt ^ 1][k][l][pn - cal[j]]; } } } memset(f[rt^1], 0, sizeof f[rt^1]); } ll ans = 0; for (int j = 0, k; j < lim; ++j) for (int nk = 1; nk <= num[j]; ++nk){ k = nx[j][nk]; ans += f[(n ^ 1) & 1][j][k][pk]; } printf ("%lld", ans); return 0; }

---

【例5】

题目描述

给出 n*m (1≤n、m≤11)的方格棋盘，用 1*2 的长方形骨牌不重叠地覆盖这个棋盘，求覆盖满的方案 数。

代码

其实并没有完全按论文里打，是参考dalaoKB代码，更为清晰明了

#include <cstdio> typedef long long ll; const int maxn = 12; ll f[maxn][1 << 11]; int n, m; template <typename T> void Swap (T &a, T &b){T t = a; a = b, b = t;} void dp (int li, int co, int rt, int la){//line, column, root, last if (co > m) return; if (co == m){ f[li][rt] += f[li - 1][la]; return ;} dp (li, co + 1, rt << 1, (la << 1) | 1); dp (li, co + 1, (rt << 1) | 1, la << 1); dp (li, co + 2, (rt << 2) | 3, (la << 2) | 3); } int main (){ freopen ("5.in", "r", stdin); freopen ("5.out", "w", stdout); int lim; scanf ("%d%d", &n, &m); if (m > n) Swap(n, m); lim = 1 << m; f[0][lim - 1] = 1; for (int i = 1; i <= n; ++i) dp(i, 0, 0, 0); printf ("%lld", f[n][lim - 1]); return 0; }

---

【例6】

题目描述

给出 n*m (1≤n、m≤9)的方格棋盘，用 1*2 的矩形的骨牌和 L 形的(2*2 的去掉一个角)骨牌不重叠地 覆盖，求覆盖满的方案数。

代码

%%%KB%%%

#include <cstdio> typedef long long ll; const int maxn = 10; ll f[maxn][1 << 9]; int n, m; template <typename T> void Swap (T &a, T &b){T t = a; a = b, b = t;} void dp (int li, int co, int rt, bool fr, int la, bool fl){ //line, column, root, fluence of root, last, fluence of last if (co == m){ if (!fr && !fl) f[li][rt] += f[li - 1][la]; return ; } dp (li, co + 1, rt << 1 | fr, 0, la << 1 | (fl ^ 1), 0); //no putting if (!fr && !fl){ dp (li, co + 1, rt << 1 | 1, 0, la << 1, 0); //10/10 dp (li, co + 1, rt << 1 | 1, 1, la << 1, 0); //10/11 dp (li, co + 1, rt << 1 | 1, 0, la << 1, 1); //11/10 } if (!fr){ dp (li, co + 1, rt << 1 | 1, 1, la << 1 | (fl ^ 1), 0); //00/11 dp (li, co + 1, rt << 1 | 1, 1, la << 1 | (fl ^ 1), 1); //01/11 } if (!fl) dp (li, co + 1, rt << 1 | fr, 1, la << 1, 1); //11/01 } int main (){ freopen ("6.in", "r", stdin); freopen ("6.out", "w", stdout); int lim; scanf ("%d%d", &n, &m); if (m > n) Swap(n, m); lim = 1 << m; f[0][lim - 1] = 1; for (int i = 1; i <= n; ++i) dp(i, 0, 0, 0, 0, 0); printf ("%lld", f[n][lim - 1]); return 0; }

---

【例7】(COGS 1520)

题目描述

给出 n*m(n,m≤10)的方格棋盘，用 1*r 的长方形骨牌不重叠地覆盖这个棋盘，求覆盖满的方案数

代码

感谢COGS中野生神犇mikumikumi分享的代码，基本框架都是他/她的，自己打了一遍，稍加优化 附神犇注释

#include <cstdio> #include <cstring> typedef long long ll; const int maxn = 11, maxr = 1e7; ll f[2][maxr] = {0};//5 ^ 10 -> maxr ll powr[maxn] = {1}, lim;//r进制状态压缩 int n, m, r; template <typename T> void Swap (T &a, T &b){T t = a; a = b, b = t;} void dp(int li, int p, int s1, int s2){//s1是当前行的状态，s2是上一行的 if (p > m) return ; if (p == m){f[li][s1] += f[li ^ 1][s2]; return ;} for (int i = 0; i < r - 1; ++i) dp(li, p + 1, s1 * r + i, s2 * r + i + 1); dp(li, p + 1, s1 * r + r - 1, s2 * r); dp(li, p + r, s1 * powr[r] + powr[r] - 1, s2 * powr[r] + powr[r] - 1); } int main (){ freopen ("examseven.in", "r", stdin); freopen ("examseven.out", "w", stdout); scanf ("%d%d%d", &r, &n, &m); if (m % r && n % r){printf ("0"); return 0;} if (m > n) Swap(n, m); for (int i = 1; i <= m; ++i) powr[i] = powr[i - 1] * r; f[0][(lim = powr[m]) - 1] = 1; for (int i = 1; i <= n; ++i){ dp(i & 1, 0, 0, 0); memset(f[(i & 1) ^ 1], 0, sizeof (f[0])); } printf ("%lld", f[n & 1][lim - 1]); return 0; }

---

后记

这篇论文其实2016年11月就有计划全部打完的 ，但一直都拖拖拖拖拖拖拖于是我就laji了 好的我知道这梗太冷… 代码完成过程确实发现自己很多不足 以后要有类似这种有必要学习的，一定要当时就决心代码实现 再贴下关于这个的sum吧一堆XX错误 1 没有直接枚举s^out 1 0意义不清 用s错用j 2 一直错用s[j] 为 j poj1321 rti为零时 (~ &) == ^ ? 4 答案求最大却求和 比较大小后赋的又不是所比较的值 5 floor第三次打还把方程弄错，其他倒是一点没错了 6 永远都不记得当前放的会影响到上一行，上一行的当前列不要放 7 lim 写成 powr[n] 陷入几乎抄代码样例也不过模式… 用两个gdb一行行查，查出来是dp里for中dp参数li写成i