這真是一道很無言的水題
由於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鍊最長的鍊是多長
訂閱：
文章 (Atom)