轉站通知

本站已停止更新!!想繼續收看我的新文章的話,請前往我的新Blog - Chino's

2014年2月27日 星期四

UVa::10954 - Add All

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1895
簡單的題目。
加法,但是每加一次就會有個cost=目前總和,也就是要從現在最小的兩個數字開始一個一個加起來。

STEP5::Problem 0011 : Ch1-8.白之夢

http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0011
機率吧.....要找最大值,但是只能走一次,所以要猜他是不是最大的。

STEP5::Problem 0007 : Ch1-4.蘿莉的獎勵

http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0007
水題~~
排序,從最大開始,-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或是將最後的點移到前面,問最少步數。

STEP5::Problem 0004 : Ch1-1.一切的開始

http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0004
感覺有點DP的一題。要把所有I換成J,最少要幾步。

TOJ::22 / 檸檬汽水傳說

這題是NPSC初賽題,題目要問有哪幾個區間中間的所有數字都小於或等於兩邊。

2014年2月25日 星期二

STEP5::Problem 0012 : Ch2-1.言靈

http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0012
這題求n個數字中任意數字加起來為m的倍數。

STEP5::Problem 0005 : Ch1-2.梗賤橋

http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0005
這題題目要我們先換位置再判斷第m個木板是不是質數。

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),這樣的情況有兩種:

STEP5::Problem 0099 : こちら、ふたなり幸福安心委員会です。


http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0099
這題.....線段樹,尋找區間最小值。

STEP5::Problem 0087 : 中♂位♂數

http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0087
這題題目會讓你判斷一個亂序數列的中位數(你只知道第幾個但不知道數字),每次可以卻定A、B、C(任意三數)誰是這三數中的中位數。

STEP5::Problem 0021 : 背包問題

http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0021
一堆東西塞到兩個背包使其分別的平均值和最小。

TOJ::Matrix

題目是要求一段數字S, Bij=Si*Sj,矩陣B的任意子矩陣和有多少等於a。
觀察之後發現,某一個子矩陣的和等於他的邊(數列S)的乘積,有點類似(A+B)的平方之類的。

TOJ::倍數個數

求 A到B(A

TOJ::因數個數

先建根號N的質數表,然後再質因數分解求解,質因數分解時,只要是除到質數J大於根號A就可以了1,因為這樣A一定是質數,再輸出解的時候再多*2就好,如果是完全平方數或是某數的冪次,那A就會剩下1,這時直接輸出答案。


TOJ::GCD

就...最大公因數,輾轉相除法,遞迴寫法。

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為止,再讓下一節車廂進來。

TOJ::質數判斷

突然發現我對基礎的質數建表非常不熟悉,以下兩種方法,因為第二筆詢問數太多範圍又比較小,所以直接建表;第一筆則是建表到根號N,在用除法判斷,在篩質數時,要注意迴圈的範圍,其實這裡沒什麼大問題,就是如何簡化code和速度而已。


2014年2月21日 星期五

STEP5::Problem 0096 : 命運的猜測!

http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0096
互動題。
很簡單的2分搜~~

STEP5::Problem 0085 : 切木棒

http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0085.
我是用背包問題解這題。

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 0144 : Empty Stalls

http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0144
這題的解題關鍵就是---把英文學好..........

STEP5::Problem 0134 : 景點問題

http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0134
很有趣(?!)的題目。
只要找出LAC就可以了。第一次寫LAC所以寫得很難看。

STEP5::Problem 0138 : 土豪飯店

http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0138
題目是給定第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),為了方便我一次讀一行,抓完一次數字就把指標往回推一格。

2014年2月19日 星期三

STEP5::Problem 0120 : 蘿莉交換問題

http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0120
題目要交換兩行陣列中對應的數字,使得一陣列中數字不重複。
方法是先將兩個陣列並排排好,兩個兩個連起來,再把一樣的數字連起來,會連成很多環或是鍊,在任意一條上依序標上010101....

STEP5::Problem 0119 : 你這個幼女控

http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0119
其實應該不算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,還好有那個.....費馬小定理?!
a^{{p-1}}\equiv 1{\pmod  {p}},所以先把d、e都mod28就好了。
至於最後那個函式是快速輸入(對這題沒啥用,但是可以加快速度,宣告時前面應該要加inline)
code都是if海......

STEP5::Problem 0108 : 妹妹的遊戲

http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0108
這題是基礎的樹的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入,很方便~

STEP5::Problem 0106 : 2項式展開

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 : 轎夫

這題題目是有權無項圖,要求圖中兩點間的路徑最貴的那一條邊最便宜的值。
也就是找出MST,在用LCA找出兩點之間的路徑,答案就是這條路徑上最貴的那條邊。
用vecotor存好後,priority_queue找出MST,再找LCA,我用no[]紀錄祖先,H[]紀錄深度,coco[]紀錄權重