111學測 交大資工 APCS組
規則：
每個人只有 7 分鐘 （ 自介 1 分鐘
然後 6 分時會敲門提醒
7 分時會直接開門
自介
大概一分鐘，其實不會計時
我自己練的大概都 1 分 10 ~ 20 秒
（ 就大概 1 分鐘就可以
教室配置
有 3 個教授 ( 離有點距離
配置大概長這樣：
然後有椅子可以坐
教授提問
全部都只有一個教授在問….
（ 聽學長＆其他人的消息應該是謝旻錚教授(那時候坐在最右邊)
Q1 : 我看到你的簡歷有 Github統計，其中的 PR 都是向哪些專案contribute ?
我回答的：
都是一些小型的專案，像是朋友的小作品，然後去修改一些小東西… （ 教授有點頭
我心裡想的：
那個Github統計的其實是真的沒有經歷可以放了，但是我想弄滿兩面好看的表格
有些 PR 是我自己在不同電腦打code要commit上去需要 merge 的時候的 ， 但是很像也一起算進去ㄌ ….
Q2 : 那你是如何準備APCS的 ?
主要還是刷題，就像是今天主要以動態規劃的題目做練習，明天針對圖論，後天針對其他主題之類的。
Q3 : 那在你練習過程中，最深刻的演算法是什麼？
應該是 Dijkstra 最短路徑演算法，因為這是感覺跟生活中最接近的演算法，可以實際運用。
Q3 : 那Dijkstra 演算法的概念？
主要是以 Greedy 的想法，搭配Priority_Queue優化的單點源最短路徑。
Q4 : Dijkstra 的限制？
有負環就不行
Q5 : 那有負邊可以嗎？
負邊也不行
Q6 : 你有實際寫過 Dijkstra 嗎？
有
Q7 : 用什麼寫的？
C++
（ 這邊 6 & 7 是接著問的，所以很短
Q8 :
現在有 3 個點： A、B、C （ 教授一邊比劃圖形 ），然後邊權都是 1 ，Dijkstra會怎麼處理？
( 如圖所示 )
會有一個Distance 數組紀錄到該點的最短距離，如果 當前的距離 + 連到Neighbor的邊權 < Neighbor的距離 的話就更新距離 ， 然後放入 PQ
（ 要表達這個情況： Dis [ neighbor] > Dis[ current] + Edge weight( current to neighbor) ）
（ 這邊我應該還要說預設為 INF 然後起點為 0 ）
Q9 :
如果現在多一個 a ——5—— c 的 edge 會有什麼影響？
( 如圖所示 )
Me :
那一樣檢查 C 附近有沒有可以更新的
如果有的話 一樣放進 PQ
Professor :
可是現在 PQ 裡面會有兩個存兩個 C 欸
Me : ？—？ （ 疑惑貌
Professor : （ 看的出我很疑惑
現在 PQ 裡面會有 ( 2,c ) 、 ( 5,c ) 這兩個 Pair ，那 PQ 會怎麼處理？
（ 我才懂教授的意思應該是 ： 直接在PQ 塞一個 ( 5,c ) 而不是建一個加上 a ——5—— c 的圖 )
Me : 那一樣會檢查可不可以更新Dis
如果 ： Dis [ neighbor] > Dis[ current] + edge 的話
就更新 Dis [ neighbor] 然後放進 PQ
不能的話就 POP 掉
Professor : 這樣 Dis 數組不是會壞掉？
我在想（ 為什麼會壞掉QQ ？
然後時間就差不多到ㄌ
反正這整段很鬼打牆…..
但我還是沒有很懂教授的點在哪
（ 看起來跟教授沒有同頻 ， 沒回答到教授覺得是答案或是問題關鍵點 …
（ 向其他人詢問後，教授指的「數組壞掉」可能是指要證明greedy的正確性？
心得
看起來應該是我覺得算是「作品」的東西不夠有料所以狂問程競
或是今年交大擺明就是要收程競？
真的從頭到尾都在問算法，然後就暴ㄌ
其他🆒🆒的事
是 @Sean 學長帶位去準備區 ！！
（ 資訊圈應該都知道學長 ， 不是資訊圈的應該也都看過學長ㄉ備審
本人很親切 可以聊天XD
（ 雖然我 11 點就到考場休息室然後認出他 ， 但是我到 1 點面試準備前才跟他講話 www
在我被叫到要去準備區的時候
@GTcoding 剛好傳訊息問我到了沒 （ 然後我在他對面LOL
休息室很冷，冷氣開超強（ 清大的超熱
（ 休息室 ）
面試完還有麵包餐盒可以拿
（ 超重的麵包餐盒 ）
如果是開車到校園的：
交大裡面很難停車
需要繞到最裡面靠近籃球場的地方才有車位