本站遷移
因為我最近租用了網路空間以及網域,
故本站已遷移至新網站~
這邊的資訊已經正在進行搬移的工作~
希望各位可以到新網站去逛XD
New Website:
http://knightzone.org/
搜尋此網誌
2011年1月27日 星期四
[Zerojudge]a016: 數獨(SUDOKU)
這題就硬爆,檢查每個部分是否符合數獨的要求即可。
P.S. 我的程式碼中寫了一個奇怪的函式check()XD""
[C++](6ms, 674KB)
P.S. 我的程式碼中寫了一個奇怪的函式check()XD""
[C++](6ms, 674KB)
2011年1月22日 星期六
[UVa]574:Sum It Up
每個數有 有加或沒有加 兩種狀況,
直接利用遞迴把所有狀況都跑出來看看即可得解。
P.S.
為了避免印出重複的組合,
在你有把某數加進去的情況,
重複再找相同值的數是OK的;
但是若你已經不打算把這個數字加進去的時候,
記得要跳掉所有跟這個數相同值的數。
例.
今天你找到+2,
那麼你可以再繼續遞迴+2沒關係,
這樣不會重複。
除非你是已經打算不再找+2了,
那麼之後都不要讓遞迴再遞到+2。
[C](0.012)
直接利用遞迴把所有狀況都跑出來看看即可得解。
P.S.
為了避免印出重複的組合,
在你有把某數加進去的情況,
重複再找相同值的數是OK的;
但是若你已經不打算把這個數字加進去的時候,
記得要跳掉所有跟這個數相同值的數。
例.
今天你找到+2,
那麼你可以再繼續遞迴+2沒關係,
這樣不會重複。
除非你是已經打算不再找+2了,
那麼之後都不要讓遞迴再遞到+2。
[C](0.012)
[UVa]11121:Base -2
這題可以先將輸入的數字的絕對值換成2進位制,
例如:7 => 111、-7 => 111。
再來從小到大看看它由哪些2的幾次方組成,
如果該次方與輸入的數字同號時,換成base(-2)的時候,也一樣會有該次方;
如果該次方與輸入的數字不同號時,換成base(-2)的時候,就需要該次方與該次方+1兩個所組成。
例如:
7 = 111 有2^0、2^1、2^2。
2^0 -> (-2)^0 直接換過來即可。
2^1 -> ((-2)^1 + (-2)^2) 該次方+該次方的下一個次方即可組成。
2^2 -> (-2)^2 直接換過來即可。
加起來會有 1個(-2)^0,1個(-2)^1,2個(-2)^2,
2個(-2)^2要進位,但是對於base(-2)又得再利用(-2)^3+(-2)^4才能組起來,
所以答案就會是 11011 。
[C](0.044)
例如:7 => 111、-7 => 111。
再來從小到大看看它由哪些2的幾次方組成,
如果該次方與輸入的數字同號時,換成base(-2)的時候,也一樣會有該次方;
如果該次方與輸入的數字不同號時,換成base(-2)的時候,就需要該次方與該次方+1兩個所組成。
例如:
7 = 111 有2^0、2^1、2^2。
2^0 -> (-2)^0 直接換過來即可。
2^1 -> ((-2)^1 + (-2)^2) 該次方+該次方的下一個次方即可組成。
2^2 -> (-2)^2 直接換過來即可。
加起來會有 1個(-2)^0,1個(-2)^1,2個(-2)^2,
2個(-2)^2要進位,但是對於base(-2)又得再利用(-2)^3+(-2)^4才能組起來,
所以答案就會是 11011 。
[C](0.044)
2011年1月21日 星期五
[UVa]755:487--3279
先將每一種不同格式的電話號碼全部換成7位數整數,
利用一個hash紀錄每一種電話號碼的出現的次數,
將出現兩次以上的電話號碼紀錄到一個陣列裡面,
再利用quicksort將這個陣列以電話號碼來排序,
最後從頭將電話號碼及其出現的次數輸出來即可。
[C](0.420)
利用一個hash紀錄每一種電話號碼的出現的次數,
將出現兩次以上的電話號碼紀錄到一個陣列裡面,
再利用quicksort將這個陣列以電話號碼來排序,
最後從頭將電話號碼及其出現的次數輸出來即可。
[C](0.420)
[UVa]10699:Count the factors
直接從2開始到根號N去除除看能不能整除,
能整除就知道其質因數有此數,因此就把質因數個數加一,
接著把N中所有含有的這個質因數除乾淨,再往下一個搜尋。
[C++](0.012)
能整除就知道其質因數有此數,因此就把質因數個數加一,
接著把N中所有含有的這個質因數除乾淨,再往下一個搜尋。
[C++](0.012)
[UVa]541:Error Correction
檢查每行與每列的1的個數是否為偶數,
如果有某一行與某一列不吻合,
則要換的那個位元就是(那行,那列)。
如果有多行多列,或是行有問題但是列沒問題,或者反過來,
則都沒辦法判斷要換那個位元。
如果都吻合,那就OK,沒什麼問題。
[C](0.016)
如果有某一行與某一列不吻合,
則要換的那個位元就是(那行,那列)。
如果有多行多列,或是行有問題但是列沒問題,或者反過來,
則都沒辦法判斷要換那個位元。
如果都吻合,那就OK,沒什麼問題。
[C](0.016)
2011年1月20日 星期四
[UVa]10071:Back to High School Physics
這題只要套公式即可得解。
P.S. 因為是一等加速度,所以位移的公式就是 平均速度 * 經過的時間,
而因為正好是要兩倍時間後的位移,所以此時的速度即為平均速度,再乘上2倍時間即得解。
[C](0.028)
[C++](0.132)
P.S. 因為是一等加速度,所以位移的公式就是 平均速度 * 經過的時間,
而因為正好是要兩倍時間後的位移,所以此時的速度即為平均速度,再乘上2倍時間即得解。
[C](0.028)
[C++](0.132)
[UVa]10062:Tell me the frequencies!
這題的話,
我是先一個一個字看它的ASCII碼是多少,
把陣列中它的ASCII碼那格加1,
表示這個字多出現了一次。
我用了三個變數,
一個存最大出現的ASCII碼,
一個存最小出現的ASCII碼,
一個存最多出現的次數。
然後我就從出現一次開始搜尋,直到最多出現的次數,
每次搜尋都是從最大ASCII碼搜尋到最小ASCII碼這樣,
搜尋到次數一樣就輸出。
(當然這題用Sort也是OK啦XD)
[C](0.008)
我是先一個一個字看它的ASCII碼是多少,
把陣列中它的ASCII碼那格加1,
表示這個字多出現了一次。
我用了三個變數,
一個存最大出現的ASCII碼,
一個存最小出現的ASCII碼,
一個存最多出現的次數。
然後我就從出現一次開始搜尋,直到最多出現的次數,
每次搜尋都是從最大ASCII碼搜尋到最小ASCII碼這樣,
搜尋到次數一樣就輸出。
(當然這題用Sort也是OK啦XD)
[C](0.008)
2011年1月19日 星期三
[Zerojudge]d120: 10699 - Count the factors
直接從2開始到根號N去除除看能不能整除,
能整除就知道其質因數有此數,因此就把質因數個數加一,
接著把N中所有含有的這個質因數除乾淨,再往下一個搜尋。
[C++](8ms, 700KB)
能整除就知道其質因數有此數,因此就把質因數個數加一,
接著把N中所有含有的這個質因數除乾淨,再往下一個搜尋。
[C++](8ms, 700KB)
[Zerojudge]d095: 579 - ClockHands
先把時鐘刻劃360格,一格1度,
則再將時針指向的位置的度數去跟分針指向的位置的度數進行絕對值相減,
即可得解。
(若大於180度,就利用360去減其值的絕對值去把它減到小於180度為止)
P.S. 時針指的刻度算法: 小時*30(一個小時30度) + 分/60 * 30(因為分針走一圈,時針就走30度)
分針指的刻度算法: 分*6(五分鐘走30度,則一分鐘走6度)
[C++](12ms, 762KB)
則再將時針指向的位置的度數去跟分針指向的位置的度數進行絕對值相減,
即可得解。
(若大於180度,就利用360去減其值的絕對值去把它減到小於180度為止)
P.S. 時針指的刻度算法: 小時*30(一個小時30度) + 分/60 * 30(因為分針走一圈,時針就走30度)
分針指的刻度算法: 分*6(五分鐘走30度,則一分鐘走6度)
[C++](12ms, 762KB)
[Zerojudge]c067: Box of Bricks
先找出平均數,就可以知道後來每一堆積木的個數。
將每一堆大於平均數的積木,將其個數減去平均數的數字(也就意味這堆要搬多少個盒子到別堆去)加起來就是答案。
[C++](8ms, 702KB)
將每一堆大於平均數的積木,將其個數減去平均數的數字(也就意味這堆要搬多少個盒子到別堆去)加起來就是答案。
[C++](8ms, 702KB)
[Zerojudge]d226: 10071 - Back to High School Physics
這題只要套公式即可得解。
P.S. 因為是一等加速度,所以位移的公式就是 平均速度 * 經過的時間,
而因為正好是要兩倍時間後的位移,所以此時的速度即為平均速度,再乘上2倍時間即得解。
[C](2ms, 264KB)
[C++](12ms, 692KB)
P.S. 因為是一等加速度,所以位移的公式就是 平均速度 * 經過的時間,
而因為正好是要兩倍時間後的位移,所以此時的速度即為平均速度,再乘上2倍時間即得解。
[C](2ms, 264KB)
[C++](12ms, 692KB)
[Zerojudge]a017: 五則運算
利用stringstream將運算元及運算子以空白隔開,
並一一讀取。
讀到運算元就丟入運算元的堆疊中,
讀到運算子就丟入運算子的堆疊中,
並判斷上一個運算子的優先度是否大於等於它,
若是的話,就一直執行,直到遇到比它小的運算子才放進堆疊中。
唯'('和')'比較特別,
丟入堆疊時:
( > * = / = % > + > - > ),
判斷時:
* = / = % > + > - > ( 。
遇到')',要一直輸出,只要輸出到'(',就把'('消去,也不把自己')'存進堆疊中。
這樣做完即可得解。
[C++](6ms, 766KB)
並一一讀取。
讀到運算元就丟入運算元的堆疊中,
讀到運算子就丟入運算子的堆疊中,
並判斷上一個運算子的優先度是否大於等於它,
若是的話,就一直執行,直到遇到比它小的運算子才放進堆疊中。
唯'('和')'比較特別,
丟入堆疊時:
( > * = / = % > + > - > ),
判斷時:
* = / = % > + > - > ( 。
遇到')',要一直輸出,只要輸出到'(',就把'('消去,也不把自己')'存進堆疊中。
這樣做完即可得解。
[C++](6ms, 766KB)
2011年1月18日 星期二
[Zerojudge]a013: 羅馬數字
這題可分成兩個部分來做,
一個是把羅馬數字變成阿拉伯數字,
另外一個是把阿拉伯數字變成羅馬數字。
羅馬數字變成阿拉伯數字就是,
遇到其羅馬字母就將結果加上其代表數值,
再判斷它前一個字母是不是小於它,
如果是就減掉前面那個小於它的值的兩倍。
(因為你在前面執行到它的時候有加的它的值,所以不僅要把多的去掉,
還要把它原本減一次的意思表示出來,導致要扣兩倍。)
P.S. 根據羅馬數字的規則,會有這種狀況的只有:IV、IX、XL、XC、CD、CM。
而把阿拉伯數字變成羅馬數字就以
M、CM、D、CD、C、XC、L、XL、X、IX、V、IV、I
這個順序把大於它的值一直減掉,然後一直輸出,即可得解。
[C++](4ms, 740KB)
一個是把羅馬數字變成阿拉伯數字,
另外一個是把阿拉伯數字變成羅馬數字。
羅馬數字變成阿拉伯數字就是,
遇到其羅馬字母就將結果加上其代表數值,
再判斷它前一個字母是不是小於它,
如果是就減掉前面那個小於它的值的兩倍。
(因為你在前面執行到它的時候有加的它的值,所以不僅要把多的去掉,
還要把它原本減一次的意思表示出來,導致要扣兩倍。)
P.S. 根據羅馬數字的規則,會有這種狀況的只有:IV、IX、XL、XC、CD、CM。
而把阿拉伯數字變成羅馬數字就以
M、CM、D、CD、C、XC、L、XL、X、IX、V、IV、I
這個順序把大於它的值一直減掉,然後一直輸出,即可得解。
[C++](4ms, 740KB)
[Zerojudge]a012: Hashmat的戰役
這題只要將兩個數絕對值相減即可,
唯一的陷阱就是在於數值範圍,
剛好到2^32,就連unsigned int也會爆,
所以請用long long吧!
P.S. C語言的abs不太支援long long Orz...
[C](2ms, 272KB)
[C++](4ms, 696KB)
唯一的陷阱就是在於數值範圍,
剛好到2^32,就連unsigned int也會爆,
所以請用long long吧!
P.S. C語言的abs不太支援long long Orz...
[C](2ms, 272KB)
[C++](4ms, 696KB)
[Zerojudge]a010: 因數分解
直接從2開始搜尋到輸入的值的根號,
看看能不能整除,
能整除就一直除到不能,
做完後再看看輸入的值是否已經被除到只剩下1,
如果不是,一定只是一個大於輸入的值的根號的質數,將之輸出即可。
[C++](6ms, 700KB)
看看能不能整除,
能整除就一直除到不能,
做完後再看看輸入的值是否已經被除到只剩下1,
如果不是,一定只是一個大於輸入的值的根號的質數,將之輸出即可。
[C++](6ms, 700KB)
[Zerojudge]a009: 解碼器
利用ASCII碼找出Sample Input和Sample Output相差的k值,
將輸入的每個字都以此k值做加減即可得解。
P.S. k值為7
[C++](6ms, 730KB)
將輸入的每個字都以此k值做加減即可得解。
P.S. k值為7
[C++](6ms, 730KB)
[Zerojudge]a008: 中文大寫數字
初次想會覺得比較難,
因為條件會感覺很多。
實際上就是先把輸入的數字每一位數存放於陣列每一格中,
再用一個for從高位數開始跑到低位數,
然後去判斷跑到的數字:
1.如果是1~9,就輸出它的值跟它的單位。
2.如果是0,而且是在萬位和億位,只要輸出它的單位即可。
3.如果是0,而且不在萬位和億位,但是比它低一位數的地方有數字,就輸出"零"。
4.非以上狀況,不輸出。
[C++](2ms, 730KB)
因為條件會感覺很多。
實際上就是先把輸入的數字每一位數存放於陣列每一格中,
再用一個for從高位數開始跑到低位數,
然後去判斷跑到的數字:
1.如果是1~9,就輸出它的值跟它的單位。
2.如果是0,而且是在萬位和億位,只要輸出它的單位即可。
3.如果是0,而且不在萬位和億位,但是比它低一位數的地方有數字,就輸出"零"。
4.非以上狀況,不輸出。
[C++](2ms, 730KB)
[Zerojudge]d067: 文文的求婚--續集 (1 行版)
直接判斷是否為閏年即可,
每筆測資僅一行,不需用到無限輸入。
P.S. 閏年是能被4整除但不能被100整除的年份,以及能被400整除的年份。
[C++](4ms, 674KB)
每筆測資僅一行,不需用到無限輸入。
P.S. 閏年是能被4整除但不能被100整除的年份,以及能被400整除的年份。
[C++](4ms, 674KB)
[Zerojudge]a006: 一元二次方程式
公式解,即可得。
P.S. 公式:(-b+sqrt(b*b-4*a*c))/(2*a) 以及 (-b-sqrt(b*b-4*a*c))/(2*a)
[C++](5ms, 704KB)
P.S. 公式:(-b+sqrt(b*b-4*a*c))/(2*a) 以及 (-b-sqrt(b*b-4*a*c))/(2*a)
[C++](5ms, 704KB)
2011年1月11日 星期二
訂閱:
文章 (Atom)