[USACO] sec_1-4_The Clocks

過年前來一帖~

有夠詭異的題目

乍看之下用BFS暴搜 DEBUG DE了3小時= =(其實好像還是可以 只是沒找到正確的剪枝而已)

後來想一想(查一查..)由於每個方法轉4次以上就會重複 SO 3^7爆破摟
-----------------------------------------------------------------
試過許多方法 一開始原本要試TBFS(雙向廣度優先搜尋) 後來因為不熟悉用法而且題目要求解路徑

想說太麻煩而改回單純BFS 但又遭遇了一開始提到的問題(重複判斷一直出錯 導致錯誤解)

後來試了下DFS 但好像方法錯了 一直試一直試....

最後只好爬文 剛好看到發人深省的一文

"順序不影響結果 & 鎂種發法超過4次等於沒轉"

怎麼一開始會沒想到呢？ 應該是太執著於DEBUG 而沒有從頭到尾重新檢視題目吧 要以此為鑑阿
-----------------------------------------------------------------
USER: Lee Pu [leepupu1]
TASK: clocks
LANG: C++

Compiling...
Compile: OK

Executing...
Test 1: TEST OK [0.000 secs, 3176 KB]
Test 2: TEST OK [0.000 secs, 3176 KB]
Test 3: TEST OK [0.076 secs, 3176 KB]
Test 4: TEST OK [0.022 secs, 3176 KB]
Test 5: TEST OK [0.054 secs, 3176 KB]
Test 6: TEST OK [0.076 secs, 3176 KB]
Test 7: TEST OK [0.086 secs, 3176 KB]
Test 8: TEST OK [0.054 secs, 3176 KB]
Test 9: TEST OK [0.076 secs, 3176 KB]

All tests OK.
Your program ('clocks') produced all correct answers! This is your
submission #14 for this problem. Congratulations!

Here are the test data inputs:

------- test 1 ----
9 9 12
6 6 6
6 3 6
------- test 2 ----
12 9 12
9 9 9
12 9 12
------- test 3 ----
6 9 3
3 3 9
12 12 12
------- test 4 ----
9 3 9
9 9 9
9 9 9
------- test 5 ----
6 12 12
12 12 12
12 12 12
------- test 6 ----
3 12 9
6 6 6
12 12 12
------- test 7 ----
12 3 3
3 6 6
12 3 6
------- test 8 ----
12 3 9
9 12 12
3 6 9
------- test 9 ----
9 12 9
12 3 12
9 12 9
Keep up the good work!
Thanks for your submission!

CODE

ACM Q571

ACM Q571 Jugs

大家應該都有玩過到水遊戲吧？ 就是說有某甲很無聊，拿了兩個空杯子，最大容量分別是Ca,Cb公升

你現在有無限多的水(水資源浩劫..) 題目要求你裝出N公升的水

我一開始以為有啥神奇的解法 結果竟然要用BFS暴搜出解答 BFS竟然還能用在這種地方？！

是說用每一種方法去試 確定沒重複再丟到QUEUE裡 等待下次遍歷 一開始寫了快200行...AC 但看了別人的碼後傻眼

我竟然忘了可以直接開bool陣列去存visit 頭腦不清楚阿~~

貼上第2版的碼 精簡過 也把visit改正了..

The Code

ACM Q989

一直有一個夢想 寫出會解數獨的程式

一年前剛學會backtrace時 興奮的寫了一個解數獨的程式 結果應位判斷放錯位置 一直跑不出來

後來因為忙東忙西也忘記這件事了 最近看到ACM Q989 突然想其來一年前的失敗經驗

想說一年也該有些長進了 結果還是解了3天才解出來XD 100多行 真慘

重點是check()函式 只要再backtrace時判斷是否符合規定 這樣答案就呼之欲出了XDD

The Code

ACM Q762

恩...跟著BFS提單做的

不算太難的BFS 還是寫了12X行 把程式名稱轉成編號比較需要想一下

而最短路徑則是當BFS找到後要結束BFS 不然會被覆蓋調 還有如過一直遇到RE就用以下測資
1
AA BB
AA CC

有點瞎XD

The Code

ACM Q10583

這提蠻值得注意的是Disjoint set

使用 uniun 合併集合 最後再算出集合個數

The Code

ACM Q11727

簡單Ad Hoc題

ACM Q10812

簡單Ad Hoc題

ACM Q10066

令人頭痛的LCS

目前我只有一個初步模糊的概念

所以先寫找長度 比較簡單的題目 參考演算法筆記的

Longest Common Subsequence

說真的 那麼多書看了還是 演算法筆記 一看就差不多了解了

<

等DP觀念在成熟一點在嘗試找出這個序列

不貼碼了 幾乎跟演算法筆記一模一樣

ACM Q10082

模擬題

不難 小心格式

The Code

ACM Q483

簡單題...

輸出時要注意格式 小心句子後面多輸出空格

還有當輸入是一行空白時 不用再輸出一行

The Code

ACM Q136

無言 還沒學會DP

先慢慢算在直接輸出吧

待研究........

ACM Q133

開心阿 難得送一次就AC了

AD HOC題目

花了1小時 有點囧

The Code

ACM Q191

算蠻簡單的一題 稍微想一下九知道這題的78測資會是啥

但還是解了3個小時 應該是一次作太多事了＠＠

這壞習慣真該改一改

ACM Q336

重拾熱忱後又因為課業被耽誤了許久...

別談過去了

最近又開始接觸圖論

當然先看BFS DFS DFS接近backtrace的玩法我比較熟

所以我先研究BFS 廣度優先搜尋

不錯的例題：Q336

花了整個下午約5小時才解完

基礎架構1HR之內就完成了

但Debug了N小時.....

後來去看國外的討論版

原來....

測資太神奇了 除了有單獨存在的點（自己連自己）

還有提出的問題是剛剛建立圖的時候並沒有輸入的

大略如上

程式碼太醜 就不附上啦XDDDDDDD

程式設計...

最近愛上了C++

才發現原來VB原來這麼高階@@

後來覺得原來我的基礎根本不夠

現在我打算從資料結構 作業系統開始 完完全全的了解電腦^_^

以後我會在這裡發表一些我的研究心得 希望有興趣的網友不吝嗇指教喔^___^