隨筆-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個點，讓「最短的點間距離」最大
並且起點和終點不能移除