PKU3251-Big Square

題目： http://poj.org/problem?id=3251
Farmer John擁有很多乳牛，事實上，Farmer Bob也有很多乳牛
他們倆決定來一場世紀乳牛大對決！
現在他們把各自的乳牛放置到一個N*N(100*100)網格的交會點上
希望能圍出一個最大的正方形四個角落都站著自己陣營的乳牛
正方形的邊不一定要和網格平行
(一格只會有0~1隻乳牛，所以只有 空格'*' FJ側'J' 和 FB側'B'三種符號)

現在所有的乳牛都站到網格上了，除了Farmer John的乳牛Bessie之外
把Bessie放進去以後FJ側能圍出多大面積的正方型呢？

(最大的正方形四角不一定要包含Bessie，
給出的測資一定會有至少一個'*'給Bessie站)

PKU3046-Ant Counting

題目：http://poj.org/problem?id=3046
Bessie正在觀察A隻螞蟻
它們可以分成T(1000)個族群、編號1...T，每個族群有1...100隻螞蟻
(也就是說A最多到100000)
Bessie想要把它們分成好多好多子集合
她想知道具有S隻螞蟻的子集合數+(S+1)螞蟻子集數+(S+2)螞蟻子集數+...+B螞蟻子集數
總共是多少？(mod 1000000)

PKU3045-Cow Acrobats

題目：http://poj.org/problem?id=3045
FJ有N(50000)頭牛，每頭牛有自己的重量W_i和力量S_i
現在這些牛想要玩疊羅漢
每隻牛承受的風險值=自己頭上所有牛的重量和-力量
某個疊羅漢方法它倒塌的危險相當於風險最大那頭牛的風險值
問最優的情形下最小的危險度

PKU3263-Tallest Cow

題目：http://poj.org/problem?id=3263
FJ有N(10000)頭牛一字排開，每頭牛有各自的正整數高度
並且已知最高的l號牛的高度是H
再來給出R條「某u牛能看見某v牛」的關係
代表著
1.h[u]<=h[v]
2.其他介於u...v之間的x都滿足h[x]<h[u]
一定存在滿足所有約束條件的解，問每一頭牛最高可能是多高

PKU3279-Fliptile

題目：http://poj.org/problem?id=3279
(經典燈泡遊戲)
有一個至多15*15的黑白棋盤格
每次可以選擇某個位置進行「操作」，使該位置+四周黑變白白變黑
輸出操作數最少的方案使得棋盤全部變白，如果有多個方案應輸出字典序最小的

/*
事實上，本人驗過原USACO測資、全部只有一組解…字典序可以無視
*/

PKU3272-Cow Traffic

題目：http://poj.org/problem?id=3272
給一N(5000)點M(50000)邊的有向無環圖，點編號1...N
保證所有連結邊u->v都滿足u<v、可能有重邊、所有點都能走到點N
(所以，它也是個弱連通圖)

入度為0的點是起點，編號N是終點
問從起點走到終點的所有路徑中，「被經過最多次的邊」被經過了幾次？

PKU3190-Stall Reservations

題目：http://poj.org/problem?id=3190
有N(50000)頭牛，每頭牛都有產奶時段[A,B]
每次奶牛都要自己用一個牛欄來產奶，當她產完以後、其他牛才可以重複使用
問最少要幾個牛欄、並且輸出任意一種分配方案

PKU3260-The Fewest Coins

題目：http://poj.org/problem?id=3260
FJ有N(100)種面額為Vi(120)的硬幣，每種硬幣有Ci(10000)個

他想去商店購買價值T(10000)的物品，如果可行的話、可以給較多的總金額來找錢

問最小的支付硬幣數+找回硬幣數(商店擁有無限個各種硬幣)

PKU3280-Cheapest Palindrome

題目：http://poj.org/problem?id=3280
給一長度為M(2000)的小寫字母字串
以及所有出現字母的"增加成本"和"刪除成本"
求讓字串變成回文的最小成本

PKU3662-Telephone Lines

題目：http://poj.org/problem?id=3662
給一張有N(1000)個點編號1...N，P(10000)條邊的帶權無向圖
現在FJ想從中選一些邊來架電話線，好讓點編號1和編號N連通
架電話線的費用算法是所選的所有邊中，最大的那一條權重

並且電話公司提供了FJ一些優惠，其中K條邊是免費的
問FJ最少要花多少錢、架不起來要輸出-1

NTUJ1584-崩壞的道路

題目：http://acm.csie.org/ntujudge/problem.php?id=1584
樹上有N(10000)個節點，其中有T個點是重要的
每條邊上有權重代表拔走這條邊的花費，現在想拔走恰好K條邊
使得拔完以後每個連通塊都保有至少一個重要節點
問最小花費
(題設保證拔法一定存在)

PKU3670-Eating Together

