http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1895
簡單的題目。
加法,但是每加一次就會有個cost=目前總和,也就是要從現在最小的兩個數字開始一個一個加起來。
2014年2月27日 星期四
STEP5::Problem 0007 : Ch1-4.蘿莉的獎勵
http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0007
水題~~
排序,從最大開始,-1-2-3..........直到等於0為止的前N項全部加起來輸出。
為了練習手co了heapㄏ.......
水題~~
排序,從最大開始,-1-2-3..........直到等於0為止的前N項全部加起來輸出。
為了練習手co了heapㄏ.......
2014年2月26日 星期三
STEP5::Problem 0006 : Ch1-3.陷阱
http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0006
不知道分哪類......。
題目是要讓1~任意點的區間和大於0,每次可以讓一個點+1或是將最後的點移到前面,問最少步數。
不知道分哪類......。
題目是要讓1~任意點的區間和大於0,每次可以讓一個點+1或是將最後的點移到前面,問最少步數。
2014年2月25日 星期二
STEP5::Problem 0129 : 驗算
http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0129
這題是矩陣乘法,但是直接乘一定會爆掉(n^3),所以要利用矩陣乘法的結合率(矩陣沒有交換率,但有結合率),先randen一個1*n的矩陣L,(A*L)*(B*L)=(C*L),這樣的情況有兩種:
這題是矩陣乘法,但是直接乘一定會爆掉(n^3),所以要利用矩陣乘法的結合率(矩陣沒有交換率,但有結合率),先randen一個1*n的矩陣L,(A*L)*(B*L)=(C*L),這樣的情況有兩種:
STEP5::Problem 0087 : 中♂位♂數
http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0087
這題題目會讓你判斷一個亂序數列的中位數(你只知道第幾個但不知道數字),每次可以卻定A、B、C(任意三數)誰是這三數中的中位數。
這題題目會讓你判斷一個亂序數列的中位數(你只知道第幾個但不知道數字),每次可以卻定A、B、C(任意三數)誰是這三數中的中位數。
2014年2月24日 星期一
2014年2月23日 星期日
UVa::514 - Rails
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=455
stack的應用,先讓一節車廂進來,比對看看出去的誰第一個出去,如果就是stack的TOP就POP掉,重複POP到出去的不是TOP為止,再讓下一節車廂進來。
stack的應用,先讓一節車廂進來,比對看看出去的誰第一個出去,如果就是stack的TOP就POP掉,重複POP到出去的不是TOP為止,再讓下一節車廂進來。
2014年2月21日 星期五
STEP5::Problem 0130 : 壓力好大
http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0130
這題是01背包問題的變形。先開一個寬度跟體力一樣陣列,每個元素初始成你銀行裡的錢,把任務依照賺的錢排序(得到-花費),然後 DP[i]=MAX(DP[i],DP[i-體力]+得到-花費)。
2014年2月20日 星期四
STEP5::Problem 0138 : 土豪飯店
http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0138
題目是給定第a天比第b天最多多c人。
可以將題目轉成有向有權圖。然後Dijkstra's就AC了。O(E log V)
題目是給定第a天比第b天最多多c人。
可以將題目轉成有向有權圖。然後Dijkstra's就AC了。O(E log V)
STEP5::Problem 0068 : Ch6-3.二三四問題
http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0068
單純字串處理,只是要注意數字尾巴直接接負號的情況(123-123),為了方便我一次讀一行,抓完一次數字就把指標往回推一格。
單純字串處理,只是要注意數字尾巴直接接負號的情況(123-123),為了方便我一次讀一行,抓完一次數字就把指標往回推一格。
2014年2月19日 星期三
STEP5::Problem 0120 : 蘿莉交換問題
http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0120
題目要交換兩行陣列中對應的數字,使得一陣列中數字不重複。
方法是先將兩個陣列並排排好,兩個兩個連起來,再把一樣的數字連起來,會連成很多環或是鍊,在任意一條上依序標上010101....
題目要交換兩行陣列中對應的數字,使得一陣列中數字不重複。
方法是先將兩個陣列並排排好,兩個兩個連起來,再把一樣的數字連起來,會連成很多環或是鍊,在任意一條上依序標上010101....
STEP5::Problem 0119 : 你這個幼女控
http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0119
其實應該不算DP,應該是遞迴吧。(分類太多會很煩...
總之,這題是8皇后問題。有人直接跑出全部的結果再一個一個比......雖然我覺得是好方法啦,可是我不會八皇后ㄏㄏ........
其實應該不算DP,應該是遞迴吧。(分類太多會很煩...
總之,這題是8皇后問題。有人直接跑出全部的結果再一個一個比......雖然我覺得是好方法啦,可是我不會八皇后ㄏㄏ........
STEP5::Problem 0110 : 你的法律事務所
http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0110
題目要求交換陣列上的數字或輸出。
兩個交換就直接換,整行或整列交換要用一組索引,交換索引而不是交換陣列本身。
題目要求交換陣列上的數字或輸出。
兩個交換就直接換,整行或整列交換要用一組索引,交換索引而不是交換陣列本身。
STEP5::Problem 0109 : 超高校級的密碼
http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0109
這題算是mod運算吧,將文字轉成數字後,在開d 、e次方,然後mod29。
因為d、e很大,一定會爆long long,還好有那個.....費馬小定理?!
,所以先把d、e都mod28就好了。
至於最後那個函式是快速輸入(對這題沒啥用,但是可以加快速度,宣告時前面應該要加inline)
code都是if海......
這題算是mod運算吧,將文字轉成數字後,在開d 、e次方,然後mod29。
因為d、e很大,一定會爆long long,還好有那個.....費馬小定理?!
,所以先把d、e都mod28就好了。
至於最後那個函式是快速輸入(對這題沒啥用,但是可以加快速度,宣告時前面應該要加inline)
code都是if海......
STEP5::Problem 0108 : 妹妹的遊戲
http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0108
這題是基礎的樹的BFS(其實本來想寫DFS.....),跑完後在回朔路徑並加總。
寫的很難看..........
這題是基礎的樹的BFS(其實本來想寫DFS.....),跑完後在回朔路徑並加總。
寫的很難看..........
STEP5::Problem 0107 : 魔法少女伊莉雅
http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0107
這題算是水題。我早期用C的code好醜........
注意r=0的情況,然後可以直接用 printf("%.6f\n",float); 輸出,他會自動4捨5入,很方便~
這題算是水題。我早期用C的code好醜........
注意r=0的情況,然後可以直接用 printf("%.6f\n",float); 輸出,他會自動4捨5入,很方便~
STEP5::Problem 0098 : 刮鬍匹配
http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0098
這題很簡單,其實先把0放到stack裡,如果放了1進去,就看他上一個是不是0,是就一起拔掉,不是就繼續堆上去,輸出。
這題很簡單,其實先把0放到stack裡,如果放了1進去,就看他上一個是不是0,是就一起拔掉,不是就繼續堆上去,輸出。
STEP5::Problem 0084 : 神秘題
http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0084
這題只要利用第一二組測資,照著傳再PO結果到題目提示的網站上,就會發現這題是歐拉函數(幹嘛不早講.......)。歐拉函數是小於或等於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就可以了。
這題是前綴和,第一次寫。
有使用到樹套樹,分別在C x1,y1 、x2+1,y2+1 的地方加上1,x1,y2+1 x2+1,y1 的地方加上-1,query就直接將左上到x,y的和%2就可以了。
STEP5::Problem 0149 : 轎夫
這題題目是有權無項圖,要求圖中兩點間的路徑最貴的那一條邊最便宜的值。
也就是找出MST,在用LCA找出兩點之間的路徑,答案就是這條路徑上最貴的那條邊。
用vecotor存好後,priority_queue找出MST,再找LCA,我用no[]紀錄祖先,H[]紀錄深度,coco[]紀錄權重
也就是找出MST,在用LCA找出兩點之間的路徑,答案就是這條路徑上最貴的那條邊。
用vecotor存好後,priority_queue找出MST,再找LCA,我用no[]紀錄祖先,H[]紀錄深度,coco[]紀錄權重
訂閱:
文章 (Atom)