当罗梅洛走进房间时,卡马克一如往常坐在显示器前优化着下一代图像引擎。
他的房间比以前大了不少,也更干净整洁,但仍然是那么简朴无华
C++博客
|
首页
|
发新随笔
|
发新文章
|
联系
|
聚合
|
管理
USACO Chapter1 Done
经过几天奋战,把USACO Chapter1搞定了
Section 1.4:
PROB Packing Rectangles
(超级恶心的关于包装一些矩形的题)
Section 1.5:
PROB Checker Challenge (上一篇提到过的,传说中的“八皇后”)
备份一下我写的所有题代码:
http://www.cppblog.com/Files/CK985/USACO-Chapter1.rar
继续Chapter 2.
发表于 2008-12-11 16:42
CK
阅读(1505)
评论(1)
编辑
收藏
引用
评论
#
re: USACO Chapter1 Done
如果你在第一章最后一题Checker卡住了,请看这里.
Chapter1最后一题Checker,即"n皇后".
DFS+位运算+剪枝.
即用位运算来进行状态判断.比如,在N=8时,要在某行的第4个位置放一个棋子,则可以表达为:00010000,也就是1<<4.这样的话,再加上适当的剪枝来搜索,就可以大大提高搜得效率.
那么又如何剪枝呢?我们可以考虑只枚举某些情况,其他情况可以通过枚举出来的情况通过对称,旋转等变换得到.
先看N为偶数的情况.为偶数的话,第一排只用枚举一半(1~N/2),剩下的一半可以由枚举出来的情况可以由前面的情况对称得到.
那么N为奇数的时候呢,就应该枚举中间列(第N div 2 +1 列)以及中间行(N div 3 + 1行)的前半部分(1~N div 2),并且,枚举时,中间列的枚举数应当大于中间行的枚举数,或者小于之.这样确定了后,就可以通过4种旋转*2种对称得到8种图形,并且是不重复的.剩下最后一种情况就是,刚好枚举点在最中心时,再全部枚举一遍.这样就找出所有方案数了.
方案数问题解决了后,就再写个裸搜,把前3种情况搜出来,便可以通过此题了.
经实验,通过N=13时,只需要0.2s.
刷新评论列表
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
随笔:15 文章:0 评论:45 引用:0
<
2024年9月
>
日
一
二
三
四
五
六
25
26
27
28
29
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
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(4)
给我留言
查看公开留言
查看私人留言
随笔档案
2010年3月 (1)
2010年1月 (2)
2009年11月 (1)
2009年9月 (1)
2009年8月 (1)
2009年6月 (2)
2009年5月 (2)
2009年1月 (1)
2008年12月 (4)
文章分类
Direct3D中的2D应用底层
(rss)
相册
else
GameMaster
Project DIVA
Sumreen
魔法少女葵
友情链接
SonicMisora的博客
RUA牛的博客
搜索
最新评论
1. re: DXUT工作模式的简单解析-底层框架
您好!我希望能跟你学习DXUT以及3D开发
--张忆
2. re: Direct3D中的简单2D绘制(上)——纹理的绘制[未登录]
汝好
--SonicMisora
3. re: NOIP2009前一天[未登录]
=_,=
--SonicMisora
4. re: Direct3D中的简单2D绘制(上)——纹理的绘制
图片为啥是⑥⑧娘……………………
--Tamashii
5. re: BMS(音乐游戏)文件结构解析
想起当年玩单机版的劲乐团.....
--陈昱(CY)
阅读排行榜
1. Direct3D中的简单2D绘制(上)——纹理的绘制(4944)
2. Direct3D中的简单2D绘制(下)——文字的绘制(4179)
3. DXUT工作模式的简单解析-底层框架(2736)
4. BMS(音乐游戏)文件结构解析(2731)
5. CTSC、APIO以及四川省信息学省队选拔赛总结(2604)
评论排行榜
1. CTSC、APIO以及四川省信息学省队选拔赛总结(16)
2. Direct3D中的简单2D绘制(上)——纹理的绘制(7)
3. USACO Chapter3 Done(4)
4. USACO Chapter4 Done(4)
5. Direct3D中的简单2D绘制(下)——文字的绘制(3)