題目：http://poj.org/problem?id=3670
由N(30000)個{1,2,3}組成的數列，每次可以塗掉一個號碼換任意一個新的號碼
問最少要塗改幾次才能把整個數列弄成不遞增或不遞降

PKU3083-Children of the Candy Corn

題目：http://poj.org/problem?id=3083
迷宮遊戲存在一種找路的策略，叫左手法則(或右手法則)
意即行走選路完全依據「牆壁靠左手邊」的原則
當然，只有入口和出口都在迷宮邊邊的時候才有效、這裡保證都找得到路

給一個w*h(40*40)的迷宮、有一些障礙物
問左手法則會走幾步？右手法則走幾步？最佳路線會走幾步？

(推薦這題!)

TIOJ1643-建築工程規劃

題目：http://tioj.redirectme.net:8080/JudgeOnline/showproblem?problem_id=1643
有一N*M(1000*1000)的棋盤格
畫出面積最大的一塊長方形，滿足長方形內最大值-最小值不超過L(20)

PKU3267-The Cow Lexicon

題目：http://poj.org/problem?id=3267
給一個信息串長度L(300)，以及字典中W(600)個的單詞(長25)
問最少要刪除幾個字元，始能讓整條信息全部由字典信息串接起來
(字典中的字可以重複用)


程式碼：http://codepad.org/xdaN3zhU

silver組的題目可以嗅出的風格：【直白DP】

PKU1276-Cash Machine

題目：http://poj.org/problem?id=1276

程式碼：http://codepad.org/gFdQ2EmB

和pku1014-dividing異曲同工，就是個【多重背包】

PKU2996-Help Me with the Game

題目：http://poj.org/problem?id=2996
程式碼：http://codepad.org/PhUyvSra
與2993搭檔的模擬題

PKU2993-Emag eht htiw Em Pleh

題目：http://poj.org/problem?id=2993
程式碼：http://codepad.org/qcLhswFn

就是2996-Help Me with the Game的倒轉版
同為模擬題
不過相較2996需要考慮輸出順序來講，2993也許比較容易一次AC

PKU1573-Robot Motion

題目：http://poj.org/problem?id=1573

模擬

PKU2632-Crashing Robots

題目：http://poj.org/problem?id=2632
程式碼：http://codepad.org/Jhi0ePzU

就是個模擬，沒什麼好說的

PKU3295-Tautology

題目：http://poj.org/problem?id=3295
程式碼：http://codepad.org/5ObB5ut1 (精簡的idea來自網路)

訓練計畫說它是構造法，我AC了怎麼想也不了解什麼是構造法…
嗯，奇妙的東西

PKU3984-迷宮問題

題目：http://poj.org/problem?id=3984

一道數據很小的迷宮題(為什麼我都找不到正常的迷宮題...)

2012Mar總結

這個月是成果豐碩的一個月呢！經過了入營考、第一階段

有TOI那麼好的coding環境，AC了一些不錯的題目

<RMQ+LCA>
http://nphard001.blogspot.com/2012/03/pku3264-balanced-lineup.html
http://nphard001.blogspot.com/2012/03/pku1330-nearest-common-ancestors.html
高一曾經寫過RMQ，不過完全沒有了解、基本上邊界+1 -1都是亂矇的
實際理解覺得這資料結構挺優美的

<爆搜大未來>
因為受到一模爆搜題全錯的打擊，開啟了一系列的爆搜題
http://nphard001.blogspot.com/2012/03/pku3322-bloxorz-i.html
http://nphard001.blogspot.com/2012/03/pku1475-pushing-boxes.html
http://nphard001.blogspot.com/2012/03/pku2286-rotation-game.html
尤其是rotation-game，讓我首co了IDA*、真高興學到一個那麼偷懶的算法(欸?)

<綜合>
http://nphard001.blogspot.com/2012/03/pku3171-cleaning-shifts.html
和1月份AC的PKU2376同名題目兩相對照，感覺很深刻
更深的體會一些DP和貪心的本質

http://nphard001.blogspot.com/2012/03/pku1737-connected-graph.html
http://nphard001.blogspot.com/2012/03/hoj108-ptm.html
兩道組合數學問題，尤其PTM真的很變態、花了我整整三天才想出來
大概覺得很充實吧？

http://nphard001.blogspot.com/2012/03/hoj100.html
選秀(淘汰賽)，來自POI的圖論題目、突然覺得POI的題目其實頗有魅力呢！

隨筆-Judge

剛剛一時興起想把以前各judge的AC數抓來統計一下
zerojudge: 300
TIOJ:96
UVa:135
USACO Training:97
POJ:173
HOJ:26

共計827題
本來以為水題率那麼高應該會破千的哈哈哈結果還差太遠

PKU2286-The Rotation Game

題目：http://poj.org/problem?id=2286
井字型的盤面，共24格，擺放1、2、3各8個
可以使用的行動是往某個方向「抽動」一格，讓那排往特定方向輪動
目標是讓中間八格的數字一樣
輸出一種步數最少並字典序最小的方案

