調和的靈感

相當有趣的一題....寫程式產生器 用自創的Modified-Permutation Algo (￣▽￣＃)﹏﹏ 第一次寫有點痛苦，過了幾天醞釀過想法後，寫起來很順很快就AC了 距離連號解題剩下最後一題107了..

I have a dream..... 就是....一次AC..... 最好不是渣渣題.... 到底什麼時候才能達成呢？

解題策略 典型的凸包 (Convex Hull ) 問題。我是採用 Graham's Scan 來解。作法可以參考 維基條目 Graham's Scan ，我就是照著條目裡的算法原封不動實做的。 本題要找出所有被飛彈摧毀的王國的國土面積總和。過程中一共有兩件事要解決，第一個要知道每個王國的國土面積，第二個要能判斷飛彈落點有沒有打中王國。 求國土面積，要先對王國內的所有的發電廠位置求凸包，然後由凸包去計算多邊形面積 (題目頁有給多邊形面積公式) 。 判斷飛彈落點是否落在國土內，也是以凸包為基礎，沿著凸包的每個邊判斷，如果飛彈落點都在邊的左側，那就表示打中了! 注意 使用Graham's Scan 時要特別注意共線問題，尤其是起始點三點共線，例如 (0,0) (1,1) (2,2) (1,3) ，求出來的凸包應該是 (0,0) (2,2) (1,3)。 閒聊 @2011.10.07 有點囉嗦的題目。2008年底我第一次解這題，因為過程有點曲折，所以花了好幾天才解出來，而且一直搞不定 std::sort( ) 的判斷函數，現在重寫一遍，感覺比較清爽一些了!

 "you can't add apples and oranges."「你不能把蘋果和橘子加在一起」 --談為什麼需要向量 The central porblem of linear algebra is to solve a system of equations. 線性代數的核心問題就是要解方程組！ It is also common sense: If you put on socks and then shoes, the first to be taken off are the ___. 常識也告訴我們：假如你先穿襪子再穿鞋，那麼脫的時候，首先該脫掉___。 --談為何AB的反矩陣是B -1 A -1 Ax combines the columns of A while x T A T combines the rows of A T Ax線性組合了A的諸行，而x T A T 線性組合了A T 的諸列。 --談為何(AB) T = B T A T 最近看Gilbert Strang寫的『Introduction to Linear Algebra』，Strang教授講法生動，不論是趣味的例子，或者是一句話直搗觀念核心，都常讓我拍案叫絕。 比起補習班名師的講義，研讀起來樂趣大多了。有機會再補上更多句子。

渣渣題三號 判斷點是否在矩形內。在頭腦不清的凌晨三點，犯了一些低級錯誤，還好很快就AC了。 我最近的休閒娛樂就是寫渣渣題....

Buffered加速版 0.020s。看到很多0.000s，這我真的不知道怎麼做了.... 該不會是用組語寫吧...這題用組語寫似乎很簡單....

難題寫多了，來寫渣渣題。AC 0.020秒

解題策略 Some Hints about uVA 104  gits大大說得很清楚，我就不囉唆作法了。 閒聊 苦思良久的UVa 104終於在 gits 幾乎手把手的帶領下寫出來了，了結了多天以來的心中懸念。XDDD稍微變化題，馬上就把我土法煉鋼學會的Floyd-Warshall 打回原型。連F-W要用二維還是三維陣列來建表都搞不清楚，唉，由這題可以知道我的DP/Graph有待磨練。 只有與問題面對面的對決，在測資跟Bug中打滾一番後，才能對Algorithm有更深刻的體會吧。這也是我寫ACM的目的與樂趣所在。不過...這題還是有點心虛阿.....orz 只能說敗給你了Modified Floyd-Warshall，還未夠班....總有一天我要能秒殺這題。

