洛谷P 1562はまだN皇后です
1173 ワード
転送ゲート:https://www.luogu.com.cn/problem/P1562
参考ブログ:https://blog.csdn.net/qq_40828060/article/details/79364577
この問題は最初は普通のdfsで、タイムアウトしました.
大物がビット演算を使うのを見て、私もやってみます.違うのは、私は0で置くことができないことを表して、1は置くことができることを表して、それでは、dfsのパラメータの伝達の時少し面倒です
dfs関数では、pのうちの1は、その行が置かれている位置を表し、さらにdfsの場合、次の行への影響を考慮して、~pは、置かれている位置を表す.
同じ列の角度で、現在の列&~p:row&~pであるべきである
主対角線(left diagonal)では、(現在の状態&~p)>>1であり、さらに高位補1であるべきであり、このとき補の1は(1<>1)であるべきである
二次対角線(right diagonal)では、(現在の状態&~p)<<1であり、さらに低位補1であるべきであり、このとき補1は真の1である.
このようにするのはとても面倒で、やはり置くことができるのは0で表して、置くことができないのは1でプログラムを書くのに便利ですと言わざるを得ません.
私は強情に2時間以上デバッグしてやっとビット演算をここでやり終えた.ああ、おかずが多すぎます.!!!
参考ブログ:https://blog.csdn.net/qq_40828060/article/details/79364577
この問題は最初は普通のdfsで、タイムアウトしました.
大物がビット演算を使うのを見て、私もやってみます.違うのは、私は0で置くことができないことを表して、1は置くことができることを表して、それでは、dfsのパラメータの伝達の時少し面倒です
dfs関数では、pのうちの1は、その行が置かれている位置を表し、さらにdfsの場合、次の行への影響を考慮して、~pは、置かれている位置を表す.
同じ列の角度で、現在の列&~p:row&~pであるべきである
主対角線(left diagonal)では、(現在の状態&~p)>>1であり、さらに高位補1であるべきであり、このとき補の1は(1<>1)であるべきである
二次対角線(right diagonal)では、(現在の状態&~p)<<1であり、さらに低位補1であるべきであり、このとき補1は真の1である.
このようにするのはとても面倒で、やはり置くことができるのは0で表して、置くことができないのは1でプログラムを書くのに便利ですと言わざるを得ません.
私は強情に2時間以上デバッグしてやっとビット演算をここでやり終えた.ああ、おかずが多すぎます.!!!
#include
#include
int N;
int ans;
int map[15];
int allone;
void dfs(int i,int row,int ld,int rd);
int main(void) {
char ch[16];
int i,j;
scanf("%d
",&N);
allone=(1<>1)+((rd&~p)>>1));// 1, 0
}
}