並且報告中間是哪一種數字八個一樣…(我在這WA了超久，我以為是輸出步數)


程式碼：http://codepad.org/KrDgnk6a
其實就是一道【IDA*】基礎題
清楚簡明教程請參考：http://www.4ucode.com/Study/Topic/1689492

HOJ108-PTM序列

題目：http://hoj.mooo.com/judge/index.php/problem/view/108
今給一由01組成的字串A1(長度100萬)
定義A2=A1A1'，即原A1接上自己的補串
問對給出的n(到10^18)，An串的「01各數相同子串數」有多少？

例如
001110有4個子串合乎要求
123456<--編號，[1,4][2,3][5,6][1,6]四個子串內0和1數量相等

PKU1475-Pushing Boxes

題目：http://poj.org/problem?id=1475
給一個R*C(20*20)的棋盤
S是人的起點、B是箱子，想用最少推的次數把箱子推到T目標格
並且輸出整個推的操作序列，如果推的次數一樣則選總次數最少

PKU3322-Bloxorz I

題目：http://poj.org/problem?id=3322
文字說明原題有了，這裡給出原本的遊戲bloxorz
盤面大小至多500*500
#是障礙物
.是正常的格子
X表示起點，也可以是XX表示一開始是躺著
O表示終點、終點總是要剛好立在O上
E表示脆弱的格子，如果站在E上會bye

程式碼：http://codepad.org/NcTAYaBL
事實上，就是一個需要細心耐心愛心的暴搜

PKU3262-Protecting the Flowers

題目：http://poj.org/problem?id=3262
有N(100000)隻牛在花田裡快樂的吃花，FJ要把它們一隻一隻牽回牧場
每隻牛需要花Ti的時間牽回家、再走Ti回來花田(就是花2*Ti時間)
當FJ在牽牛的過程中，其他留在原地的牛會繼續以每時間單位Di的速度享用花朵
計算出最優的牽牛順序，報告花被吃掉的最小數目

程式碼：http://codepad.org/P7BU21mO
目前糊里糊塗AC的題目，待補

PKU3181-Dollar Dayz

題目：http://poj.org/problem?id=3181

簡單換硬幣方案數問題，需要大數

PKU3187-Backward Digit Sums

題目：http://poj.org/problem?id=3187

只要你會【std::next_permutation】的話，就能瞬殺這題了

PKU2411-Mondriaan's Dream

題目：http://poj.org/problem?id=2411

求寬度n、高度m的棋盤格上，塞滿2*1骨牌的方法數有多少種？(至多11*11)

PKU3660-Cow Contest

就是個【Floyd】，code很短不過倒也不算水題

PKU3168-Treats for the Cows

題目：http://poj.org/problem?id=3186
一正整數陣列a[]有N(2000)個元素一字排開
從第一輪開始，每輪只能從最左端或最右端拿走一個數字，得分=輪數*a[i]
問最大得分

PKU1160-Post Office

我還不會O(n^2)，先寫著

PKU1236-Network of Schools

題目：http://poj.org/problem?id=1236
給N(100)個點組成的有向圖，問：
1.至少要選幾個點當起點，能走過整張圖
2.至少要加幾條邊，可以讓整個圖任兩點能相互連通

PKU2231-Moo Volume

Moo~~~Farmer John的牛最喜歡聊天了，你要算它們聊天音量的總合

只能算比較簡單吧，我覺得不是水題

PKU3624-Charm Bracelet

原來，其實我會CO【01背包問題】

PKU3250-Bad Hair Day

題目：http://poj.org/problem?id=3250
給N(80000)個正整數的一個序列
問有多少對i,j (1<=i<j<=N)滿足 a[i]>a[k] (i<k<=j)

程式碼：http://codepad.org/111J65km
其實就是個【stack】

PKU2513-Colored Sticks

題目：http://poj.org/problem?id=2513
給出不超過250000根棍子
一根棍子用兩個字串(分別不超過10個字)來表示頭尾兩端的顏色
棍子可以反轉，問是否可能將棍子全部接成一條線、讓它們相接處顏色相同

PKU1330-Nearest Common Ancestors

題目：http://poj.org/problem?id=1330
(其實就是Lowest Common Ancestor，LCA問題)
給一棵具有N(10000)個節點的有根樹，以及一筆詢問p,q
問點p和點q最近公共祖先的點編號是什麼？


程式碼：http://codepad.org/HgaMlA8m
測資弱了點，只有單筆詢問、但仍不失是經典問題

我覺得這兒已經寫得很完備，請自行參考：
LCA RMQ求解最小公共祖先问题

PKU3264-Balanced Lineup

題目：http://poj.org/problem?id=3264
有N(50000)個元素的陣列，給Q(200000)筆詢問[p,q]，回答該區間內最大值-最小值

