klion26
klion26's blog
C++博客
|
首頁
|
發(fā)新隨筆
|
發(fā)新文章
|
聯(lián)系
|
聚合
|
管理
隨筆:71 文章:0 評論:17 引用:0
USACO 1_5_4 Checker Challenge (n皇后)
這題題就是n皇后,不過不超時可能比較困難,至于可能是因?yàn)橐话愕娜硕贾佑|過遞歸版的,表示那個時間和空間要求很高啊。下面我們用位運(yùn)算來解決這個問題。確切的說是
Matrix67大牛的原創(chuàng)
(再次膜拜),當(dāng)然建議先看前面兩篇,不然可能有點(diǎn)暈乎乎的。看完之后,你會發(fā)現(xiàn)自己提高了,呵呵。大牛已經(jīng)說的很清楚了,我就不多說了,貼個C語言版的代碼吧
CODE
1
max
=
(
1
<<
n)
-
1
;(n是皇后數(shù))
2
sum
=
0
;
//
最后結(jié)果在sum中
3
void
work(
int
row,
int
ld,
int
rd)
4
{
//
row是列禁止,ld是對角線禁止,rd是反對角線禁止
5
int
pos,p;
6
if
(row
==
max)
7
sum
++
;
8
pos
=
max
&
(
~
(row
|
ld
|
rd));
//
得到當(dāng)前行的可放皇后的位置
9
//
row|ld|rd是禁止位,然后取反,在和max與就是可以放皇后的位置
10
while
(
0
!=
pos)
11
{
12
p
=
pos
&
-
pos;
//
在可放的位置找第一個,然后測試
13
pos
-=
p;
//
把已經(jīng)測試過的去掉
14
work(row
+
p,(ld
+
p)
>>
1
,(rd
+
p)
<<
1
);
//
移位是因?yàn)樵诋?dāng)前行是禁位的
//
話,那么在下一行就是左移一位或者右移一位了
15
}
16
}
17
理解了上面的代碼之后,這題剩下的就是求前三個了,那個可以用遞歸版的,也可以用這個求不過還得加一個參數(shù),里面在改一下,用log或者long10求log(2)p時注意精度,不然結(jié)果4會變成3,但是單獨(dú)把3拿出來之后,4就還是4,這或許是計算機(jī)內(nèi)部的原因吧,哪位路過大牛知道的告訴聲,感激不盡,對于13皇后,我的才用了0.2S。而且1A,小小的興奮下,哈哈,第一章結(jié)束了,下面是第二章,奮斗,加油。
似乎官方的是搜索,但是還沒看,往上應(yīng)該有的,就不傳上來了,如果要的話,留郵箱吧,不過基本也沒必要了,因?yàn)槟莻€搜索時間肯定不比這個少,但是對于學(xué)習(xí)知識到是不錯的選擇。
發(fā)表于 2010-06-07 19:12
Klion
閱讀(318)
評論(0)
編輯
收藏
引用
所屬分類:
USACO
只有注冊用戶
登錄
后才能發(fā)表評論。
【推薦】100%開源!大型工業(yè)跨平臺軟件C++源碼提供,建模,組態(tài)!
相關(guān)文章:
USACO 4-1-4Cryptcowgraphy
USACO 4_1_3 Fence Loops
USACO 4_1_1 Beef McNuggets
USACO 3_3_4 Home On The Range
USACO 3_3_1 Riding The Fences
USACO 3_3_5 A Game
USACO 3_2_2 Stringsobits
USACO 3_2_6 Sweet Butter----最短路
USACO 3_1_4 Shaping Regions
USACO 2_3_5 Controlling Companies
網(wǎng)站導(dǎo)航:
博客園
IT新聞
BlogJava
博問
Chat2DB
管理
<
2010年6月
>
日
一
二
三
四
五
六
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
常用鏈接
我的隨筆
我的評論
我參與的隨筆
留言簿
(1)
給我留言
查看公開留言
查看私人留言
隨筆分類
(99)
DP(7)
(rss)
Linux學(xué)習(xí)之路(11)
(rss)
POJ(18)
(rss)
USACO(27)
(rss)
計算機(jī)專業(yè)(3)
(rss)
計算幾何
(rss)
數(shù)據(jù)結(jié)構(gòu)&字符串(14)
(rss)
數(shù)學(xué)(8)
(rss)
搜索(4)
(rss)
貪心(1)
(rss)
圖論(4)
(rss)
雜(2)
(rss)
隨筆檔案
(71)
2010年12月 (7)
2010年11月 (11)
2010年9月 (6)
2010年8月 (12)
2010年7月 (12)
2010年6月 (6)
2010年5月 (15)
2010年4月 (2)
好友鏈接
我的獨(dú)立域名
我的獨(dú)立域名
搜索
最新評論
1.?re: SQL Server 2005端口號設(shè)置
在程序中的數(shù)據(jù)庫連接字符串也應(yīng)該做相應(yīng)的更改,怎么操作啊?
--peijian
2.?re: SQL Server 2005端口號設(shè)置
如果是在本機(jī),客戶端IP還是寫localhost嗎?
--的
3.?re: VMware 安裝RedHat9時光盤無法掛載的問題[未登錄]
嗯 收獲了 謝謝
--jz
4.?re: Ubuntu死機(jī)那點(diǎn)事
確實(shí)有用,我用到第3點(diǎn),就可以了。
謝謝!
--Annie
5.?re: POJ_1195 二維樹狀數(shù)組
@yp
能有這效果,我表示非常高興
--klion26
閱讀排行榜
1.?Ubuntu死機(jī)那點(diǎn)事(4809)
2.?SQL Server 2005端口號設(shè)置(4737)
3.?POJ 1014 && 1742 多重背包的O(VN)解法(2958)
4.?三種簡單博弈問題的簡單介紹(2897)
5.?HDU_1907&2509 博弈(2316)
評論排行榜
1.?SQL Server 2005端口號設(shè)置(6)
2.?三種簡單博弈問題的簡單介紹(2)
3.?回歸CPP Blog(2)
4.?《自己動手寫操作系統(tǒng)》第一步(2)
5.?POJ_1195 二維樹狀數(shù)組(2)
Powered by:
博客園
模板提供:
滬江博客
Copyright ©2025 Klion
久久久亚洲精品蜜桃臀
|
亚洲中文字幕久久精品无码喷水
|
色综合久久久久网
|
青青青青久久精品国产h久久精品五福影院1421
|
97久久久精品综合88久久
|
久久久精品久久久久久
|
久久九九兔免费精品6
|
青青国产成人久久91网
|
久久经典免费视频
|
91久久精品国产成人久久
|
久久成人国产精品免费软件
|
成人a毛片久久免费播放
|
久久国产精品成人影院
|
亚洲中文字幕伊人久久无码
|
国产99久久久久久免费看
|
亚洲精品tv久久久久久久久
|
中文字幕日本人妻久久久免费
|
色综合久久最新中文字幕
|
中文字幕人妻色偷偷久久
|
久久这里的只有是精品23
|
亚洲国产精品久久久久婷婷软件
|
91精品国产91久久久久久
|
区亚洲欧美一级久久精品亚洲精品成人网久久久久
|
久久亚洲高清观看
|
久久久久亚洲av无码专区导航
|
亚洲国产视频久久
|
亚洲国产成人精品女人久久久
|
中文无码久久精品
|
蜜桃麻豆WWW久久囤产精品
|
久久久无码精品亚洲日韩软件
|
91精品国产高清久久久久久国产嫩草
|
亚洲精品tv久久久久久久久
|
97精品依人久久久大香线蕉97
|
久久亚洲精品国产精品婷婷
|
亚洲国产成人精品久久久国产成人一区二区三区综
|
久久精品国产亚洲av高清漫画
|
伊人久久大香线蕉亚洲五月天
|
亚洲精品tv久久久久久久久
|
少妇久久久久久被弄高潮
|
久久天天躁狠狠躁夜夜96流白浆
|
精品久久久噜噜噜久久久
|