这道题花了很多的时间额。。。
大意是九皇后。
USACO给出的Hint很强大，但自己下还是TLE在最后一个数据上，时间消耗1.3s左右，方法就是普通的标记数组表示不能访问。
弄反斜线的坐标和索引对应时掣肘了那么几下。。。
后来看到有人说位运算，就把之前的标记数组改成了二进制状态表示，但效果一点都没有，左右是一样，代码里面还是要For那些点来判断。
就按Hint里的把多次调用的小代码放到主体中，因为大量的Call也会造成nontrial的消耗，但未果。
至于Hint里说的对称和旋转重复的部分不去跑，可以省掉不少时间，可是不会。
看了大牛们的Blog后，才知道如下：
用3个数组来表示3种情况下对应的某行的状态，然后每次都获得一个数，表示出那些位置是可以访问的，用t&(-t)的办法，可以获得最低位的1，每次的提取就省掉了没用的For了，还有用到^操作，是练习位运算的一道好题。
用了如下的位运算操作AC如下：
又有一大牛这样说，n分奇数和偶数，偶数时，第一行枚举前半段，这样求的的解一定可以在右边找到镜像。奇数时，分别枚举中间的行和列，要求都小于一般，且规定行小于列，这样可以保证旋转+镜像后的解不重复且这些解就是最终的解，只有1/8的原来的个数。
介于实现考虑，都用对称，省掉一半的时间，n=6时特判。
AC如下：
到Chapter 2了，兴奋。
1 #include < iostream > 2 #include < string > 3 #include < algorithm > 4 #include < string .h > 5 #include < vector > 6 #include < math.h > 7 #include < time.h > 8 #include < queue > 9 #include < set > 10 using namespace std; 11 12 const int MAX = 15 ; 13 14 int n, cnt, ansCnt; 15 int full; // 表示都能放1111..n 16 int limit; // 表示优化对称用的 17 int stateCol[MAX]; 18 int stateA[MAX]; // A为主对角线 19 int stateB[MAX]; // B为从对角线 20 int ans[MAX]; 21 // 表示棋盘中每行的各种方法的状态 22 // 1表示不能放 23 24 void ready() 25 { 26 memset(stateCol, 0 , sizeof (stateCol)); 27 memset(stateA, 0 , sizeof (stateA)); 28 memset(stateB, 0 , sizeof (stateB)); 29 full = ( 1 << n) - 1 ; 30 limit = ( 1 << ((n + 1 ) / 2 )) - 1 ; 31 cnt = 0 ; 32 ansCnt = 0 ; 33 } 34 35 int getBit( int x) 36 { 37 int res = 0 ; 38 while (x) 39 { 40 x >>= 1 ; 41 res ++ ; 42 } 43 return res; 44 } 45 46 void dfs( int row, int t) 47 { 48 if (row == n) 49 { 50 cnt ++ ; 51 if (cnt <= 3 ) 52 { 53 for ( int i = 0 ; i < n; i ++ ) 54 { 55 if (i == 0 ) printf( " %d " , ans[i]); 56 else printf( " %d " , ans[i]); 57 } 58 printf( " \n " ); 59 } 60 ansCnt ++ ; 61 if (n > 6 && ans[ 0 ] <= n / 2 ) ansCnt ++ ; 62 return ; 63 } 64 // 先取出能放的状态,can表示能放的位置 65 int can = t ^ (stateCol[row] | stateA[row] | stateB[row]); 66 while (can) 67 { 68 int col = (can & ( ~ can + 1 )); // 取最后的一位1,按顺序遍历 69 ans[row] = getBit(col); 70 stateCol[row + 1 ] = stateCol[row] | col; 71 stateA[row + 1 ] = ((stateA[row] | col) << 1 ) & full; 72 stateB[row + 1 ] = (stateB[row] | col) >> 1 ; 73 dfs(row + 1 , full); 74 can ^= col; 75 } 76 } 77 78 void go() 79 { 80 if (n > 6 ) dfs( 0 , limit); 81 else dfs( 0 , full); 82 printf( " %d\n " , ansCnt); 83 } 84 85 int main() 86 { 87 // freopen("checker.in", "r", stdin); 88 // freopen("checker.out", "w", stdout); 89 90 scanf( " %d " , & n); 91 ready(); 92 go(); 93 }
感谢：
http://blog.sina.com.cn/s/blog_5ed6a69f0100dywr.html
http://jingsixee.blog.hexun.com/4915336_d.html
转载于:https://www.cnblogs.com/litstrong/archive/2010/04/15/1712983.html
相关资源：数据结构—成绩单生成器