PKU3171-Cleaning Shifts

題目：http://poj.org/problem?id=3171
連題名都一模一樣、同樣來自USACO Silverpku2376-cleaning-shifts的帶權版本
給出N條(10000)區間、選擇該區間的成本以及想覆蓋的範圍[M,E] (0...86399)
問覆蓋所求區間的最小成本，無解輸出-1

PKU1328-Radar Installation

題目：http://poj.org/problem?id=1328
現在二維平面上有n(1000)個點，想要在x軸上安排針測距離d的雷達、覆蓋所有點
問最少要安排幾個雷達？
(debug搞了N久才發現我Case的C沒大寫…)

PKU2586-Y2K Accounting Bug

水

PKU2965-The Pilots Brothers' refrigerator

和PKU1753-Flip Game解法類似、暴力解

HOJ100-選秀

題目：http://hoj.mooo.com/judge/index.php/problem/view/100
給一張具有n(100000)個點的有向圖、邊不超過1000000條
存在邊(u,v)代表選手u比賽的時候一定會贏選手v
(是故u,v和v,u只可能有一條存在)
如果u和v之間沒有邊存在，那麼比賽的時候有可能u贏v也可能反過來
比賽的順序是任意的，問有哪些人「有可能」奪冠？

PKU1737-Connected Graph

題目：http://poj.org/problem?id=1737
男人八題之一
組合數學問題，給一個具n個節點(1...50)的無向圖
問有多少種不同的連結方法可以使其成為連通圖
每個點視為相異(可以想像編號1...n，同構圖編號序不同也當成不同)

圖論神話

有一天，神說要有樹、於是就有了二元樹；神說要有圖、於是就有了無向圖

大家有了這麼好用的資料結構，對神感謝不已

可惜後來人們越用越複雜、漸漸地不太方便

於是神就發明了權重

2012Feb總結

這整個月寒假幾乎都在打minecraft
結果似乎也沒生出幾篇遊戲攻略文，真是懶惰二月天

http://nphard001.blogspot.com/2012/02/pku2227-wedding-juicer.html
即使會了heap好像也不太好想
這題我高一的時候就在黑書上看到了，直到最近才AC(真是...)

http://nphard001.blogspot.com/2012/02/pku3020-antenna-placement.html
我卡N久的一道問題
說起來它的測資範圍一度把我騙去寫狀態壓縮，才發現時間根本不會過！
看discuss發現也有人跟我一樣狀態壓縮真是讓我內牛滿面後來二分匹配又一直有bug找不出來、重寫才過
現在看到解題報告文中「充滿愉悅智慧」
想想應該是源自大哲學家尼采有一本書「愉悅的智慧」 (到底有什麼干係XD)

2012Jan總結

整理code的時候發現把AC全部堆在一起頗亂的
如果按照一個月一個月放似乎不錯！
突然想來回顧一下每個月覺得收穫最多的題目好了

http://nphard001.blogspot.com/2012/01/pku1196-twofive.html
來自USACO-Training的難題，現在想起來
當時能寫出來幾乎是靠nocow上的題解(才找出bug)

http://nphard001.blogspot.com/2012/01/pku3659-cell-phone-network.html
貪心解能爽過的題目
不過如果選每個點的成本有所不同的話、那又非DP不可了
似乎貪心的題目都能搞成類似這樣的DP版本題目？

http://nphard001.blogspot.com/2012/01/pku2374-fence-obstacle-course.html
想出來覺得茅塞頓開的DP題，希望以後越DP越順手

PKU3258-River Hopscotch

題目：http://poj.org/problem?id=3258
在一個數線上有起點0和終點L，以及N個中繼點
現在想移除至多M個點，讓「最短的點間距離」最大
並且起點和終點不能移除

PKU3273-Monthly Expense

相當好懂的題目，箇中要領就是個【二分答案】

PKU1837-Balance

題目：http://poj.org/problem?id=1837
天秤上有C(20)個刻度點(-15...15)
想要把G(20)顆重量為wi(1...25)的砝碼全部掛上去
問達成兩邊平衡的"方法數"有幾種

PKU1274-The Perfect Stall

二分匹配經典裸題

PKU3256-Cow Picnic

基本DFS/BFS

PKU2436-Disease Management

枚舉

PKU2395-Out of Hay

基本最小瓶頸生成樹<-->最小生成樹

良心三大公設

(對「公設」的基本定義，請參考中文wiki「公理」)

我試著很小心的發表這篇文章，實際上、我覺得這滿深奧的
就現在我的理解也還很淺而已

來說一小段引言吧

科幻小說構造的世界裡常見一類「控制他人(思想)」的事情，那似乎可以稱得上是完完全全的控制。(頂多再多一個類似法力vs意志力的因素，把這種能力的程度設定在控制者與被控制者的角力)

