题目大意: 和A+B一样经典的八皇后问题，要求输出前三个字典序最小的解，以及总的方案数。
解题思路： 如果N比较小，那么随便搜都可以过。但如果N大等于10，就要求对程序进行优化。
这题我很奇葩地用广搜来做，各种状态压缩压线飘过，搓的一逼。AC后去网上找了几篇解题报告，发现用位运算来优化深搜，非常飘逸。
其中属Matrix67的文章分析地最透彻，最好理解。想深入理解可移步：http://www.matrix67.com/blog/archives/268。
在这里我把集中常用的运算整理下：
- 去掉最后一位 | (101101->10110) | x >> 1
- 在最后加一个0 | (101101->1011010) | x << 1
- 在最后加一个1 | (101101->1011011) | (x << 1) + 1
- 把最后一位变成1 | (101100->101101) | x | 1
- 把最后一位变成0 | (101101->101100) | (x | 1)-1
- 最后一位取反 | (101101->101100) | x ^ 1
- 把右数第k位变成1 | (101001->101101,k=3) | x | (1 << (k-1))
- 把右数第k位变成0 | (101101->101001,k=3) | x&(~(1 << (k-1))
- 右数第k位取反 | (101001->101101,k=3) | x ^ (1 << (k-1))
- 取末三位 | (1101101->101) | x & 7
- 取末k位 | (1101101->1101,k=5) | x & (1 << (k-1))
- 取右数第k位 | (1101101->1,k=4) | (x >> (k-1)) & 1
- 把末k位变成1 | (101001->101111,k=4) | x | (1 << (k-1))
- 末k位取反 | (101001->100110,k=4) | x ^ (1 << (k-1))
- 把右边连续的1变成0 | (100101111->100100000) | x & (x+1)
- 把右起第一个0变成1 | (100101111->100111111) | x | (x+1)
- 把右边连续的0变成1 | (11011000->11011111) | x | (x-1)
- 取右边连续的1 | (100101111->1111) | (x ^ (x+1)) >> 1
- 去掉右起第一个1的左边 | (100101000->1000) | x & (x ^ (x-1))
测试数据：
13
1 3 5 2 9 12 10 13 4 6 8 11 7
1 3 5 7 9 11 13 2 4 6 8 10 12
1 3 5 7 12 10 13 6 4 2 8 11 9
73712
代码：
- /*
- ID:imonlyc1
- PROG:checker
- LANG:C++
- */
- #include <stdio.h>
- #include <string.h>
- int state,cnt;
- int ans[15],n;
- int GetCol(int a) //不用 log 节省时间
- {
- switch (a)
- {
- case 1:
- return 1;
- case 2:
- return 2;
- case 4:
- return 3;
- case 8:
- return 4;
- case 16:
- return 5;
- case 32:
- return 6;
- case 64:
- return 7;
- case 128:
- return 8;
- case 256:
- return 9;
- case 512:
- return 10;
- case 1024:
- return 11;
- case 2048:
- return 12;
- case 4096:
- return 13;
- }
- }
- void Dfs(int row, int ld, int rd, int deep) {
- int pos, col;
- if (row != state) {
- pos = state & ~(row | ld | rd); //取合法的位置
- while (pos != 0) {
- col = pos & -pos; //取最右边那一列，col = 1<<x。等于pos&((~pos)+1)
- pos = pos - col; //慢慢往左移动
- if (cnt < 3) ans[deep] = col; //记录前三个的答案，ans[i]表示第i行放的是x列
- //三个状态都要做相应改变，对角线一个向左一个向右
- Dfs(row + col, (ld + col) >> 1, (rd + col) << 1, deep + 1);
- }
- }
- else {
- cnt++;
- if (cnt <= 3) {
- for (int i = 1; i <= n - 1; i++)
- printf("%d ",GetCol(ans[i]));
- printf("%d\n",GetCol(ans[n]));
- }
- }
- }
- int main()
- {
- //freopen("checker.in","r",stdin);
- //freopen("checker.out","w",stdout);
- scanf("%d",&n);
- state = (1 << n) - 1;
- Dfs(0,0,0,1);
- printf("%d\n",cnt);
- return 0;
- }