Classified Problems on Online Judge
練習題選自以下線上測評系統
* sicily:http://soj.me, 中山大學Sicily線上測評系統
* UVA OnlineJudge, 題号字首為uva
* ProgrammingChanlanges Online Judge, 題号字首為pc
題目的分類僅供參考，很多題目有多種實作，有些題目比較綜合，是以或許有不确切或不正确的分類，發現問題請提醒我。
1. 程式設計入門
2. 資料結構
3. 字元串
4. 排序
5. 算術與代數
6. 組合問題
7. 數論
8. 搜尋: 回溯法，啟發式搜尋
9. 圖周遊
10. 圖算法
11. 動态規劃
12. 網格,幾何,計算幾何
【程式設計入門】
PC 110101, uva 100, The 3n+1 problem, 難度 1
PC 110102, uva 10189, Minesweeper, 難度 1
PC 110103, uva 10137, The Trip, 難度 1
pc 110104, uva 706, LC-Display, 難度 1
pc 110105, uva 10267, Graphical Editor, 難度 1
PC 110106, uva 10033, Interpreter, 難度 2
pc 110107, uva 10196, Check the Check, 難度 1
PC 110108, uva 10142, Australian Voting, 難度 1
sicily 1144陶陶摘蘋果. 簡單計數，難度0
sicily 1145校門外的樹. 簡單計數，難度0
sicily 1232Electrical Outlets.簡單計數，難度0
sicily 1324 Score.簡單計數，難度0
sicily 1157 Thehardest problem.簡單大小比較，難度0
sicily 1147誰拿了最多獎學金. 結構體、數組、分支，難度1
sicily 1795 Table tennis, 幾何題, 難度
sicily 1798 Aliceand Bob,政策, 難度1
sicily 1087 Funny game. 簡單政策. 難度1
sicily 1510 Mispelling, 字元串, 難度0
sicily 1500 Prime Gap. 求小于給定整數的最大素數. 難度1.
sicily 1561 PRIME Number. 難度1
sicily 1007 To and Fro, 數組與下标（二維數組）, 難度1
sicily 1036 Crypto Columns, 二維數組,字元串,排序, 難度1
sicily 1014, Specialized Four-Dig, 進制轉換,字元串, stack, 難度 1
sicily 1813 M進制數問題, 難度 1
sicily 1298 數制轉換. 把整數轉換成特殊3進制. 難度1.
sicily 1325 Digit Generator. 提取整數各位數字. 難度0
sicily 1154 easysort.簡單排序. 難度0
sicily 1814 日期計算問題
sicily 1815 計算兩點間的距離
sicily 1816 平面幾何問題
sicily 1817 校歌手大獎賽
sicily 1818 成績轉換
【資料結構】
pc 110201, uva 10038, Jolly Jumper, 難度 1
pc 110202, uva 10315, Poker Hands, 難度 2
pc 110203, uva 10050, Hartals, 難度 2
pc 110204, uva 843, Crypt Kicker, 難度 2
pc 110205, uva 10205, Stack 'em Up, 難度 1
pc 110206, uva 10044, Erdos Numbers, 難度 2
pc 110207, uva 10258, Contest Scoreboard, 難度 1
pc 110208, uva 10149, Yahtzee, 難度 3
sicily 1200 Stick. 簡單查找配對，或排序或用set，難度1
sicily 1194 Message Flood. 單詞查找。排序後二分查找,或哈希或平衡二叉樹或set, 難度1
sicily 1931 卡片遊戲. 隊列，難度2
sicily 1443 Printer Queue. 基本隊列操作。
sicily 1021 couples. 棧, 難度1
sicily 1934 移動小球. 線性表，難度2
sicily 1509 Rails. 難度2
sicily 1768 雙棧排序
sicily 1021 couples. 棧，難度2
sicily 1210 二叉樹, 二叉樹周遊順序先後中轉換，挺經典的。
sicily 1935 二叉樹重建. 二叉樹，難度2
sicily 1082 manager, 維護一個能夠删除最小元和最大元的資料結構，可以用一個大根堆和一個小根
堆實作，Wanglei用了兩個set,set1支援最小元的删除，set2支援最大元的删除，每
加入一個新元素x，将x加入set1,-x加入set2,這樣set1的頭元素就是最小元，
set2的頭元素的相反數就是最大元．
sicily 1310 Right-Heavy Tree 笛卡爾樹相關，複雜度O(N)或O(NlogN)。
sicily 1426 Phone List 電話号碼字首檢索，trie樹相關。
sicily 1149 等價表達式 判斷表達式是否等價（遞歸求解）
sicily 1136 山海經 n長序列裡求m次區間詢問的最大連續子區間和。線段樹/RMQ
sicily 1375 Balanced Lineup. 哈希
【字元串】
pc 110302, uva 10010, Where's Waldorf, 字元串
pc 110304, uva 850, Crypt Kicker II, 字元串
pc 110306 File Fragmentation, 字元串
pc 110307 Doublets, 字元串
sicily 1133 SPAM 輸出輸入字元串裡的合法email位址。
sicily 1323 Switch text 字元串處理。
【排序和查找】
pc 110401, uva 10041, Vito's Family
pc 110403, uva 10037, Bridge
pc 110405, uva 10026, Shoemaker's Problem
pc 110406, uva 10138, CDVII
pc 110402, uva 120, Stacks of Flapjacks, 堆棧, 排序
pc 110404, uva 10191, Longest Nap
pc 110407, uva 10152, ShellSort, 龜殼排序
pc 110408, uva 10194, Football
sicily 1930 排序. 直接選擇排序. 難度1.
sicily 1046 Plane Spotting. 排序. 難度1.
sicily 1134 積木分發. 從小到大排序. 難度1.
sicily 1097 LED Modding 排序。
sicily 1438 Shopaholic 排序，隔三求和。
sicily 1306 Sorting Algorithm 基本的排序，輸出。
sicily 1198 Substring. 字元串，排序. 難度1.
sicily 1252 Defining Moment 字元串劃分前字尾
【圖周遊】
pc 110901, uva 10004, Bicoloring, 難度1
pc 110902, uva 10067, Playing with Wheels, 難度2
pc 110903, uva 10099, The Tourist Guide, 難度3
pc 110904, uva 705, Slash Maze, 難度2
pc 110905, uva 10029, Edit Step Ladders, 難度3
pc 110906, uva 10051, Tower of Cubes, 難度3 (USE UVA JUDGE-- NOT PC JUDGE)
pc 110907, uva 10187, From Dusk Till Dawn, 難度3
pc 110908, uva 10276, Hanoi Tower Troubles Again, 難度3
sicily 1936 Knight Moves. 深度優先搜尋，回溯
sicily 1940 Ordering Tasks. 拓撲排序. 難度3
sicily 1155 Can I Post the letter 判斷兩點是否可達。（圖的周遊）
sicily 1308 Dependencies among Jobs 圖的周遊。
sicily 1424 獎金 拓撲排序
sicily 1034 Forest 森林的定義，求最大寬度與深度。（深度優先周遊）
sicily 1114 Food Cubes 廣度優先周遊給3維空間圖染色。（dfs容易棧溢出）
【圖算法】
pc 111001, uva 10034, Freckles, 難度 2
pc 111002, uva 10054, The Necklace, 難度 3, (USE UVAJUDGE -- NOT PC JUDGE)
pc 111006, uva 10199, Tourist Guide, 難度 3
pc 111007, uva 10249, The Grand Dinner, 難度 4, (USE UVAJUDGE -- NOT PC JUDGE)
pc 111003, uva 10278, Fire Station, 難度 2
pc 111004, uva 10039, Railroads, 難度 3
pc 111005, uva 10158, War, 難度 3
pc 111008, uva 10092, The problem with the ProblemSetter, 難度 3
sicily 1031 Campus 單源最短路，dijkstra。
sicily 1090 Highways 最小生成樹。難度2。
sicily 1402 Panic Room 構圖求網絡最大流
sicily 1303 Job Assignment 二分圖的最大權比對
sicily 1192 Guardian of Decency 求最大獨立集，比較特殊可以轉二分比對做。
sicily 1211 商人的宣傳, 簡單題，有向圖矩陣乘法，O(n^3*logL)；直接疊代也行,O(n*m*L)。
sicily 1350 Piggy banks 給出每個點出度為1的有向圖，求環的個數。（簡單）
sicily 1423 魔王bug的2色定理 構圖求網絡的最小割。
sicily 1173 Reliable Nets 無向圖求最小的二連通子圖。（資料小可以搜尋）
sicily 1141 猴子的争鬥 完全圖最小生成樹的方法數，節點全排列: n!*(n^(n-2))
sicily 1196 Conflict 關系閉包的轉換
sicily 1170 Countdown 建樹，統計
sicily 1132 ROUTES 用括号序清單示樹，求兩節點最近公共祖先。
sicily 1210 二叉樹 知道前序後序求可能的方法數
sicily 1326 Apple Tree, 建樹，求兩結點最近公共祖先。
利用棧：計數器=0,遇到'0',計數器入棧，計數器++;遇到'1',棧頂元素出棧，并且目前棧頂元素為出棧元素父節點，連邊
【搜尋：回溯，啟發式搜尋，剪枝】
pc 110801, uva 861, Bishops
pc 110802, uva 10181, 15-Puzzle Problem (USE UVA JUDGE -- NOT PC JUDGE)
pc 110805, uva 10032, Tug of War
pc 110806 Garden of Eden
pc 110807, uva 704, Colour Hash
sicily 1002 Anti-Prime Sequences. 搜尋，回溯。
sicily 1835 N Queens Problem. 搜尋，回溯。
sicily 1444 Prime Path 廣度優先搜尋
sicily 1048 Inverso. 廣度優先搜尋BFS，二進制表示狀态判重。難度3
sicily 1317 Sudoku. 數獨求解的個數。
sicily 1171 The Game of Efil 2^16 dfs枚舉棋盤後檢測
sicily 1219 新紅黑樹. 砍樹博弈，min-max搜尋或記憶化搜尋
v1215 脫離地牢. 有限制的迷宮求兩人相遇的最小步驟。（廣度優先搜尋）
sicily 1180 Pasting Strings 給10個字元串，求一個排列使得某種權和最大，全排列搜尋。
sicily 1024 Magic Island. 無向圖的最長路，深度優先搜尋DFS. 難度2
sicily 1050 Numbers & Letters 回溯 DFS求5個數可否運算得到目标數, 否則輸出可得到的小于目标數的最大數.
sicily 1135 飛越原野 最短時間過地圖，廣度優先搜尋.
sicily 1107 Simple Puzzle 按題意搜尋，有可能有前置零，輸出排序.
sicily 1150 簡單魔闆 廣度優先搜尋，全排列的hash函數設計
sicily 1151 魔闆 廣度優先搜尋，全排列的hash函數設計
sicily 1152 簡單的馬周遊問題，迷宮問題的可行性剪枝.
sicily 1153 馬周遊問題。 同上，擴充狀态節點的時候按目标函數值排序。
sicily 1378 八數位問題. 啟發式搜尋。
【動态規劃】
pc 111101 Is Bigger Smarter? (USE UVA JUDGE -- NOT PC JUDGE)
pc 111103 Weights and Measures
pc 111104 Unidirectional TSP
pc 111106 Ferry Loading (USE UVA JUDGE -- NOT PC JUDGE)
sicily 1001 Alphacode, dp基本題
sicily 1264 Atomic Car Race dp基本題.
sicily 1342 開心的金明 背包dp
sicily 1146 采藥 01背包 剩餘類dp
sicily 1419 On the run(牛奶快遞), dp
sicily 1019 Apple Tree 樹型dp,邊dfs邊更新最優值。05南韓賽區題，本題即是經典的最近公共祖先（LCA）的簡化版。因為給出了通路順序，而且隻需求一次，是以比傳統的LCA簡單很多。可以使用傳統的單個LCA問題的樸素算法來解這道題，簡單介紹如下：
要求u和v的LCA，隻要從u的父親開始順着樹往上枚舉u的祖先并儲存在一個清單L中，然後
再用類似的方法枚舉v，當第一次發現某個祖先x在L中時，則輸出x。複雜度是o(n)。
由于這題的特殊性，也可以用一種更簡單的方法來做。那就是根據DFS的原理，設一個棧，直接從左往右掃一次。這樣也是o(n)，但寫起來更容易一些，不過比較易出錯。
另外，這題還要注意的地方就是A=B的時候要特殊處理一下。
sicily 1138 尋寶之旅 dp
sicily 1225 電子眼 樹+一邊的圖上求最小邊覆寫，樹型dp.
sicily 1404 Hie with the Pie 狀态壓縮dp
sicily 1103 The Top-Code 字元串劃分dp,要求字典序輸出方案時的狀态表示方法。
sicily 1123 The Longest Walk 有向圖求任意起終點的無重複點的最長路，狀态壓縮dp
【未歸類的 動态規劃/遞推/組合計數】
sicily 1355 The Bus 二維的最長上升子序列，最長不遞減子序列的變種。用STL裡的map寫巨簡單。
sicily 1169 ACM(ACronymMaker) 給一些短語求按題意要求構成指定縮寫的方法數.
sicily 1163 Tour 歐幾裡德旅行商問題（吳文虎那本書p314）
sicily 1233 Necklace Decomposition 按題意分割字母.
sicily 1222 單詞選擇 在給定文章裡選出連續的一段包含最多的word且長度最短.
sicily 1197 Hotel 字元串含通用符的比對,記憶化搜尋.
sicily 1120 Walk Through the Forest 簡單無向圖,求節點1到節點2的按題意走法的方法數.
sicily 1091 Maximum Sum 求分兩個部分後的和最大.
sicily 1098 Marching in the Corp 給出部分偏序關系,求可能的排名方法數.
sicily 1049 Mondriaan 2*1跟1*1的磚鋪成2*n的走道的方法數%10.
sicily 1121 Tri Tiling 2*1的轉鋪成3*n的走道的方法數。
sicily 1327 Pinary 遞推求第k個pinary數。
sicily 1233 Necklace Decomposition 按題意分割字母.
sicily 1221 數字遊戲 n個數序列每個數每次會減少b[i]。取出m個數,求最大值.
sicily 1139 電路穩定性 遞歸處理括号對序列算電路不通機率.
sicily 1108 Online Selection 問答遊戲，n層k個回答拿了m分，求最大的回答0的個數.
sicily 1033 City Road 求0,0走到n+1,m+1的最短路方法數，中間有一些障礙.
sicily 1176 Two Ends 二人從兩頭取數，對方貪心取大的，你盡量使得兩者的差大.
sicily 1413 Whac-a-Mole 打地鼠遊戲，求一定時間内能打到最多地鼠的方案。
sicily 1415 Honeycomb Walk 蜜蜂窩走N步回到出發地的方法數。
【二分法/分治】
sicily 1017 Rate of Return. 求解方程，二分. 難度2
sicily 1211 商人的宣傳 求兩點間L步到達的方法數.
sicily 1137 河床. 求一個最長的連續區間滿足其中的最小數和最大數之差不大于k。
sicily 1441 Pie 二分
【貪心】
sicily 1198 Substring 8個串排出最小字典序。（用ab<ba做比較函數排序）
sicily 1140 國王的遺産 砍不大于n/2個節點的最大樹枝
sicily 1172 Queens, Knights and Pawns 染色模拟
sicily 1193 Up the Stairs 搬箱子上樓梯.
【算數與代數】
pc 110502 Reverse and Add
pc 110503 The Archeologists' Dilemma
pc 110504 Ones
pc 110505 A multiplication game
sicily 1813 M進制數問題. 進制轉換，難度1
sicily 1201 01000001. 大整數二進制加法
sicily 1029 Rabbit. 高精度求和，難度2
sicily 1020 Big Integer. 高精度數求模，難度2
sicily 1381 a * b. 高精度乘法
sicily 1240 Faulty Odometer 十進制數少了4的計數
【組合問題】
pc 110603 Counting
pc 110604 Expressions
pc 110606 The Priest Mathematician
pc 110607 Selfdescribing Sequence
sicily 1089 Farey Sequence. 計算Farey Sequence元素個數. 難度2
sicily 1224 速配遊戲 組合數學上經典的穩定婚姻問題。
sicily 1242 Suit Distribution 無聊計數
sicily 1174 Square Count 數方塊數，容斥原理。
sicily 1302 Magic Square 奇數階的魔方構造
sicily 1125 Arnie versus the IRS. 兩個日期間0-9數字出現次數統計，周末不計。
sicily 1200 Stick. 奇數根木棍，不同種類的有偶數個，有一種隻有奇數個。異或. 難度1
sicily 1344 數列 某種規則的數列生成
sicily 1203 The Cubic End 給一個1,3,7,9結尾的數求一個數的立方的尾部是原數
sicily 1280 Permutation
sicily 1214 信号分析 數列找規律求an=n的個數. 二進制表示時是回文。出題人梁峰， 很有意思的一題，不是看過他的報告我也想不到。請問你是否有從二進制的方向想過這個數列呢？n=1,2,3,4,5,6,7,8;an=1,1,3,1,5,3,7,1，它們的二進制形式為n=(1)2,(10)2,(11)2,(100)2,(101)2,(110)2,(111)2,(1000)2;an=(1)2,(01)2,(11)2,(11)2,(001)2,(101)2,(011)2,(111)2,(0001)2，找出什麼規律了嗎？an的二進制串恰好是n的二進制串的反轉。其實這個可以用歸納法證明：對于a2n=an，(2n)2=(n)2_0（注意這裡設”_”為二進制串連接配接符号，再設~n為n的二進制串倒轉），經函數a反轉後等式成立（反轉後0在前面實際就沒了）。
對于a4n+1 = 2*a2n+1 - an，(4n+1)2=(n)2_01，(2n+1)2=(n)2_1，(a4n+1)2=10_(~n)2，2*a(2n+1)=2*[1_(~n)2]=1_(~n)2_0，an=(~n)2，a4n+1 + an = 10_(~n)2 + (~n)2 = 1_(~n)2_0 =
2*a2n+1。同理a4n+3等式亦相同證明，綜上等式對所有n∈N均成立，證畢。知道這個性質，簡單了，使得an=n的隻有那些二進制形式是回文串的了，枚舉二進制的前半部分p，翻轉複制到後一半，注意要生成兩個n值，一個是p_(~p)，一個是p_~(int(p/2))，如果小于等于n，則統計。時間複雜度是O(√n)。
【數論】
pc 110702 Carmichael Numbers (USE UVA JUDGE -- NOT PC JUDGE)
pc 110704 Factovisors
pc 110707 Marbles
pc 110708 Repackaging
【暫時未細分的數學】
sicily 1251 Plinko 彈珠遊戲算機率
sicily 1258 It 多項式求導
sicily 1047 Super Snooker 連續的數和可否二分.
sicily 1448 Antimonotonicity 最長不單調子序列（f[0]>f[1]<f[2]>f[3]..）統計極點個數
sicily 1433 Optimal Parking 直接算
sicily 1259 Sum of Consecutive Prime Numbers 連續素數和
sicily 1239 Smallest Differencev 一些數位，組成差最小的兩個數
sicily 1231 The Embarrassed Cryptographer 兩個素數積，枚舉因子
sicily 1218 紀念郵票 同1209
sicily 1209 Sequence Sum Possibilities 求m分解成不同的連續整數和的方法數
sicily 1206 Stacking Cylinders 堆圓筒，解方程.
sicily 1199 GCD 求小于N且與N的GCD大于M的數個數.
sicily 1190 Reduced ID Number 找最小的數使得給出的所有數mod它的結果不同
sicily 1099 Packing Passengers 線性模方程
sicily 1119 Factstone Benchmark 求n!<=2^k的最大n. 兩邊取對數.
sicily 1412 Tour Guide n個物體向各個方向做勻速運動。
sicily 1305 Who’s Winner 博弈題，找規律。
【模拟/其他】
sicily 1122 Prerequisites 模拟統計學生選課。
sicily 1093 Air Express 枚舉。
sicily 1237 Paint Mix 黑白染料混合出指定灰階的染料。
sicily 1202 The Bank of Kalii 日期比較
sicily 1187 Laserbox 機器人運動模拟，dfs周遊。
sicily 1177 Take Your Vitamins 按要求做一些基本的資料統計。
sicily 1182 Context-Free Clock 鐘表時間和時針分針之間夾角的關系。
sicily 1100 Tennis Anyone 網球排名統計。
sicily 1110 ioi photos 模拟.統計
sicily 1128 DICE 判斷骰子是左手型還是右手型，模拟旋轉.(逆序可以做)
sicily 1129 ISBN 給定規律求ISBN最後一位.
sicily 1401 Children of the Candy Corn 模拟左手規則走迷宮。
sicily 1205 brainf*ck 模拟解釋執行題目中定義的一種程式設計語言
【幾何與計算幾何】
pc 111202 The Monocycle
pc 111203 Star
pc 111205 Robbery
pc 111207 Dermuba Triangle
pc 111301 Dog and Gopher
pc 111302 Rope Crisis in Ropeland!
pc 111305 Birthday Cake (USE UVA JUDGE -- NOT PC JUDGE)
pc 111308 How Big Is It?
pc 111401 Herding Frosh
pc 111403 Chainsaw Massacre
pc 111404 Hotter Colder
pc 111408 Nice Milk
sicily 1012 Stacking Cylinders. 平面幾何. 難度2
sicily 1175 Swamp Things 平面上N個點，求一條經過最多點的直線。
sicily 1234 Playground 半圓圈能否構成封閉圈。平面圖，轉為判斷多邊形能否構成
sicily 1179 Extrusion 多邊形求面積
sicily 1045 Space Management 求平面上矩形疊加的總面積，矩形切割或者離散化.
sicily 1092 Stars in Your Window 線段樹.
sicily 1145 校門外的樹 離散化或O(n)的掃描
sicily 1223 防禦力場 求一條過目标點的直線，使得直線一邊的點最少
sicily 1216 野外行軍 光程最短路
sicily 1118 War on Weather 球外一點與球切線直接判斷範圍。
![D. Ehab the Xorcist(構造+思維)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)