想要永遠完全的控制一個人想當然爾是不可能的。
畢竟我們俗人連自己都不一定能控制了(例如說生病的時候)
但是如果想要大程度的操控一個人卻不無可能，好比說色情小說常寫的「如果你不聽我的話我就把你的裸照公開」這類的，或者是常見在夫妻之間、親子之間的控制

上面這些都滿邪惡的，不過先看看這個吧
「想要小程度的操控一大群人是很有可能的」
這樣的例子就滿地都是、大部分出現在商業行為，例如熱銷的產品、偶像追星狗仔這類現象
然而想要小程度的操控(僅僅是把錢掏出來)「一大群人」，就是利用人的一些通性

這也就是政治家和企業家在做的事情

引言到此結束

如果這是個有良心的世界，那麼它肯定會滿足下面這三句俗諺：
1.善有善報，惡有惡報
2.一分錢一分貨
3.一分耕耘一分收穫

人們非常崇拜這三句話以及背後的意涵，不是無從理解
要是人不這樣相信的話、社會就不會進步了(對吧？)

我想這是一個人類很強的通性，並且由這三句話延伸出很多有趣的現象
現在我也還沒有了解透徹、就先寫到這裡吧

小學

前些日子家母為了工作需要，去上一門叫做「風險管理」的課

其實課程內容不外乎就是一些你能想像的內容：把可能的風險全部列出來、為它們標上發生機會，以及危害的程度…

PKU1459-Power Network

題目：http://poj.org/problem?id=1459
給一張流網路，有多個源點以及匯點、求最大流的值

程式碼：http://codepad.org/RvG9mAhT

其實就是很基本的構圖Flow

明明題目說了至多100個節點阿？我陣列開104wa加大到200就AC了。

PKU3020-Antenna Placement

題目：http://poj.org/problem?id=3020
最大40*10的棋盤上有一些「*」或是「o」
想用2*1的骨牌蓋住所有的*、求最少要幾張骨牌(可以重疊)

PKU2227-The Wedding Juicer

題目：http://poj.org/problem?id=2227
有一大小N*M的棋盤(地勢模型)，每個格子各有自己的高度
(高度B可以想像成有B塊1*1*1的正立方體堆起來的柱子)
積水會從上下左右四個方向、較低的地勢流走，而棋盤外的高度等同0
問最多有幾立方單位的積水

PKU2229-Sumsets

題目：http://poj.org/problem?id=2229

待補

PKU2455-Secret Milking Machine

題目：http://poj.org/problem?id=2455
無向帶權圖有N(200)個點M(40000)條邊，現在想找出T條從點1到達點N的路徑
並且這T條路徑使用的邊不可重複
單個邊的路程越長的話，FJ的行跡也越容易暴露
找出T條夠秘密的路徑讓最長的那條路長度最短、報告這個長度

PKU2454-Jersey Politics

題目：http://poj.org/problem?id=2454

無言指數破表的一題XDDDDDDDD

可是又不算水題，乾脆直接丟無內容好了

PKU3169-Layout

題目：http://poj.org/problem?id=3169
有N(1000)隻牛站在數線上，座標x1,x2,...,xn、並且有x1<=x2<=...<=xn
以及給出ML(10000)條互相喜歡的關係，牛p喜歡牛q希望彼此距離不超過r
還有MD(10000)條互相討厭的關係、希望彼此距離至少超過s
問滿足條件的情形下，最大的xn-x1是多少？
如果條件矛盾輸出-1，答案無限大輸出-2

PKU2393-Yogurt factory

題目：http://poj.org/problem?id=2393
連續N(10000)週每週都有不同的優格生產單位成本、以及當週訂單量
除了當週立即生產滿足訂單之外，
也可以預先生產好、以每單位每週S的成本保存
問滿足全部N週訂單所需的最小生產成本

程式碼就不附了

貪心、意外很水的金組題

PKU2456-Aggressive cows

題目：http://poj.org/problem?id=2456
Farmer John的乳牛們是很Aggressive的
現在數線上有N(100000)個牛舍一字排開
一個牛舍可以裝一隻牛
以及現在想要放M隻牛進去
牛之間的距離越近的話就越容易幹架(真是Aggressive)
所以FJ希望牛之間隔的越遠越好，也就是找出一種分配方案
使得最近的牛隻之間間隔距離可以最大化
輸出這個值

PKU3168-Barn Expansion

題目：http://poj.org/problem?id=3168
給出N(25000)個不重疊的矩形，惟矩形之間可能共邊或共點
所謂可擴張矩形，是那些「不和任何其他矩形共邊或共點」的矩形
問這樣的可擴張矩形有幾個？

PKU3013-Big Christmas Tree

題目：http://poj.org/problem?id=3013
程式碼：http://codepad.org/iTWsHhPr

最短路，待補

PKU2374-Fence Obstacle Course

