這真是一道很無言的水題
由於p值最多到100位，double可以存下1.7*10^3XX這麼多(精度16位多)
所以直接開cmath....(ry)
2011年12月31日 星期六
PKU1739-Tony's Tour
題目：http://poj.org/problem?id=1739
給一張大小N*M的地圖(最多8*8)，上面有一些道路【.】和障礙物【#】
Tony想從農場(最左下角格)走到市場(最右下角格)，並且經過所有可以走的格子
試問有幾種不一樣的走法？
類似的問題是USACO Training544 Betsy's Tour，附上翻譯網連結參考：
http://www.nocow.cn/index.php/Translate:USACO/betsy
給一張大小N*M的地圖(最多8*8)，上面有一些道路【.】和障礙物【#】
Tony想從農場(最左下角格)走到市場(最右下角格)，並且經過所有可以走的格子
試問有幾種不一樣的走法？
類似的問題是USACO Training544 Betsy's Tour，附上翻譯網連結參考：
http://www.nocow.cn/index.php/Translate:USACO/betsy
2011年12月29日 星期四
【筆記】名題精選百則-心得
我非常喜歡這本書、可惜google網上少有對這本書的討論
從高中資訊競賽的角度來說，這可能不是一本最有效率的書
(畢竟沒有專章講解DP、圖論這些)
但是從寫程式的角度，不管以後走學術研究、軟體設計，這本書具有很棒的全面性
最難能可貴的是這本書不只是收集題目、提供答案，
更有一種把讀者當成學生、循循善誘、悉心引導的品質
提示我們觀察的角度、如何從樸素做法進階到有效的作法等等
而每題解答後附上的習題，多可分為三類：
A.對題解算法的精髓作檢討：例如原題從正整數改成整數是否成立？圓形能不能推廣到橢圓形？
B.提出原題的特例：例如當所求集合不存在時
C.提出對原題擴展的問題：例如印出所有解、改變部分題設
我想，如果今後期許自己作完一道問題能問出這三種問題、也就看得更高更遠了吧！
--
筆記一些在競賽中出現的名題(多是DP、貪心)
16.連續整數的固定和：NPSC變形(電腦出租公司)
22.整數的所有不同分割數目：PKU上某DP題
34.最大方塊區域：經典DP、IOI2008噁心變形
49.包含在其他區間中間的區間：各種區間時間類貪心的始祖
57.最長共同部分序列：經典DP、今年北市賽出了要求一模一樣的題目
66.找零錢問題、67.背包問題、86.最大連續元素和：經典DP
68.最佳矩陣相乘順序：北市賽出了類似形狀的DP
69.最短路徑問題、77.環遊世界、78.一筆畫：經典圖論
71.穩定伴侶問題：貪心，校內賽考了一樣的
92.最長遞增部分序列：經典DP，USACO Training有一道求LIS總數的變形
從高中資訊競賽的角度來說，這可能不是一本最有效率的書
(畢竟沒有專章講解DP、圖論這些)
但是從寫程式的角度，不管以後走學術研究、軟體設計，這本書具有很棒的全面性
最難能可貴的是這本書不只是收集題目、提供答案，
更有一種把讀者當成學生、循循善誘、悉心引導的品質
提示我們觀察的角度、如何從樸素做法進階到有效的作法等等
而每題解答後附上的習題，多可分為三類：
A.對題解算法的精髓作檢討：例如原題從正整數改成整數是否成立？圓形能不能推廣到橢圓形？
B.提出原題的特例：例如當所求集合不存在時
C.提出對原題擴展的問題：例如印出所有解、改變部分題設
我想，如果今後期許自己作完一道問題能問出這三種問題、也就看得更高更遠了吧！
--
筆記一些在競賽中出現的名題(多是DP、貪心)
16.連續整數的固定和：NPSC變形(電腦出租公司)
22.整數的所有不同分割數目：PKU上某DP題
34.最大方塊區域：經典DP、IOI2008噁心變形
49.包含在其他區間中間的區間：各種區間時間類貪心的始祖
57.最長共同部分序列：經典DP、今年北市賽出了要求一模一樣的題目
66.找零錢問題、67.背包問題、86.最大連續元素和：經典DP
68.最佳矩陣相乘順序：北市賽出了類似形狀的DP
69.最短路徑問題、77.環遊世界、78.一筆畫：經典圖論
71.穩定伴侶問題：貪心，校內賽考了一樣的
92.最長遞增部分序列：經典DP，USACO Training有一道求LIS總數的變形
【筆記】名題精選百則-題意整理
名題精選百則，實有107組題目敘述/參考答案
不過如果嚴格地去除重複的部分應該是92道問題
(例如「列出所有子集」、「列出所有子集－字典順序」是一道問題，
「奇數階魔方陣」、「單偶數階魔方陣」、「雙偶數階魔方陣」也視為一樣的問題)
為求督促自己理解之效
這裡將所有題目的「題意」整理後，茲列表如下：
不過如果嚴格地去除重複的部分應該是92道問題
(例如「列出所有子集」、「列出所有子集－字典順序」是一道問題，
「奇數階魔方陣」、「單偶數階魔方陣」、「雙偶數階魔方陣」也視為一樣的問題)
為求督促自己理解之效
這裡將所有題目的「題意」整理後，茲列表如下：
2011年12月26日 星期一
COCI-2011/2012#3-6-Traka
題目PDF：http://www.hsin.hr/coci/contest3_tasks.pdf
比賽官網、測資：http://www.hsin.hr/coci/
(克羅埃西亞文Traka -> 英文Tape)
有N個工人組成的生產線，以及要進行的M樣工作(N,M到100000)
每位工人負責的崗位都有複雜度T[i]
每樣工作也有相應的複雜度F[j]
工人i進行工作j需要花T[i]*F[j]的時間(T和F是1...10000的正整數)
現在這個公司有個規定，工人一旦完成工作
一定要立刻交給下一個人並且要馬上開工！
萬一此時下一個人手邊還有工作沒作完，老闆就會爆炸，把全部的員工都火掉
這時候身為工人1號的Mirko有個重要的責任
他可以透過適當的等待一些秒數再工作，來避免相撞(也只有他有權這麼做)
例如下面這條範例測資它會在時刻0開始工作1、時刻4結束、(等待1秒)、時刻5開始工作2...
問最少要花多少時間這N個人依序將M樣工作做完
3 3
2
1
1
2
1
1
答案是11
比賽官網、測資：http://www.hsin.hr/coci/
(克羅埃西亞文Traka -> 英文Tape)
有N個工人組成的生產線，以及要進行的M樣工作(N,M到100000)
每位工人負責的崗位都有複雜度T[i]
每樣工作也有相應的複雜度F[j]
工人i進行工作j需要花T[i]*F[j]的時間(T和F是1...10000的正整數)
現在這個公司有個規定，工人一旦完成工作
一定要立刻交給下一個人並且要馬上開工！
萬一此時下一個人手邊還有工作沒作完，老闆就會爆炸，把全部的員工都火掉
這時候身為工人1號的Mirko有個重要的責任
他可以透過適當的等待一些秒數再工作，來避免相撞(也只有他有權這麼做)
例如下面這條範例測資它會在時刻0開始工作1、時刻4結束、(等待1秒)、時刻5開始工作2...
問最少要花多少時間這N個人依序將M樣工作做完
3 3
2
1
1
2
1
1
答案是11
2011年12月23日 星期五
2011年12月20日 星期二
HOJ15-搬家
題目：http://hoj.mooo.com/judge/index.php/problem/view/15
原題：http://poj.org/problem?id=1734
n個點(n<=100)構成的無向圖，
求權值最小環的權重(兩個點來回不算，所以至少要有三個點)
CEOI 1999 Trip，原題是必須輸出這個環經過的結點
程式碼(求權重)：http://codepad.org/1JTXeH6U
(解題報告待補)
原題：http://poj.org/problem?id=1734
n個點(n<=100)構成的無向圖，
求權值最小環的權重(兩個點來回不算，所以至少要有三個點)
CEOI 1999 Trip，原題是必須輸出這個環經過的結點
程式碼(求權重)：http://codepad.org/1JTXeH6U
(解題報告待補)
2011年12月16日 星期五
PKU3254-Corn Fields
題目：http://poj.org/problem?id=3254
現在FJ有個N*M格的原野想要放牧，有些格子可以放牛、有些格子不能放牛
(最大12*12)
並且，上下或左右相鄰的兩個格子不能同時放牧
請問總共有多少種不同的放牧方法呢？(全部不放也是一種方法)
現在FJ有個N*M格的原野想要放牧，有些格子可以放牛、有些格子不能放牛
(最大12*12)
並且，上下或左右相鄰的兩個格子不能同時放牧
請問總共有多少種不同的放牧方法呢？(全部不放也是一種方法)
2011年12月14日 星期三
PKU2136-Vertical Histogram
統計文章中A...Z出現的次數，並且輸出成漂亮的長條圖形
注意行尾空白
我個人是多存一個變數記錄"目前積欠幾個空格"，當需要輸出星號才一口氣補空格
注意行尾空白
我個人是多存一個變數記錄"目前積欠幾個空格"，當需要輸出星號才一口氣補空格
PKU2406-Power Strings
題目：http://poj.org/problem?id=2406
(這真是一道傻人有傻福的題目…)
定義字串的冪次例如s^n就是把字串s拼接n次
例如"abc"^3 就是"abcabcabc"
給定一個字串S，試著把它還原成s^n的形式，問最大可行的n是多少？
(長度最多1000000)
(這真是一道傻人有傻福的題目…)
定義字串的冪次例如s^n就是把字串s拼接n次
例如"abc"^3 就是"abcabcabc"
給定一個字串S，試著把它還原成s^n的形式，問最大可行的n是多少？
(長度最多1000000)
PKU1401-Factorial
題目：http://poj.org/problem?id=1401
(經典問題)
給一正整數N介於1...1000000000，問N!尾綴連續有幾個0呢？
好比說15!=1307674368000，答案就是3
(經典問題)
給一正整數N介於1...1000000000，問N!尾綴連續有幾個0呢？
好比說15!=1307674368000，答案就是3
PKU1014-Dividing
題目：http://poj.org/problem?id=1014
有總計不超過20000顆大理石，價值1的有a1顆、價值2的有a2顆…一直到價值6
每顆大理石都不能分割，
問是否存在一種方案能把石頭平分給兩人，使其總價值相等？
有總計不超過20000顆大理石，價值1的有a1顆、價值2的有a2顆…一直到價值6
每顆大理石都不能分割，
問是否存在一種方案能把石頭平分給兩人，使其總價值相等？
PKU2081-Recaman's Sequence
如果直接按照定義來建表的話，每次檢查是否和前面重複需要O(n)
作n個這樣的數列就得O(n^2)，會超時
既然只是簡單的檢查重複、只要支援插入，
那麼hash每次O(1)顯然是很好的選擇 (discuss有人給出了這題最大的答案...)
不過類似的功能用std::map來實作O(nlgn)也是能達到通過的標準
(其實這應該有數學規律可找...)
作n個這樣的數列就得O(n^2)，會超時
既然只是簡單的檢查重複、只要支援插入，
那麼hash每次O(1)顯然是很好的選擇 (discuss有人給出了這題最大的答案...)
不過類似的功能用std::map來實作O(nlgn)也是能達到通過的標準
(其實這應該有數學規律可找...)
NPSC2011-高中組決賽-pF-田忌賽馬
題目：(官方網站似乎尚未公布…這裡憑比賽印象打出來)
現在有三條數列a、b、c，都恰有n項
(其中a,c可以1~10億，b可以0~100，n沒記錯應該有100000左右)
問要取最小的m(最少的訓練天數)能滿足
對於至少k對不同的i,j，存在a[i]+m*b[i]>c[j]
(也就是訓練m天馬的力量>對手馬的力量，勝k場)
現在有三條數列a、b、c，都恰有n項
(其中a,c可以1~10億，b可以0~100，n沒記錯應該有100000左右)
問要取最小的m(最少的訓練天數)能滿足
對於至少k對不同的i,j，存在a[i]+m*b[i]>c[j]
(也就是訓練m天馬的力量>對手馬的力量，勝k場)
2011年12月5日 星期一
PKU2739-Sum of Consecutive Prime Numbers
題目：http://poj.org/problem?id=2739
問一個正整數n(2...10000)存在多少種方法可以表示成一段連續質數和
程式碼：http://codepad.org/4T2fx0wJ
作法和2140的「連續正整數」異曲同工，解題報告請參考：
http://nphard001.blogspot.com/2011/12/pku2140-herd-sums.html
(順帶一件有趣的事情，Discuss中打表AC的表裡看來答案不外乎是0,1,2,3這四種…？)
問一個正整數n(2...10000)存在多少種方法可以表示成一段連續質數和
程式碼：http://codepad.org/4T2fx0wJ
作法和2140的「連續正整數」異曲同工，解題報告請參考：
http://nphard001.blogspot.com/2011/12/pku2140-herd-sums.html
(順帶一件有趣的事情，Discuss中打表AC的表裡看來答案不外乎是0,1,2,3這四種…？)
PKU1013-Counterfeit Dollar
題目：http://poj.org/problem?id=1013
經典問題，有12個銀幣，已知其中一個是假的(重量可能比較重或輕)
現在利用天秤來判斷哪一個是假幣
給出Sally Jones已經秤三次的結果，「保證有且有一組解」
問哪一個是假幣，比真幣輕或重
經典問題，有12個銀幣，已知其中一個是假的(重量可能比較重或輕)
現在利用天秤來判斷哪一個是假幣
給出Sally Jones已經秤三次的結果，「保證有且有一組解」
問哪一個是假幣，比真幣輕或重
PKU1519-Digital Roots
題目：http://poj.org/problem?id=1519
將一個數字各個位數加總
如果總和不是一位數(大於9)，那麼再作一次各數字加總…
直到一位數，是為Digital Root
對給出的n問它的Digital Root是多少
將一個數字各個位數加總
如果總和不是一位數(大於9)，那麼再作一次各數字加總…
直到一位數，是為Digital Root
對給出的n問它的Digital Root是多少
PKU2140-Herd Sums
題目：http://poj.org/problem?id=2140
給一正整數n(最多一千萬)
問有多少種i,j (1<=i<=j<=n)可以達成sigma(k=i...j) k = n
例如15可以是15, 7+8, 4+5+6, 1+2+3+4+5這四種方法
對了，原來Farmer John大學主修數學(炸)
給一正整數n(最多一千萬)
問有多少種i,j (1<=i<=j<=n)可以達成sigma(k=i...j) k = n
例如15可以是15, 7+8, 4+5+6, 1+2+3+4+5這四種方法
對了，原來Farmer John大學主修數學(炸)
PKU2247-Humble Numbers
題目：http://poj.org/problem?id=2247
程式碼：http://codepad.org/6UuS8cWg
和PKU1338-Ugly Numbers幾乎相同，解題報告參考：
http://nphard001.blogspot.com/2011/12/pku1338-ugly-numbers.html
唯獨需要特別注意1st,2nd,3rd,11th,211th,...這件事情(可以參考程式碼)
程式碼：http://codepad.org/6UuS8cWg
和PKU1338-Ugly Numbers幾乎相同，解題報告參考：
http://nphard001.blogspot.com/2011/12/pku1338-ugly-numbers.html
唯獨需要特別注意1st,2nd,3rd,11th,211th,...這件事情(可以參考程式碼)
PKU1338-Ugly Numbers
題目：http://poj.org/problem?id=1338
所謂的Ugly Number就是那些質因數隻包含2,3,5的數
另外，1也算Ugly Number
多比詢問第n小的Ugly Number是多少？(1<=n<=1500)
(和2247幾乎一樣...只不過改成2,3,5,7)
所謂的Ugly Number就是那些質因數隻包含2,3,5的數
另外，1也算Ugly Number
多比詢問第n小的Ugly Number是多少？(1<=n<=1500)
(和2247幾乎一樣...只不過改成2,3,5,7)
PKU1887-Testing the CATCHER
題目：http://poj.org/problem?id=1887
程式碼：http://codepad.org/tdrfRdei
和2533都是求LIS的問題(其實最長遞減應該是LDS…？)
解題報告請參考：
http://nphard001.blogspot.com/2011/12/pku2533-longest-ordered-subsequence.html
程式碼：http://codepad.org/tdrfRdei
和2533都是求LIS的問題(其實最長遞減應該是LDS…？)
解題報告請參考：
http://nphard001.blogspot.com/2011/12/pku2533-longest-ordered-subsequence.html
2011年12月3日 星期六
2011年12月2日 星期五
PKU1008-Maya Calendar
題目：http://poj.org/problem?id=1008
相當有意思的模擬題，有關曆法轉換
利用時間戳記的觀念(在這裡兩曆法的共同語言是距第一天過了幾天)
貼上程式碼提供參考
程式碼：http://codepad.org/xS4D4ORH
相當有意思的模擬題，有關曆法轉換
利用時間戳記的觀念(在這裡兩曆法的共同語言是距第一天過了幾天)
貼上程式碼提供參考
程式碼：http://codepad.org/xS4D4ORH
PKU1316-Self Numbers
定義d(n)=n+(n所有位數和)，ex: d(75)=75+7+5、d(123)=123+1+2+3
129能透過d(123)造出來
但像31這樣的數就無法通過這個函數造出來，是為self-number
請輸出所有1...10000的self-number
水題，倒是讓我想到和USACO-Training-3.1的humble頗異曲同工
129能透過d(123)造出來
但像31這樣的數就無法通過這個函數造出來，是為self-number
請輸出所有1...10000的self-number
水題，倒是讓我想到和USACO-Training-3.1的humble頗異曲同工
PKU1458-Common Subsequence
LCS問題
"The input data are correct." 是整個題目最fishy的地方
看了discuss哀鴻遍野之後我很榮幸第一次上傳就AC了這題可怕的輸入…
"The input data are correct." 是整個題目最fishy的地方
看了discuss哀鴻遍野之後我很榮幸第一次上傳就AC了這題可怕的輸入…
PKU1936-All in All
題目：http://poj.org/problem?id=1936
給兩個字串a,b
問a是不是b的子序列
原則上是能秒的題目，但是名題百選有給出這個問題好玩的變化版本
因此我想等手邊有書再補述這題XD
(未完)
給兩個字串a,b
問a是不是b的子序列
原則上是能秒的題目，但是名題百選有給出這個問題好玩的變化版本
因此我想等手邊有書再補述這題XD
(未完)
PKU2262-Goldbach's Conjecture
哥德巴赫猜想。
n只到100萬，把質數表建出來
每個n都從小到大枚舉a，只要n-a也是質數就輸出、結束
是我錯覺吧...UVA似乎也有一模一樣的題目...？
n只到100萬，把質數表建出來
每個n都從小到大枚舉a，只要n-a也是質數就輸出、結束
是我錯覺吧...UVA似乎也有一模一樣的題目...？
PKU2000-Gold Coins
第一天有1塊錢，接下來兩天每天2塊錢、三天每天三塊、d天每天d塊...
問到第n天的時候總共拿了多少錢
實際上，n只到10000、連公式都不必推直接模擬打表輸出就行了囧
(相當空虛的一道題…)
問到第n天的時候總共拿了多少錢
實際上，n只到10000、連公式都不必推直接模擬打表輸出就行了囧
(相當空虛的一道題…)
2011年12月1日 星期四
PKU1218-THE DRUNK JAILER
題目：http://poj.org/problem?id=1218
給定一個正整數n(5<=n<=100)
現在獄卒喝醉了他會做n輪以下的事情：
第1輪，喝一點威士忌，把編號1,2,3,4,...的牢房打開
第2輪，喝一點威士忌，把編號2,4,6,8,...的牢房關起來
第3輪把3,6,9,12...的牢房開的關起來、關的打開
直到第n輪結束以後，獄卒就會暴斃，
然後牢房是開著的犯人就會趁機逃出來
問對每個n會有幾個犯人逃出來
給定一個正整數n(5<=n<=100)
現在獄卒喝醉了他會做n輪以下的事情：
第1輪，喝一點威士忌，把編號1,2,3,4,...的牢房打開
第2輪，喝一點威士忌，把編號2,4,6,8,...的牢房關起來
第3輪把3,6,9,12...的牢房開的關起來、關的打開
直到第n輪結束以後，獄卒就會暴斃，
然後牢房是開著的犯人就會趁機逃出來
問對每個n會有幾個犯人逃出來
PKU1207-The 3n + 1 problem
題目：http://poj.org/problem?id=1207
給一正整數n，如果n=1就結束，n是奇數就3n+1，偶數就減半
原則上n<1000000的時候都會回到1
例如n=22會有過程：22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
共16個數字，即長度16
問介於整數p和q之間這種3n+1鍊最長的鍊是多長
給一正整數n，如果n=1就結束，n是奇數就3n+1，偶數就減半
原則上n<1000000的時候都會回到1
例如n=22會有過程：22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
共16個數字，即長度16
問介於整數p和q之間這種3n+1鍊最長的鍊是多長
2011年11月30日 星期三
PKU1001-Exponentiation
題目：http://poj.org/problem?id=1001
給一個實數R，求出R^n確切的值
瞄了一下discuss發現原來這題的實際測試資料與題目設定不符(推測應該是題意不清)
R並不會<99.999，實際上意思R的位數最多"6格"，整數的話<=999999，小數會<=9999.9
(如何能知道測試資沒照題目出？
其實只要利用已經AC的code，
稍加修改加入「如果測資超出範圍，隨便輸出或無窮迴圈」這類的code
如果還是AC表示有乖乖照範圍、WA或TLE了測資就真的有問題了)
給一個實數R，求出R^n確切的值
瞄了一下discuss發現原來這題的實際測試資料與題目設定不符(推測應該是題意不清)
R並不會<99.999，實際上意思R的位數最多"6格"，整數的話<=999999，小數會<=9999.9
(如何能知道測試資沒照題目出？
其實只要利用已經AC的code，
稍加修改加入「如果測資超出範圍，隨便輸出或無窮迴圈」這類的code
如果還是AC表示有乖乖照範圍、WA或TLE了測資就真的有問題了)
提問與動機
上google輸入「如何 孩子 聰明」有82,200,000項結果
如果把聰明換成信心的話，結果剩31,100,000項，
可見現在父母還是覺得聰明比較重要(誤)
最近回想起為什麼會喜歡程式解題，結論很有意思
如果把聰明換成信心的話，結果剩31,100,000項，
可見現在父母還是覺得聰明比較重要(誤)
最近回想起為什麼會喜歡程式解題，結論很有意思
ZJb242-檸檬汽水傳說
題目：http://zerojudge.tw/ShowProblem?problemid=b242
給一非負整數序列a1,a2,...,an (n<1000000)
問有多少數對(i,j)滿足
A : 1<=i<j<=n
B : 對所有的i<k<j，滿足ai>=ak且aj>=ak (換句話說，ai和aj必須是[i,j]序列中最大的兩個數)
例如：5 3 1 3 5
滿足的數對有(1,2)(1,4)(1,5)(2,3)(2,4)(2,5)(3,4)(4,5)共八對
給一非負整數序列a1,a2,...,an (n<1000000)
問有多少數對(i,j)滿足
A : 1<=i<j<=n
B : 對所有的i<k<j，滿足ai>=ak且aj>=ak (換句話說，ai和aj必須是[i,j]序列中最大的兩個數)
例如：5 3 1 3 5
滿足的數對有(1,2)(1,4)(1,5)(2,3)(2,4)(2,5)(3,4)(4,5)共八對
2011年11月29日 星期二
PKU1002-487-3279
題目：http://poj.org/problem?id=1002
是相當平易近人的模擬題，就不防雷直接貼程式碼了
字典序輸出完全靠威能map<string,int>解決:p
程式碼：http://codepad.org/6v0AEX4G
是相當平易近人的模擬題，就不防雷直接貼程式碼了
字典序輸出完全靠威能map<string,int>解決:p
程式碼：http://codepad.org/6v0AEX4G
PKU3176-Cow Bowling
和PKU1163一模一樣，解題報告請參考：
http://nphard001.blogspot.com/2011/11/pku1163-triangle.html
只要把程式碼存陣列的範圍100改到350就能AC了
http://nphard001.blogspot.com/2011/11/pku1163-triangle.html
只要把程式碼存陣列的範圍100改到350就能AC了
PKU1163-The Triangle
題目：http://poj.org/problem?id=1163
從三角塔最頂端走、每次可以走左或走右，讓路線上數字總和最高
是IOI1994年的題目
和pku3176題意一模一樣，只不過是USACO2005銅組、範圍到350
從三角塔最頂端走、每次可以走左或走右，讓路線上數字總和最高
是IOI1994年的題目
和pku3176題意一模一樣，只不過是USACO2005銅組、範圍到350
PKU1607-Deck
題目：http://poj.org/problem?id=1607
解題報告請參考pku1003，這篇純粹記錄：
http://nphard001.blogspot.com/2011/11/pku1003-hangover.html
解題報告請參考pku1003，這篇純粹記錄：
http://nphard001.blogspot.com/2011/11/pku1003-hangover.html
PKU1003-Hangover
題目：http://poj.org/problem?id=1003
是物理學重心的時候經典的疊方塊問題，設方塊長為1
對給定想造成的位移總和，問最少要幾塊方塊才能疊出來
和PKU1607-Deck相類似、解題報告放一起
是物理學重心的時候經典的疊方塊問題，設方塊長為1
對給定想造成的位移總和，問最少要幾塊方塊才能疊出來
和PKU1607-Deck相類似、解題報告放一起
PKU1004-Financial Management
題目：http://poj.org/problem?id=1004
給12個小數，輸出他們的平均值
程式碼：http://codepad.org/Whigm5fU
神奇的WA掉一次
後來看了Discuss才是神奇的開始
原來選G++就等於沒辦法用printf("%lf");！
太神奇了
於是把Language換成C++就AC
真是寫水題長知識
給12個小數，輸出他們的平均值
程式碼：http://codepad.org/Whigm5fU
神奇的WA掉一次
後來看了Discuss才是神奇的開始
原來選G++就等於沒辦法用printf("%lf");！
太神奇了
於是把Language換成C++就AC
真是寫水題長知識
2011年11月25日 星期五
ZJb239-電腦出租公司
題目：http://zerojudge.tw/ShowProblem?problemid=b239
測試資料(高中組初賽裁判測資)：http://contest.cc.ntu.edu.tw/npsc2009/schedule.htm
(NPSC2009高中組初賽pB)
有長度N<1000000的非負整數序列，
一段連續整數和代表一種出租方案的效能
也就是說有N(N+1)/2種不同的出租方案
問組合效能由小到大排列中排行第M的出租方案效能會是多少
測試資料(高中組初賽裁判測資)：http://contest.cc.ntu.edu.tw/npsc2009/schedule.htm
(NPSC2009高中組初賽pB)
有長度N<1000000的非負整數序列，
一段連續整數和代表一種出租方案的效能
也就是說有N(N+1)/2種不同的出租方案
問組合效能由小到大排列中排行第M的出租方案效能會是多少
2011年11月24日 星期四
PKU3767-I Wanna Go Home
題目：http://poj.org/problem?id=3767
有n個點m條邊的無向帶權圖(2<=N<=600，0<=M<=10000)
形容的說法是每個點不是屬於國家1、就是屬於國家2
Mr.M現在會從一個屬於國家1的點出發，問走到某個國家2點的最短路是多少？
但是不同國家間的交通必須繳交通行證，不巧Mr.M只申請了一張
有n個點m條邊的無向帶權圖(2<=N<=600，0<=M<=10000)
形容的說法是每個點不是屬於國家1、就是屬於國家2
Mr.M現在會從一個屬於國家1的點出發，問走到某個國家2點的最短路是多少？
但是不同國家間的交通必須繳交通行證，不巧Mr.M只申請了一張
PKU2723-Get Luffy Out
題目：http://poj.org/problem?id=2723
有N對鑰匙、M層樓，編號X的鑰匙可以開編號X的門
其中這N對鑰匙中的每一對，都只能從兩把鑰匙中選一把帶在身上
(對於p,q這對鑰匙，選了p的話q就會消失，反之亦然)
而這M層順序分別1F,2F,3F,...,MF，各層樓也有兩道門
只要打開其中一道門就能通過該層樓了
現在Luffy被關起來了，他的好朋友Ratish要去救他
對每筆給定的鑰匙以及門組合，請問Ratish最多可以爬到幾層樓？
(到達5F即1F,2F,3F,4F,5F都成功通過)
(2011.12.16補上解題報告)
有N對鑰匙、M層樓，編號X的鑰匙可以開編號X的門
其中這N對鑰匙中的每一對，都只能從兩把鑰匙中選一把帶在身上
(對於p,q這對鑰匙，選了p的話q就會消失，反之亦然)
而這M層順序分別1F,2F,3F,...,MF，各層樓也有兩道門
只要打開其中一道門就能通過該層樓了
現在Luffy被關起來了，他的好朋友Ratish要去救他
對每筆給定的鑰匙以及門組合，請問Ratish最多可以爬到幾層樓？
(到達5F即1F,2F,3F,4F,5F都成功通過)
(2011.12.16補上解題報告)
PKU2479-Maximum sum
題目：http://poj.org/problem?id=2479
所謂的一段區間[i,j]，必須i<=j (至少一個元素)
問最大取兩段不相交區間和是多少？
需要注意的是，再怎麼差也要取一個最大的。
(全是負數的話就得選最大的兩個負數)
(2011.12.16補上解題報告，姊妹題PKU2593買一送一)
所謂的一段區間[i,j]，必須i<=j (至少一個元素)
問最大取兩段不相交區間和是多少？
需要注意的是，再怎麼差也要取一個最大的。
(全是負數的話就得選最大的兩個負數)
(2011.12.16補上解題報告，姊妹題PKU2593買一送一)
PKU2352-Stars
題目：http://poj.org/problem?id=2352
滿天星斗的天空有N(不超過15000)顆星星，給出它們的座標(非負整數)
(已經幫你按照Y座標排序，如果Y相同會照X排序)
請問0,1,...,N-2,N-1級星分別有幾顆呢？(N=5即輸出0,1,2,3,4級星的數目)
我們定義一顆星星的等級是L，表示有L顆其他星星在這顆星的左下方(正左和正下都算)
(2011.12.16補上解題報告)
滿天星斗的天空有N(不超過15000)顆星星，給出它們的座標(非負整數)
(已經幫你按照Y座標排序，如果Y相同會照X排序)
請問0,1,...,N-2,N-1級星分別有幾顆呢？(N=5即輸出0,1,2,3,4級星的數目)
我們定義一顆星星的等級是L，表示有L顆其他星星在這顆星的左下方(正左和正下都算)
(2011.12.16補上解題報告)
PKU1129-Channel Allocation
題目：http://poj.org/problem?id=1129
給定一個"平面圖"，問最少要幾種顏色染上去能讓同色點不相鄰
雖然已知答案只會是1,2,3,4(四色定理)
看了一下發現我當年的code是貪心隨便亂圖色就過了(這題數據比較弱)
改天來研究正解...
(解題報告待補)
給定一個"平面圖"，問最少要幾種顏色染上去能讓同色點不相鄰
雖然已知答案只會是1,2,3,4(四色定理)
看了一下發現我當年的code是貪心隨便亂圖色就過了(這題數據比較弱)
改天來研究正解...
(解題報告待補)
PKU1015-Jury Compromise
題目：http://poj.org/problem?id=1015
有n個人要選m個人當陪審團(n<=200,m<=20)
每個人對控方和辯方有不同的好感度(這些值介於0...20)
給出一種陪審團組合滿足 | "控方總好感"-"辯方總好感" | 最小，
並且 "控方總好感"+"辯方總好感" 最大
(之前這篇還沒補上內容的時候google "pku 1015"就會連進來了...真可怕QQ)
有n個人要選m個人當陪審團(n<=200,m<=20)
每個人對控方和辯方有不同的好感度(這些值介於0...20)
給出一種陪審團組合滿足 | "控方總好感"-"辯方總好感" | 最小，
並且 "控方總好感"+"辯方總好感" 最大
(之前這篇還沒補上內容的時候google "pku 1015"就會連進來了...真可怕QQ)
PKU1000-A+B Problem
題目：http://poj.org/problem?id=1000
其實就是輸出A+B的值，各大Judge可見的測試用題
倒是可以提一點
我先前在windows上利用wget的功能做了一個程式
把PKU上排名前5000名使用者的AC記錄全部撈出來
然後統計各題AC人數、製成統計表
http://codepad.org/amaNAHFv
第一行1000 4556
就是題號1000有4556人AC的意思，有約10％的人沒寫這題XD
搜尋一下題號2299(求逆序數對數目，50萬個數字)
2299 2362
發現有2362個人AC，這題在第99行(意即第99簡單的題目)
3666有n^2作法、比較複雜的nlgn作法
3666 563
位居第779名，算比較難的題目
其實就是輸出A+B的值，各大Judge可見的測試用題
倒是可以提一點
我先前在windows上利用wget的功能做了一個程式
把PKU上排名前5000名使用者的AC記錄全部撈出來
然後統計各題AC人數、製成統計表
http://codepad.org/amaNAHFv
第一行1000 4556
就是題號1000有4556人AC的意思，有約10％的人沒寫這題XD
搜尋一下題號2299(求逆序數對數目，50萬個數字)
2299 2362
發現有2362個人AC，這題在第99行(意即第99簡單的題目)
3666有n^2作法、比較複雜的nlgn作法
3666 563
位居第779名，算比較難的題目
2011年11月17日 星期四
HOJ85-毛毛蟲問題
題目：http://hoj.mooo.com/judge/index.php/problem/view/85
(我超愛這題的題目描述，好可愛阿≧ｘ≦)
有N隻(N<=300000)毛毛蟲，想選出儘量多的毛毛蟲放進觀察箱裡並讓它們存活
每隻毛毛蟲有二氧化碳排放量a以及忍受度b
讓觀察箱中平均每隻毛毛蟲收到的二氧化碳都不超過b
(我超愛這題的題目描述，好可愛阿≧ｘ≦)
有N隻(N<=300000)毛毛蟲，想選出儘量多的毛毛蟲放進觀察箱裡並讓它們存活
每隻毛毛蟲有二氧化碳排放量a以及忍受度b
讓觀察箱中平均每隻毛毛蟲收到的二氧化碳都不超過b
2011年11月10日 星期四
PKU3268-Silver Cow Party
題目：http://poj.org/problem?id=3268
有向圖加權圖N個點(N<=1000)、M條邊(M<=100000)
權重都是正的
問對於一個給定的點X，
求點對(X,i)使得(X到i的最短路徑+i到X的最短路徑)最大
有向圖加權圖N個點(N<=1000)、M條邊(M<=100000)
權重都是正的
問對於一個給定的點X，
求點對(X,i)使得(X到i的最短路徑+i到X的最短路徑)最大
2011年11月8日 星期二
HOJ90-買賣土地
題目：http://hoj.mooo.com/judge/index.php/problem/view/90
給一個N*N大小(N<=2000)的矩陣以及K值，問是否存在一個子矩陣和t滿足K<=t<=2K
給一個N*N大小(N<=2000)的矩陣以及K值，問是否存在一個子矩陣和t滿足K<=t<=2K
PKU3481-DoubleQueue
題目頁：http://poj.org/problem?id=3481
每個用戶有識別號K以及優先度P
有很多用戶要登入銀行系統等待被處理
給一段操作序列，可能有
1.加入某用戶(K,P)
2.服務優先度最高的用戶
3.服務優先度最低的用戶
對每個2、3操作輸出被處理到的用戶識別號
如果沒有用戶等待被處理，就輸出0
每個用戶有識別號K以及優先度P
有很多用戶要登入銀行系統等待被處理
給一段操作序列，可能有
1.加入某用戶(K,P)
2.服務優先度最高的用戶
3.服務優先度最低的用戶
對每個2、3操作輸出被處理到的用戶識別號
如果沒有用戶等待被處理，就輸出0
訂閱：
文章 (Atom)