[閒聊] 程式大賽題目~

[chchwy (mat)]

都比完了
來交流一下解法吧

快樂的吳家瑋隊Source code
http://cssa.ntue.edu.tw/~chchwy/cs_contest.zip



1. 典型迴圈題

2. 找因數

3. 二進位跟十六進位換算

4. 找最小公倍數
   a * b = gcd(a,b) * lcm(a,b)

5. Max sub-matrix
   暴力法可解
   for (x1,y1) from (0,0) to (n,n)
      for(x2,y2) from (x1,y1) to (n,n)
         計算(x1,y1)~(x2,y2)的sub_Matrix總和

暴力法
http://chchwy.blogspot.com/2008/11/acm108-maximum-sum-te-version.html

DP高速解法
http://chchwy.blogspot.com/2008/11/acm108-maximum-sum-ac.html


6. Stack應用題，對100級來說難度應該是零

7. Convex Hull (凸包演算法)
http://www.geocities.com/kfzhouy/Hull.html
http://www.csie.ntnu.edu.tw/~u91029/ConvexHull.html


8. Maximum Consecutive Sum 的變化題
   將sum換成乘積即可。

   題目要求O(n)的解法，簡單講就是掃過一次sequence就必須找出解
   不能有兩層迴圈。

  http://www.csie.ntnu.edu.tw/~u91029/MaximumConsecutiveSum.html


9. Greedy解
   我想看看要怎麼寫比較簡潔清楚.....

10. no idea....?
    O(nlogn+I)....找資料中= ="



--

夜精小德 Char - 巨龍之喉 (前月神殿) PvP

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.45.138.11
※ 編輯: chchwy          來自: 114.45.138.11        (11/29 00:23)
※ 編輯: chchwy          來自: 114.45.138.11        (11/29 00:26)
推 jerry771210:有難度0這嚜誇張嗎XD王老大用來測試誰是自己寫的作業
推 daniel114:第四題 如果a=5 b=10 只要2片就可以拼成正方形
→ daniel114:好像不是 gcd(a,b) * lcm(a,b)
→ daniel114:還是我弄錯了?
→ chchwy:XD
※ 編輯: chchwy          來自: 114.45.138.11        (11/29 00:41)
※ 編輯: chchwy          來自: 114.45.138.11        (11/29 00:42)
→ chchwy:只是提一種算最小公倍數的方法
推 daniel114:哦哦
推 jerry771210:不是用短除法求到最後 最下面兩個數相乘?
推 jerry771210:不太懂為什麼是用gcd*lcm
推 jerry771210:哦  你是教我們怎嚜找LCM??了解
→ chchwy:樓上幹麻砍文啊=3=
→ muxiv: 哦  你是教我們怎嚜找 http://yofuk.com