題目：http://poj.org/problem?id=2374
(請參考原文敘述的"INPUT DETAILS")
我這裡把它想像成SuperMario那樣2D重力的世界
有N(50000)個平台，分別高度是1,2,3,...,N、高度0就是地面
給出這些水平平台在x軸上的左右座標
現在你的起點是無限高空的S
一旦採到空中就會直直的往下掉不能控制
問最少要走水平的幾步，最後才能到達地面的x=0位置？

(我盡力了…好像越來越複雜、還是看原文吧…囧)

PKU3173-Parkside's Triangle

語法練習題，沒什麼好說的

PKU2375-Cow Ski Area

題目：http://poj.org/problem?id=2375
有個棋盤W*L(500*500)，每格有它的高度(地形棋盤)
滑雪的規則是這樣的：
1.每次走上下左右一格
2.只能從地形高的格子走到低的格子或一樣高的格子
現在Farmer Ron (不是FJ!!!)想要為他的滑雪場造一些纜車，
「一架纜車」可以為地形圖上任意兩格提供無條件的雙向連結
問最少要架幾架纜車，才能使得所有格子之間都可以互相到達？

PKU3048-Max Factor

找出質因數最大的數，必須小心該數本身是質數這種情形
還有如果只有1的話要輸出1...

PKU3051-Satellite Photographs

給個棋盤，問最大塊的連通塊有幾格？DFS水過

PKU3050-Hopscotch

題目：http://poj.org/problem?id=3050
在5*5棋盤上進行跳格子，每個格子上有數字
每次任選起點，可以任選上下左右跳一步(可以跳之前跳過的)
總共跳五步、包含起點有六個數字
問有多少種不同的跳格子序列？

程式碼：http://codepad.org/ueMxzyrU
單純的爆搜問題，利用STL的set來幫忙判重複

PKU3049-Securing the Barn

簡單明瞭的遞回爆搜問題，值得推薦

PKU3041-Asteroids

題目：http://poj.org/problem?id=3041
給一個N*N的棋盤(500*500)，以及M個小行星的座標
現在Bessie有個武器，發射一次可以把一行或一列的小行星毀滅掉
問至少要發射幾次才能毀滅全部小行星？

PKU1094-Sorting It All Out

題目：http://poj.org/problem?id=1094
有N(26)個字母代表的變數(從A開始的前N個字母)，以及M條由「小於」構成的關係式
目標是找出這些變數確切的由小到大序列
如果前x條關係式就發現矛盾、或前x條關係即可確定有唯一解都應報告
上述都不成立，應報告無解


程式碼：http://codepad.org/zU4HXHf5
總之就是個[拓撲排序]，容易錯的陷阱大概被我敘述掉了(看discuss的)

PKU3026-Borg Maze

題目：http://poj.org/problem?id=3026
有個R*C(50*50)的迷宮，裡面有些障礙物#、1個掃描器S、不超過100個外星人A
現在掃描器會往上下左右一格放置粒子(是為1步)、粒子下次又會再四面放射…(如此循環)
粒子碰到外星人就會把外星人也變成和掃描器一樣
問全部粒子至少要走幾格呢
(我敘述得有點濫…)

另外提醒，這題的輸入資料蛋疼…行尾會有莫名的空格
然而表達迷宮空地的字元也是空格…請審慎選擇輸入的方法

PKU1789-Truck History

題目：http://poj.org/problem?id=1789
(這英文題敘真是他媽的難懂…)
簡言之，有N個點(2...2000)的無向帶權圖、由N個字串來代表
不同點之間連線的權重，就是字串間「相應位置字母不同的各數」
好比說aabca和bbbca的距離就是2
試著選N-1條邊讓全點連通，選中的權重和Q、讓1/Q最大

PKU2240-Arbitrage

題目：http://poj.org/problem?id=2240
程式碼：http://codepad.org/IUp6DyUD

基本和PKU1860一樣、惟輸入較繁瑣，請參考：
http://nphard001.blogspot.com/2012/01/pku1860-currency-exchange.html

PKU2253-Frogger

題目：http://poj.org/problem?id=2253
現在有n個座標點(2...200)，青蛙1想跳去找青蛙2
可是它希望可以有個適合的路線，好讓它每次跳的最大腳程可以盡量小(比較輕鬆)
(想像腳力J的青蛙可以跳距離d<=J，在石頭1能抵達石頭2的前提下求最小的J)

PKU1062-昂貴的聘禮

題目：http://poj.org/problem?id=1062
這真是一道PKU名題(?)
很可惜沒有給出「等級值」確切的範圍，我討厭這種題目

程式碼：http://codepad.org/YHCXXNx4
(無腦做法：直接枚舉等級範圍一直BellmanFord…)

PKU1860-Currency Exchange

