Snowdream
posts - 403, comments - 310, trackbacks - 0, articles - 7
BlogJava
::
首頁
::
新隨筆
::
聯系
::
聚合
::
管理
USACO 1.1.5 Checker Challenge
Posted on 2007-06-03 19:22
ZelluX
閱讀(603)
評論(0)
編輯
收藏
所屬分類:
Algorithm
一開始什么優化都沒有,過不了了(記得以前是可以的啊)
然后用了三個hash數組記錄各列、對角線棋子的放置情況,再加上左右對稱解的優化,總算在0.828秒里過了
/**/
/*
PROG: checker
ID: 06301031
LANG: C++
*/
#include
<
iostream
>
#include
<
fstream
>
using
namespace
std;
int
g[
13
];
bool
column[
13
], diag1[
25
], diag2[
25
];
int
n;
int
countResult
=
0
;
int
mid
=
0
, firstHalf
=
0
;
ifstream fin(
"
checker.in
"
);
ofstream fout(
"
checker.out
"
);
void
DFS(
int
t)
{
int
i;
if
(t
==
n)
{
countResult
++
;
if
(countResult
<=
3
)
{
fout
<<
g[
0
]
+
1
;
for
(i
=
1
; i
<
n; i
++
)
{
fout
<<
"
"
<<
g[i]
+
1
;
}
fout
<<
endl;
}
return
;
}
for
(g[t]
=
0
; g[t]
<
n; g[t]
++
)
{
if
((countResult
>
3
)
&&
(t
==
0
))
{
if
(g[t]
==
n
/
2
)
{
firstHalf
=
countResult;
if
(n
%
2
==
0
)
{
fout
<<
firstHalf
*
2
<<
endl;
exit(
0
);
}
}
if
((g[t]
==
n
/
2
+
1
)
&&
(n
%
2
==
1
))
{
mid
=
countResult
-
firstHalf;
fout
<<
firstHalf
*
2
+
mid
<<
endl;
exit(
0
);
}
}
if
(column[g[t]])
{
continue
;
}
if
(diag1[g[t]
+
t])
{
continue
;
}
if
(diag2[g[t]
-
t
+
n])
{
continue
;
}
diag1[g[t]
+
t]
=
true
;
diag2[g[t]
-
t
+
n]
=
true
;
column[g[t]]
=
true
;
DFS(t
+
1
);
diag1[g[t]
+
t]
=
false
;
diag2[g[t]
-
t
+
n]
=
false
;
column[g[t]]
=
false
;
nextPosition:
;
}
}
int
main()
{
fin
>>
n;
int
i;
for
(i
=
0
; i
<
n; i
++
)
{
column[i]
=
false
;
}
for
(i
=
0
; i
<
n
*
2
-
1
; i
++
)
{
diag1[i]
=
false
;
diag2[i]
=
false
;
}
DFS(
0
);
fout
<<
countResult
<<
endl;
fout.close();
return
0
;
}
新用戶注冊
刷新評論列表
只有注冊用戶
登錄
后才能發表評論。
網站導航:
博客園
IT新聞
Chat2DB
C++博客
博問
管理
相關文章:
函數式編程另類指南[zz]
URAL 1011
Sorting Networks
URAL 題解 - wiki
《編程之美》上的一道題目的討論
求n個32位無符號整數中異或后值最大的兩個數
SICP 習題記錄 (1)
正則表達式的復雜度
Minesweeper is NP-complete
Tom Duff on Duff's Device
Powered by:
BlogJava
Copyright © ZelluX
日歷
<
2007年6月
>
日
一
二
三
四
五
六
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
6
7
常用鏈接
我的隨筆
我的評論
我的參與
最新評論
留言簿
(21)
給我留言
查看公開留言
查看私人留言
隨筆分類
(390)
Algorithm(57)
C/C++(39)
Courses(15)
Economics(2)
Laboratory(25)
Linux(47)
Mathematics(12)
OOP(89)
Scripting(19)
Security(3)
System(28)
Web(10)
書、電影、音樂(11)
其他(14)
點滴(19)
隨筆檔案
(389)
2009年12月 (1)
2009年4月 (1)
2009年3月 (4)
2009年2月 (2)
2009年1月 (2)
2008年11月 (1)
2008年10月 (9)
2008年9月 (1)
2008年7月 (2)
2008年6月 (4)
2008年5月 (12)
2008年4月 (18)
2008年3月 (7)
2008年2月 (33)
2008年1月 (19)
2007年12月 (8)
2007年11月 (14)
2007年10月 (24)
2007年9月 (18)
2007年8月 (28)
2007年7月 (33)
2007年6月 (26)
2007年5月 (30)
2007年4月 (92)
文章檔案
(7)
2007年7月 (2)
2007年5月 (4)
2007年4月 (1)
相冊
Illustration
15ers
jonathan的BLOG
Right There...
宙斯魚的小魚缸
小鮑的世界
簡單幸福
逃遁的Persephone
阿繆爾的錦瑟
風之語的BLOG
友情鏈接
(04CS) ljh
(05CS) 小菜虎的窩
(06CS) FreePeter
(06SS) Overboming
(06SS) Sherry
(06SS) 十指飛揚
(06SS) 銀色子彈
luohandsome的專欄
平淡是真——啃啃不老閣
收藏夾
[ADN.cn]Library
Debian學習筆記
Dictionary of Algorithms and Data Structures
Gollum
Lex&Yacc
Max On Java
techInterview Discussion
核桃仁
程序員面試題精選100題
鐵手
搜索
積分與排名
積分 - 338701
排名 - 166
最新隨筆
1.?新博客
2.?慎用xen的make world...
3.?內存模型相關的資料
4.?安全方面的經典論文:A Logic of Authentication
5.?Lock-Free 算法的幾個鏈接
6.?10 Papers Every Programmer Should Read
7.?PieTTY中按Ctrl+S導致掛起的問題解決
8.?Finding and Reproducing Heisenbugs in Concurrent Programs
9.?Ubuntu 8.10 瀏覽網頁不穩定的解決方法
10.?[zz]蘇南經濟模式興衰親歷記
最新評論
1.?re: C/C++中的序列點
說的太好了,解決我長久的困擾!
--除美滅日平韓
2.?re: 原來GCC是支持尾遞歸的遞推優化的
評論內容較長,點擊標題查看
--darkhorse
3.?re: Arch下配置samba服務
我按照你的方法,安裝了SAMBA,但是 /etc/rc.d/samba start 啟動不了samba服務。提示不存在這個文件或目錄的,怎么辦?
--zhangbear
4.?re: [zz]LKM Rootkits on Linux x86 v2.6
rhel 5 系列 安裝了 Xen 內核, 怎么rootkit xen kernel 呢?
--消息
5.?re: CLRS 習題 16.2-6 部分背包問題的O(n)算法
@ynnej
T(n)=2T(n/2)+O(n) 才是 nlgn 注意其中有一個2
--荒廢庭院
閱讀排行榜
1.?[zz]vim+ctags+taglist插件安裝使用(18319)
2.?memcpy函數代碼分析(9395)
3.?[zz]Zotero與Endnote的互相導入(8789)
4.?BNF 文法 (1) - 語法樹 | 二義性的解決(8282)
5.?Java泛型中的? super T語法(6568)
評論排行榜
1.?C# 學習筆記 (1)(14)
2.?Windows - QQ、網頁Flash視頻無聲音的解決方法(14)
3.?URAL 1011(10)
4.?《編程之美》上的一道題目的討論(8)
5.?Singleton模式與雙檢測鎖定(DCL)(7)
主站蜘蛛池模板:
a毛片在线还看免费网站
|
国产亚洲精品看片在线观看
|
大地资源网高清在线观看免费
|
亚洲一级毛片免费在线观看
|
亚洲人成无码www久久久
|
精品久久久久国产免费
|
国产成人AV免费观看
|
国产午夜亚洲精品不卡
|
久久精品国产亚洲AV麻豆网站
|
国产在线ts人妖免费视频
|
久久精品国产免费观看三人同眠
|
A国产一区二区免费入口
|
美女被免费网站在线视频免费
|
亚洲一区二区三区高清视频
|
99人中文字幕亚洲区
|
国产A在亚洲线播放
|
毛茸茸bbw亚洲人
|
亚洲国产成人久久综合碰
|
国产麻豆剧传媒精品国产免费
|
和日本免费不卡在线v
|
亚洲精品在线免费观看视频
|
久久成人免费电影
|
国产免费爽爽视频在线观看
|
中文字幕在线视频免费
|
精品一区二区三区高清免费观看
|
免费福利资源站在线视频
|
国产在亚洲线视频观看
|
激情婷婷成人亚洲综合
|
高h视频在线免费观看
|
免费看一级高潮毛片
|
黄床大片30分钟免费看
|
免费人成在线观看播放a
|
猫咪免费人成网站在线观看入口
|
国产亚洲精品美女久久久久久下载
|
亚洲AV永久无码天堂影院
|
亚洲av乱码中文一区二区三区
|
久久精品亚洲日本波多野结衣
|
小说专区亚洲春色校园
|
日韩在线视频播放免费视频完整版
|
亚洲爱情岛论坛永久
|
亚洲av无码成h人动漫无遮挡
|