by gits Original Thread http://online-judge.uva.es/board/viewtopic.php?t=7292 Well, I'll assume you understand what the problem asks. You have to find the shortest sequence that yelds a profit (not the one with the greatest profit!). If there is more then one sequence with the same length, any of those is valid. Now, you can't just try with brute force (trying all combinations) because it'll be too slow and you'll get Time Limit Exceeded. However, there's a well known algorithm, Floyd-Warshall, which will find all the shortest paths between every node to the others in just O(n^3) time. You can find more info about F-W in the net. In my previous post I said how you have to change the general F-W algorithm to work for this particular problem... As for floating point errors, most numbers representation isn't totally acurate; for instance, 0.1 is usually stored as 0.10000000000000001. After some operations, the error may influence the final result. Again, sea...

終於AC了..這次最大的心得就是，腦袋不清楚的時候不要寫程式。如果沒辦法理清思路，找出邏輯上的漏洞，那麼debug也只是亂試一通而已，一點幫助都沒有(只有浪費時間)。寫到後來連錯誤的測資也在試，現在想起來真是笨阿 我用recursive的方法去追蹤整顆樹。測資是pre-order sequence 所以遞回順序是root ,left-child , right-child 很不清楚核心Algo: int traversal(int sum, int target){ 抓左括號 抓root lc = traversal(int sum+root, int target) //向left-child遞回 rc = traversal(int sum+root, int target) //向right-child遞回 抓右括號 如果是Leaf? 判斷總和相不相等？ 如果是Internal Node，將子樹的結果繼續往上回傳。 } 另外一提，這次我參考了某份AC Code，用non-recursive(Stack)作法，但是因為用了STL stack;，最後執行時間0.510s，慢了我五倍之多。我用Recursive反而執行時間只有0.100s(Ranking 90，再進百大XDDDD)有點意外。證明一件事：Recursive不一定慢，但是STL=慢。

解題策略 這題AC的關鍵是時間，用暴力法O(n 6 ) 六層迴圈去解鐵定超時。已知最佳的解法是 O(n 3 ) ，不過一般用O(n 4 ) 就可以通過了。 我也是用 O(n 4 ) 的解法，首先用四層迴圈窮舉子矩陣的左上角(x1,y1) 跟右下角 (x2,y2) 的位置，一旦給定了子矩陣後，就要 O(1) 時間得到子矩陣的和。 要達成這個目標可以透過 sum table 來達成，我說明一下我的方法， sum table ( i, j ) 每個位置儲存的值的是原矩陣 (1,1) ~ (i, j) 之間的元素總和。像下圖的 sum table ( 2, 3 ) 的值就是 原矩陣 (1, 1) ~ (2, 3) 之間的元素和。 一旦建好 sum table，那接下來就可以簡單透過這 D - B -C + A 這四個sum table的元素直接得到子矩陣的和了。 閒聊 最後執行時間0.052 過關....改天再將作法補完，我好睏....晚安。原本用暴力法去跑 100x100 的矩陣，竟然要253秒(大汗)。

解題策略 注意 修正了兩個問題，終於AC了 1. 雖然題目頁說只要印小數點後三位，但其實要印四位。 2. 各個output case"之間"，要隔一個blank line。 但只有case間要空行，最後一個case印完後不能有多餘的空行。 (很嚴格的的格式要求...) 新版的AC Code

這題說穿就是LIS，對於已經精通LIS的我自然是小菜一碟(咦？) 不過這題有個陷阱，如果沒仔細讀懂題目的話，會以為只要做一次轉換，其實上要做兩次轉換。 第一次把rank轉成真正的event sequence，(rank[] => seq[]) 第二次才轉成可以做LIS的形式。(seq[] => seq2[]) 剛開始送了兩個WA，後來看事有悉蹺，(sample output怪怪的)，改了一下就AC了。

題目講解 這題給你一堆多維的箱子，要找出最長的裝箱序列，這個最常裝箱序列就是像俄羅斯娃娃那樣，大箱子裡面放入小箱子，一層包一層，必須要可以裝最多層這樣。 這題的麻煩就是各個箱子之間不一定有的大小關係 (數學上打這叫偏序集 Partial Order Set ，不過這兒我們先不管 )，比方說有兩個三維箱子 BoxA(1,4,5) 、BoxB(2,4,6) ，B箱比較大，所以 BoxA 可以裝進 BoxB 裡，那麼我們說 BoxA < BoxB 。 但來看 BoxC(1,5,6) 跟 BoxD (2,4,5) 呢? 我們既不能說BoxC < BoxD ，也不能說 BoxC > BoxD，BoxC 與 BoxD 兩者之間就沒有大小關係。 一個簡單的表示法就是有向圖(Directed Graph) 比如說 A(1,2,3) B(2,4,6) C(2,3,7) D(50,50,50) E(10,10,100) 的有向圖表示法: 到此為止，本題的最長裝箱序列，已經有兩種解法，第一個方法就是找圖的最長路徑，稍微修改 Warsahll algorithm 來解，第二個方法是跑 LIS 。 我這裡用 LIS(最長上昇子串列) 解法。 //先定義一個box struct struct Box { int no; int edge[10]; }; Box box[30]; LIS 法的關鍵是要先對箱子排序，確保小箱子一定在大箱子前，至於沒有大小關係箱子的就隨便放沒關係。這個排序以圖的角度是拓樸排序，以字串的角度是字典排序，兩者都行。 sort(box[i].edge) for all i //先對箱子內部的邊長排序 int lexico_less(const Box& a, const Box& b) { for(int i=0;i<dimension;++i) if( !(a.edge[i]<=b.edge[i]) ) return false; return true; } sort(box) by lexico_less(); //再用字典序排箱子 一切都準備好後，就...

看了兩次，可是每次都忘記，所以做個筆記 s: input string p: pattern Failure Function的值k，就是下次要從p(k)開始matching 舉例 Pattern A B C A B C D failure -1-1-1 0 1 2-1 Case I: Input string AB C D ADFGACEDAABBBB AB C A BCD 紅色 =not matching step1: 看最後一個matching字元 ( 綠色的字 ) 的failure function value= f step2: 將p(f)對齊綠色的位置 ( p(i)代表p的第i個字元 ) ex. f(C) = -1 ，所以p(-1)對齊上面那排的C AB C DADFGACEDAABB >>> ABCABCD Case II: ABCAB C E ACAADDBBBABCABC ABCAB C D f(C)=2 ，所以p(2)對齊上面那排的綠色C ABCAB C E ACAADDBBBABCABC >>> AB C ABCD 講的不是很有條理，不過我先給自己看懂就好= = 改天再來整理的清楚一些

讀取一串由空格分隔的整數 ex. 10 20 30 40 50 .data buffer BYTE 512 DUP(0) array DWORD 30 DUP(0) len DOWRD 0 ;//陣列長度 .code mov edx,OFFSET buffer mov ecx, (SIZEOF buffer) call ReadString ;//Read string to buffer mov esi,OFFSET buffer mov edi,OFFSET intArray ;//set addr, esi=buffer, edi=array mov eax,0 ;//init eax start: movzx edx,BYTE PTR[esi] cmp edx,0 ;//end of string je over cmp edx,32 ;//compare to space je stateB jmp stateA stateA: ;//is digit sub edx,48 ;//ascii edx-'0' mov ebx,edx ;//because mul use edx, back up edx mov ecx,10 mul ecx ;//eax=eax*10 mov edx,ebx add eax,edx inc esi jmp start stateB: ;//is space mov [edi],eax ;//把eax存進array裡 mov eax,0 add edi,4 inc esi inc len jmp start over: mov [edi],eax inc len 觀念很簡單 edx是Input String的位址，結果則是存在eax裡 每次從edx抓一個byte進來，判斷是1.數字 或2.空白 1.如果是數字就跳到 StateA，把eax原來的數字x10，然後加上新的數 2.如果是空白，代表一個整數結束，跳到StateB，將eax存進intArray裡，重新開始另一個循環直到edx讀到0，也就是字串的結尾為止。

計算陣列長度 list Byte 10,20,30,40 //list 是array的起始位址 ListSize = ($ - list) //ListSize是一個Constant //$代表Current Location counter list DWORD 1000,2000,3000 ListSize = ($-list)/4 //DWORD大小是4Byte，所以除以四 雙層迴圈 mov ecx,5 //外圈次數 L1: mov count,ecx mov ecx, 7 //內圈次數 L2: //do something here loop L2 mov ecx,count loop L1 if statement if (op1==op2){ statement1; } else {statement2; } cmp op1,op2 // op1==op2 je _true // jump if equal 相等的話就跳TRUE label jmp _false // 否則就無條件跳到FALSE label _true: //statement1 jmp next //跳過False部份 _false: //statement2 next: While loop while( var1>var2 ){ //statement } mov eax,var1 _while: cmp eax,var2 jle endwhile //jmp if less and equl //原本是var1>var2，條件成立就進while //這裡改成var1<=var2，條件成立就離開while //statement jmp _while _endwhile: for loop for(int i=0;i<9;i++){ statement; } mov ecx,0 //把ecx當作計數器i _for: cmp ecx,9 jge _endfor //jump if greater & equal //sta...

=解題提示= UVa官方論壇： 全世界UVa討論的集散地，當你題目解不出來時，第一件事就該來這裡搜尋該題目的討論串，通常會找到很多好心人提供的測資跟提示。 Methods to Solve 全世界最大的UVa解題提示網站，收錄的題目數量很多，品質也不錯。 Algorismist 這是一個關於演算法的維基網站，也有收錄 UVa 的解題提示，如果你有能力可以參與編輯條目，讓它變得更好。 UVa Toolkit 一般來講UVa題目頁上的範例測資都太簡單，聊勝於無。而 UVa Toolkit 這工具恰好補足了這方面的缺憾，你可以餵給它任何測資，並取得正確的對應輸出，對釐清題意很有幫助。 uHunt 非常非常好用的 UVa 解題工具網頁，可以很輕鬆的搜尋題目，安排自己解題的方向，瀏覽自己過去的解題紀錄等等。 =題目中譯= Lucky貓 著名的ACM題目中譯網，及解題提示。 Lucky貓Mirror站 同上，有難度提示。 ACM中譯 少量題目中譯。 ZeroJudge ZeroJudge是非常優秀的國產程式解題網，裡面有一區專門收錄UVa題目中譯。 =算法教學= DJWS的網路日誌 資源豐富的網站，整理了很多的算法教學，以及各種ACM競賽的資料。 C語言考古題 & C的解題 大量題目教學 Art of Programming Contest for uva 淺顯的ACM入門書，免費線上版。 NACOW 對岸關於程式設計與解題的wiki Infinite Loop 提供許多教學及ACM Tips, Sources。 =API Reference= Cplusplus.com 簡潔清楚的C/C++標準函式參考手冊，範例碼清楚實用，值得看看，我自己把這兒當後花園逛了。 =題目列表= ACM熱題排行榜 芭樂題排行榜，有哪些熱門題你還沒解過呢XD =討論論壇= NPSC補完計畫 針對NPSC的解題網站 OIBH 對岸關於資訊奧林匹亞競賽討論的論壇 algogeeks Google group about algorithms. =解題強者= 這部分網站就請各位審慎參觀了，大部分ACMer的程式碼都寫得不太好讀。 心如止水 350+題目解答，有基本的...

觀念 有修過OS應該都知道，因為執行IO動作會牽涉到interupt、system call 等等機制，花掉非常多的時間。所以對大部分的ACM題目來說，減少IO的次數是加速的好方法。 關鍵點 : 「減少IO次數」 Buffered Input: 不要用scnaf() 或者cin，用fgets一次讀進來，再parse字串。 Buffered Outout: 先用StringStream輸出至memory，最後再一次印出。 Buffered大小約在5000Byte左右，不要太小，也不要太大，導致Memory要做Swapping或paging。 其他小方法： 1. CPU通常會對4Bytes運算做最佳化(現在的32bit系統，應該也是對4Byte資料做運算最快)，所以處理資料盡量用4Bytes當一個單位。 2. 但是超過一定的資料量大小，通常長度超過十萬的陣列，那麼整個陣列的體積反而影響比較大，這時能用char, short 比較快。

本題重新寫過，請看這裡 [UVa] 101 The Blocks Problem @2009.11.12

本書作者之一賴名宗曾說過一句話，我覺得非常棒：「（學習） 什麼時候有了正確的觀念和目標，就什麼時候入門了。」那麼本書最大特點，就是建立正確物件導向觀念。 我早些年曾經在網路上看過一篇文章叫「 不要從程式語言學習物件導向 」，第一次讀時我看不懂。對我來說，物件導向不就是那些 class、new、public  等等的語法嗎？不從程式語言學還能從哪裡學呢？大多數坊間書籍只從「程式語法」的角度切入物件導向，受此影響的人（包括我）自然也曾經以為學會了 JAVA 就已經摸透物件導向了。 這個困惑直到我讀完了「世紀末軟體革命」後才稍微解開，物件導向之所以長青不倒的原因，是因為背後有一套組織程式的世界觀: 「程式是為了模擬世界」，「程式由物件組成，物件之間互相發送訊息」，而語法不過是實現整個思考架構的最末節。這樣來看，本書的撰寫順序「先OO，後C++」，這個次序才真的能抓到物件導向思考的脈絡。 本書從背景遠因─軟體危機的歷史背景開始，引出物件導向思想發芽，背後的理念精神「電腦運算的是為了模擬真實世界」，然後介紹比較完整的物件導向理論，最後，才以這樣的知識基礎下介紹C++ OOP。此時來看 C++ 的OO部份，眼光高度就有差異了，也可以知道C++並沒有完美的實踐所有的OO精神。 從思想起源再到程式實踐方法，一路娓娓道來，深入淺出，故事跟插圖很多，程式碼卻很少，架構起一個堅實又不艱澀的的地基。大學寫程式寫了四年，但是要問我何時真正開始瞭解物件導向？ 我會說從讀過這本書開始。 另外這本書給我的感動並不只單純在技術上，這三位作者寫書的時候，都還只有20歲，文字語氣中或多或少都還帶著 BBS 上的那種大學生的說話口吻，就像賀元說，他們當初寫書的動機，也只是看了一些好書想要把想法分享給大家而已，但是這本書暢銷到隔了十年還能再出「復刻版」，讓我思考，也許我自己能做的更多，年輕人就該帶有一些瘋狂的想法然後瘋狂的行動。 侯捷的二版序八個字道盡我心中的感覺 『鷹揚年少、氣吞牛斗』。 本書有一些小缺點，像涵蓋的議題很大，想要包山包海，結果貪多嚼不爛，有些細節就模糊帶過。作者之一賴明宗現在是PTT CSSE版主，可以去朝聖一下。

strlen( ) 不算'\0' ，但是會算'\n'。所以strlen("hello") 結果是5，strlen("hello\n") 結果是6。換行符號也算一個char，很容易被遺忘。 宣告string的時候，通常用的格式 char[MAXLINE+1]，最後那個1，就是拿來放字串的結尾'\0'的。 從stdin讀字串的方法: cin>>s; 讀一個單字，遇到空格or換行停止，空格or換行不會存進字串s。 cin.getline(s, length) 讀一行，遇到換行才停。 fgets(s, sizeof(s), stdin) 最後那個'\n'也會被包含在輸入字串裡。 cin.getline(s,length)則不會包含'\n'