題目：http://poj.org/problem?id=1860
有N種不同的貨幣以及M種兌換方法(100,100)，Nick擁有幣種S數量V
這M種兌換方法A B R->C R<-C
A,B表示對應的兩種貨幣編號
R是兌換比率、C是佣金，每次兌換要先扣佣金、再乘比率
(第一對RC是A->B 第二對反之)

問Nick是否有辦法通過某種兌換方法讓他的錢越換越多(當然，要是S種貨幣)

PKU3259-Wormholes

題目：http://poj.org/problem?id=3259
給定一張有向帶權圖，有N個點、M條雙向正權邊、W條單向負權邊
(N,M,W至多500,2500,200)
問圖上是否存在負環

PKU2394-Checking an Alibi

題目：http://poj.org/problem?id=2394
有N個點M條邊(500,1000)的無向帶權圖，點編號1是起點
對詢問的哪些點最短路徑長<=P

PKU3170-Knights of Ni

題目：http://poj.org/problem?id=3170
有個W*H(1000*1000)的棋盤，上面有一些空格、障礙物、果子
現在Bessie從一個位置出發，她可以走相鄰上下左右的空格
Bessie要摘到任一個果子、再送去給受傷不能走的KnightNi
問最少要走幾格
另外，在摘到果子以前Bessie不能和KnightNi站在同一格

PKU2378-Tree Cutting

題目：http://poj.org/problem?id=2378
題如其名，給一個有N(10000)個節點的無根樹，
問有哪些節點被拔掉以後，殘餘的各分塊節點數皆不超過N的一半？
(換句話說，這樣的點如果當樹根、所有子樹的總點數<=N/2)

PKU2376-Cleaning Shifts

題目：http://poj.org/problem?id=2376
有N(25000)個正整數對表示的線段[ai,bi]，
問至少選幾條才能完全覆蓋[1,T] ([1...1000000])
不可能覆蓋則輸出-1

PKU2377-Bad Cowtractors

題目：http://poj.org/problem?id=2377
給N個點M條邊(最多1000,20000)，求最大生成樹權重
求不出來必須輸出-1

(最近喜歡秒斬算法裸題…)

PKU2485-Highways

題目：http://poj.org/problem?id=2485
給出帶權無向圖N(3...500)個點間的連線距離
想要選一些連線建造高速公路
所有點之間都有路可通的前提下，最長的那條邊要盡量小
問那條邊的權重是多少？

PKU3167-Cow Patterns

題目：http://poj.org/problem?id=3167
給N(100000)個正整數(1..25)，以及K(25000)個數字的"排名格式"
問有哪些位置i，可以使A[i...i+K-1]滿足A[i+k]在這段數中排名恰好為B[k]
好比說範例測資
5 6 2 10 10 7 3 2 9
1 4 4 3 2 1
答案就只有3一個，因為：
2 10 10 7 3 2
1 4 4 3 2 1
恰好2是第1小、3是第2小、7是第3小、10是第4

---
程式碼(假解)：http://codepad.org/B4rZJgiu (47.48行表達了答案介於2000~3500)
程式碼(排名法)：待補

這裡我正解有點難產了...囧 所以待補
假解本身有一點捏、可以先參考這裡：
http://poj.org/showmessage?message_id=168920

【筆記】優良專題文章

在一些特定的主題、google能找到更精妙的解釋方法
它們多數是來自個人blog，個人的心得筆記下來造福大眾
這裡記下一些我非常喜歡的文章和大家分享：

PKU1961-Period

題目：http://poj.org/problem?id=1961
給一字串S，問對於所有的i-前綴 (指S[0...i-1])，
答出所有能達成如A^k形式的位置和對應k值(並且k>1)

程式碼：http://codepad.org/HOaY6qI0
和以下兩題類似原理的題目當同一個系列，待補內容
http://nphard001.blogspot.com/2011/11/pku3461-oulipo.html
http://nphard001.blogspot.com/2011/12/pku2406-power-strings.html

參考教程(神牛matrix67原著)：http://www.matrix67.com/blog/archives/115
堪稱最詳細最好懂的KMP算法講解

(我想，字串匹配應該算是數據結構類
畢竟有Trie有後綴數組，沒道理KMP不放一起)

【筆記】USACO-Training心得

前些日子猛然覺得，要是都比TOI了還沒從USACO-Training畢業、一定會後悔
毅力全開之下果然不出4天就把最後倒數10題做完了

===================
先說說這系列的缺點好了…(我想很少有人願意說自己AC題目的不是吧)
整個系統採取的是一章一節、一板一眼，作完一節才能看下一節的題目
可惜的是整個難度的配布其實不算是理想的簡單到難
只有第一章簡單題特多、第五章爆難，(主觀因素吧)第三章有些都可以殺爆第四章了
然而四五章也充斥不少那種，該說是太簡單呢還是太奇怪，總之就是不明所以的題目

PKU3659-Cell Phone Network

