NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » 一般 » 綜合討論區
 100台北市資訊學科能力競賽

作者 主題: 100台北市資訊學科能力競賽  (閱讀 2633 次)

lini

  • 高級會員
  • ****
  • 文章數: 101
    • 檢視個人資料
100台北市資訊學科能力競賽
« 於: 十一月 11, 2011, 05:23:09 pm »

今年是最後一年了呢 ... 有點感傷

Anyways ... 還是爆炸+粗心落到三等(6) ...

筆試成績不曉得 上機是64/100 (有16分是應該拿的)


第二題的那一筆42 應該是0
這筆測資出錯 毫無疑問 ...

稍微解釋一下各題 ...

第一題 : 手機特賣會
[解法] brute force

第二題 : 疊倍數
你有兩個正整數k(<10000) , d(<10)
題目要求找出最小的m 使得d的m位數(ex. 1的3位數=111)
成為k的倍數
[解法] 一位數一位數加上去並mod , 當然你也可以像我一樣笨笨的co大數除法 也是ok的

第三題 : 蛋白質序列比對
求LCS
[解法] LCS(Longest Common Sequence)

第四題 : 合法的著手
一個未完成的圍棋棋盤
請求出白棋 下一步可以下在哪些點
[解法] BFS(Breadth First Search)
1. 如果點上已經有棋子 顯然這個點不能下
2. 對這個點使用BFS 如果下了下去 不會被黑子圍住 則此點可行
3. 如果會被圍住 則對周圍的黑子再次進行BFS 如果可以吃掉任何一黑子 則此點也可行
4. 最後如果周圍的黑子都吃不掉 則此點不可行

第五題 : 128之謎
這題是防破台 ... 我不會 ...
題目給你一條序列 共k個數字(0<=an<=255 , 0<=k<=65535)
假設相鄰數字為x y
則相鄰數字可以合而為一 變成y^2-x
題目問 合併至最後(只剩一個數字) 是否能使之等於128
[解法] ->假
這題可能牽涉到數學
我那時候有考慮是否能做雙向BFS (Bi-BFS)
總之 測試資料很friendly
可以使用暴搜 隨便cut一下 可以抓到3筆測資 (早知道我應該這樣做 ><)
或許再配合使用Linked list  還可以抓更多 ?
可能需要一等獎的高手出來說明了 ...


20/20
12/20 (m>=500 輸出0 ... 眼脫沒看到等於 ...)
8/20 (好像陣列開太小 ... 感覺好像少打一個零 ... 囧)
20/20
4/20 (照順序合併 ... - -)
« 上次編輯: 十一月 11, 2011, 05:31:30 pm 由 lini »
記錄
+ NPSC補完計劃 » 一般 » 綜合討論區
 100台北市資訊學科能力競賽