http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0106
這題基本上是巴斯卡三角形,但是邊算邊跑一定TLE,所以先開一個陣列存起來。
STEP5::Problem 0098 : 刮鬍匹配
http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0098
這題很簡單,其實先把0放到stack裡,如果放了1進去,就看他上一個是不是0,是就一起拔掉,不是就繼續堆上去,輸出。
STEP5::Problem 0084 : 神秘題
http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0084
這題只要利用第一二組測資,照著傳再PO結果到題目提示的網站上,就會發現這題是歐拉函數(幹嘛不早講…….)。$\varphi (n)$歐拉函數是小於或等於n的正整數中與n互質的數的數目。
STEP5::Problem 0077 : 矩陣查詢
http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0077
這題是前綴和,第一次寫。
有使用到樹套樹,分別在C x1,y1 、x2+1,y2+1 的地方加上1,x1,y2+1 x2+1,y1 的地方加上-1,query就直接將左上到x,y的和%2就可以了。
STEP5::Problem 0149 : 轎夫
http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0149
這題題目是有權無項圖,要求圖中兩點間的路徑最貴的那一條邊最便宜的值。
也就是找出MST,在用LCA找出兩點之間的路徑,答案就是這條路徑上最貴的那條邊。
用vecotor存好後,priority_queue找出MST,再找LCA,我用no[]紀錄祖先,H[]紀錄深度,coco[]紀錄權重