klion26
klion26's blog
C++博客
|
首页
|
发新随笔
|
发新文章
|
联系
|
聚合
|
管理
随笔:71 文章:0 评论:17 引用:0
USACO 1_5_4 Checker Challenge (n皇后)
这题题就是n皇后,不过不超时可能比较困难,至于可能是因为一般的人都知接触过递归版的,表示那个时间和空间要求很高啊。下面我们用位运算来解决这个问题。确切的说是
Matrix67大牛的原创
(再次膜拜),当然建议先看前面两篇,不然可能有点晕乎乎的。看完之后,你会发现自己提高了,呵呵。大牛已经说的很清楚了,我就不多说了,贴个C语言版的代码吧
CODE
1
max
=
(
1
<<
n)
-
1
;(n是皇后数)
2
sum
=
0
;
//
最后结果在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));
//
得到当前行的可放皇后的位置
9
//
row|ld|rd是禁止位,然后取反,在和max与就是可以放皇后的位置
10
while
(
0
!=
pos)
11
{
12
p
=
pos
&
-
pos;
//
在可放的位置找第一个,然后测试
13
pos
-=
p;
//
把已经测试过的去掉
14
work(row
+
p,(ld
+
p)
>>
1
,(rd
+
p)
<<
1
);
//
移位是因为在当前行是禁位的
//
话,那么在下一行就是左移一位或者右移一位了
15
}
16
}
17
理解了上面的代码之后,这题剩下的就是求前三个了,那个可以用递归版的,也可以用这个求不过还得加一个参数,里面在改一下,用log或者long10求log(2)p时注意精度,不然结果4会变成3,但是单独把3拿出来之后,4就还是4,这或许是计算机内部的原因吧,哪位路过大牛知道的告诉声,感激不尽,对于13皇后,我的才用了0.2S。而且1A,小小的兴奋下,哈哈,第一章结束了,下面是第二章,奋斗,加油。
似乎官方的是搜索,但是还没看,往上应该有的,就不传上来了,如果要的话,留邮箱吧,不过基本也没必要了,因为那个搜索时间肯定不比这个少,但是对于学习知识到是不错的选择。
发表于 2010-06-07 19:12
Klion
阅读(283)
评论(0)
编辑
收藏
引用
所属分类:
USACO
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
相关文章:
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
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
<
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学习之路(11)
(rss)
POJ(18)
(rss)
USACO(27)
(rss)
计算机专业(3)
(rss)
计算几何
(rss)
数据结构&字符串(14)
(rss)
数学(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)
好友链接
我的独立域名
我的独立域名
搜索
最新评论
1. re: SQL Server 2005端口号设置
在程序中的数据库连接字符串也应该做相应的更改,怎么操作啊?
--peijian
2. re: SQL Server 2005端口号设置
如果是在本机,客户端IP还是写localhost吗?
--的
3. re: VMware 安装RedHat9时光盘无法挂载的问题[未登录]
嗯 收获了 谢谢
--jz
4. re: Ubuntu死机那点事
确实有用,我用到第3点,就可以了。
谢谢!
--Annie
5. re: POJ_1195 二维树状数组
@yp
能有这效果,我表示非常高兴
--klion26
阅读排行榜
1. Ubuntu死机那点事(4775)
2. SQL Server 2005端口号设置(4687)
3. POJ 1014 && 1742 多重背包的O(VN)解法(2923)
4. 三种简单博弈问题的简单介绍(2858)
5. HDU_1907&2509 博弈(2275)
评论排行榜
1. SQL Server 2005端口号设置(6)
2. 三种简单博弈问题的简单介绍(2)
3. 回归CPP Blog(2)
4. POJ_1195 二维树状数组(2)
5. 《自己动手写操作系统》第一步(2)