題目：http://poj.org/problem?id=3659
有個由n個點組成的無根樹
選一個點建收訊塔，那麼該點和相鄰的點都可以收到訊號
問最少要蓋幾個塔才能覆蓋全部n個點
(即最小支配集)

PKU3174-Alignment of the Planets

題目：http://poj.org/problem?id=3174
(我看了很久都看不出來題目敘述和Planets有什麼關係…)
有n個整數座標點，列出所有三點共線的三點組合

程式碼：http://codepad.org/QruEHXvF

USACO銅組題

意外的solved人數很少

N只給到770很明顯希望大家作O(n^3)、直覺簡單好懂的一題

勉強算是計算幾何吧

O(n^2lgn)也是可以的(只不過這題無用武就是)

PKU3278-Catch That Cow

題目：http://poj.org/problem?id=3278

程式碼：http://codepad.org/NRDWxBSC

FJ在數線上追牛，他可以+1 -1的移動、座標*2瞬移

問最少要幾步能追到牛

由於整個搜索空間並不大、直接開個queue把數線上0...200000全部BFS掃過就可以了

比起迷宮類的BFS問題簡單，是值得考慮的初學用題

PKU3100-Root of the Problem

和2109很像的水題(都是求n次方根到整數位)

不過有鑑於b和n實在太小，直接枚舉答案就過了…

PKU3673-Cow Multiplication

實作下去發現是非常有意思的水題

因為這可是一個誤植版的大數乘法呢！

PKU1753-Flip Game

題目：http://poj.org/problem?id=1753

程式碼：http://codepad.org/ijwNkAEk

翻旗遊戲，枚舉2^16種翻法我想是最好寫的一種

由於是全部枚舉、暴力搜索，就放C1-搜索吧

(跟直解StraightForce還是有點不太一樣的)

PKU2255-Tree Recovery

題目：http://poj.org/problem?id=2255
樹節點以字母表示，給出中序和前序表示法、輸出後序表示法


程式碼(來自劉汝佳算法競賽入門經典)：http://codepad.org/13A7plbs

經典問題(PKU訓練計畫居然說它是水題…這題對初學者太不水了吧)

整個作法其實很簡潔，看了程序就懂、就不PO解題報告了

PKU3006-Dirichlet's Theorem on Arithmetic Progressions

一道水題、範例測資給得夠多

說起來1 1 1這種特例也給了、真是夠仁慈

(題目的Title真是有夠長...)

PKU1083-Moving Tables

水題、直接照作就可以了

把簡單的題目敘述拖長真是太有ACM風格了

PKU2159-Ancient Cipher

水題，給兩字串A,B，加密可以任意排列、任意映射(不一定是凱薩)

問A是不是B加密來的

PKU3299-Humidex

給T,D,H三個值的其中兩個，依照公式求出第三個值並輸出

第一次用了cmath裡的exp和log...受教了

PKU2031-Building a Space Station

三維空間點的最小生成樹，事實上我不知道這算不算水題？

好歹基礎算法就標個無內容好了

PKU2187-Beauty Contest

題目：http://poj.org/problem?id=2187
給N個平面上的座標點(最多50000)，找出各點對中距離最遠的一對並輸出距離
程式碼(非正解)：http://codepad.org/Eu8JV5UB
事實上我覺得這題很怪就是…不少人直接枚舉凸包點就過了
另外這題的測資裡會出現重複的點、與題敘不符
(我是照我原本的作法再多判+1的點、就過了)

(解題報告待補)

PKU1113-Wall

題目：http://poj.org/problem?id=1113
順時鐘給出由n個點組成的城堡輪廓(是簡單多邊形)
現在要造一道城牆包住城堡、並且城牆上任一點和城堡任一點的距離不能小於L
問最短城牆的長度

(題目沒說要多筆輸入...)

【題單】ACM訓練計畫(poj,pku訓練計畫)

一份廣為流傳的題單，近期要開始刷了
利用手邊1-10000名解題資料，對各題號附上了連結和括弧內(AC人數)
各位可以自行複製HTML code後
搭配分析自己使用者的AC表去過濾、自由使用

PKU1196-Twofive

題目：http://poj.org/problem?id=1196
(IOI2001，USACO5.5也有收錄)
現在把A...Y總共25個字母、填到一個5*5方塊裡，好比說
ABCDE
FGHIJ
KLMNO
PQRST
UVWXY
如上的方塊型式，轉成字串型式則有ABCDEFGHIJKLMNOPQRSTUVWXY
現在25-語言是一些單詞組成的，就像上面的字串形式
然而這些25-語言的方塊形式的字母序都具有「由左而右遞增」以及「由上而下遞增」這兩種特性
按照字典序排列，第二個單詞是ABCDEFGHIJKLMNOPQRSUTVWXY、由第一個單詞交換ＵＴ組成
要求輸入單詞能算出是字典序第幾個、輸入數字能輸出對應編號的單詞

(USACO第五章最後一道AC的題目…倒數三題了)