Art of Programming Contest for uva 第二章筆記
- 比賽中你必須具備三個能力 一、判斷題目適用哪一類算法。二、把算法實作成真正可跑的程式。三、能和隊友分工合作。
- "A good algorithm is like a sharp knife - it does exactly what it is supposed to do with a minimum amount of applied effort. Using the wrong algorithm to solve a problem is trying to cut a steak with a screwdriver: you may eventually get a digestible result, but you will expend considerable more effort than necessary, and the result is unlikely to be aesthetically pleasing."
- 比賽中，你得有本事快速判別問題的分類，並且決定要用哪種算法。
- 腦力激盪找出幾個解法，然後挑最笨最簡單的那個來做，能用暴力搜就暴力搜。
- Ad Hoc 題不屬於任何已知的算法分類，沒有通解可循，你必須見招拆招，但通常也是最有趣的題目。
- 不想超時，就得學會分析算法的時間複雜度。
- 關於算法，必須要學習的事:
- 證明算法正確 (特別是貪婪法) 。
- 時間與空間複雜度分析。
- 用替代法、遞迴樹、以及大師定理分析遞迴算法。
- 用機率知識來分析隨機算法。
- 攤平分析。
- 對於算法複雜度跟時間的有基本的概念，像n=1000000時，O(nlgn)算法大約會耗掉多少時間?
- 設計好測資的能力。基本測資、恰好在邊界條件上的測資、測試變數初始化的連續測資、一個數量極大的測資、狡猾的測資。
- 如果題目沒說，不要假設測資都會排得很整齊。插入不規則的空白或tab，讓它排的亂亂的看看。
- 養成寫程式的好習慣。
- Debug 訊息不要急著刪掉，先註解起來。
- Judges don't want to put easy problems on the contest, because they have thought up too many difficult problems.
常見題目分類
- Mathematics: Prime Number, Big Integer, Permutation, Number Theory, Factorial , Fibonacci , Sequences , Modulus
- Dynmic Programming : Longest Common Subsequence , Longest Increasing Subsequence , Edit Distance , 0/1 Knapsack , Coin Change , Matrix Chain Multiplication , Max Interval Sum
- Graph : Traversal , Flood Fill , Floyed Warshal , MST , Max Bipertite Matching , Network Flow , Aritculation Point
- Sorting : Bubble Sort , Quick Sort , Merge Sort (DAndC) , Selection Sort , Radix Sort , Bucket Sort
- Searching : Complete Search, Brute Force , Binary Search (DAndC) , BST
- Simulation : Josephus
- String Processing : String Matching , Pattern Matching
- Computational Geometry : Convex Hull
- AdHoc : Trivial Problems
0 意見:
張貼意見