sicily 題目分類【轉】

【資料結構/圖論】

1310 Right-Heavy Tree   笛卡爾樹相關，複雜度O(N)或O(NlogN)。

1426 Phone List         電話号碼字首檢索，trie樹相關。

1443 Printer Queue      基本隊列操作。

1149 等價表達式         判斷表達式是否等價（遞歸求解）

1136 山海經             n長序列裡求m次區間詢問的最大連續子區間和。線段樹/RMQ

1252 Defining Moment    字元串劃分前字尾

1194 Message Flood      單詞查找。排序後二分查找

1201 01000001           大整數二進制加法

1381 a * b              高精度乘法

1424 獎金               拓撲排序

1350 Piggy banks        給出每個點出度為1的有向圖，求環的個數。（簡單）

1423 魔王bug的2色定理   構圖求網絡的最小割。

1173 Reliable Nets      無向圖求最小的二連通子圖。（資料小可以搜尋）

1192 Guardian of Decency 求最大獨立集，比較特殊可以轉二分比對做。

1031 Campus             單源最短路，dijkstra。

1090 Highways           最小生成樹。

1034 Forest             森林的定義，求最大寬度與深度。（深度優先周遊）

1114 Food Cubes         廣度優先周遊給3維空間圖染色。（dfs容易棧溢出）

1132 ROUTES             用括号序清單示樹，求兩節點最近公共祖先。

1155 Can I Post the letter 判斷兩點是否可達。（圖的周遊）

1141 猴子的争鬥         完全圖最小生成樹的方法數，節點全排列: n!*(n^(n-2))

1170 Countdown          建樹，統計

1196 Conflict           關系閉包的轉換

1210 二叉樹             知道前序後序求可能的方法數

1402 Panic Room         構圖求網絡最大流

1303 Job Assignment     二分圖的最大權比對

1308 Dependencies among Jobs 圖的周遊。

【幾何】

1175 Swamp Things       平面上N個點，求一條經過最多點的直線。

1234 Playground         半圓圈能否構成封閉圈。平面圖，轉為判斷多邊形能否構成

1179 Extrusion          多邊形求面積

1045 Space Management   求平面上矩形疊加的總面積，矩形切割或者離散化.

1092 Stars in Your Window 線段樹.

1145 校門外的樹         離散化或O(n)的掃描

1223 防禦力場           求一條過目标點的直線，使得直線一邊的點最少

1216 野外行軍           光程最短路

1118 War on Weather     球外一點與球切線直接判斷範圍。

【搜尋】

1444 Prime Path         廣度優先搜尋

1317 Sudoku             數獨求解的個數。

1171 The Game of Efil   2^16 dfs枚舉棋盤後檢測

1219 新紅黑樹           砍樹博弈，min-max搜尋或記憶化搜尋

1215 脫離地牢           有限制的迷宮求兩人相遇的最小步驟。（廣度優先搜尋）

1180 Pasting Strings    給10個字元串，求一個排列使得某種權和最大，全排列搜尋。

1024 Magic Island       無向圖的最長路。（深度優先搜尋）

1048 Inverso            廣度優先搜尋，二進制表示狀态判重。

1050 Numbers & Letters  深度優先搜尋

1135 飛越原野           最短時間過地圖，廣度優先搜尋.

1107 Simple Puzzle      按題意搜尋，有可能有前置零，輸出排序.

1150 簡單魔闆           廣度優先搜尋，全排列的hash函數設計

1151 魔闆 同上。

1152 簡單的馬周遊問題   迷宮問題的可行性剪枝.

1153 馬周遊問題         同上，擴充狀态節點的時候按目标函數值排序。

1378 八數位問題         啟發式搜尋。

【動态規劃/遞推/組合計數】

1342 開心的金明         背包dp

1264 Atomic Car Race    dp基本題.

1146 采藥               01背包 剩餘類dp

1355 The Bus            二維的最長上升子序列

1169 ACM(ACronymMaker)  給一些短語求按題意要求構成指定縮寫的方法數.

1163 Tour               歐幾裡德旅行商問題（吳文虎那本書p314）

1233 Necklace Decomposition 按題意分割字母.

1222 單詞選擇           在給定文章裡選出連續的一段包含最多的word且長度最短.

1211 商人的宣傳         求兩點間L步到達的方法數.

1197 Hotel              字元串含通用符的比對,記憶化搜尋.

1120 Walk Through the Forest 簡單無向圖,求節點1到節點2的按題意走法的方法數.

1091 Maximum Sum        求分兩個部分後的和最大.

1098 Marching in the Corp 給出部分偏序關系,求可能的排名方法數.

1049 Mondriaan          2*1跟1*1的磚鋪成2*n的走道的方法數.

1121 Tri Tiling         2*1的轉鋪成3*n的走道的方法數。

1019 Apple Tree         樹型dp,邊dfs邊更新最優值。

1138 尋寶之旅           同上。

1225 電子眼             樹+一邊的圖上求最小邊覆寫，樹型dp.

1327 Pinary             遞推求第k個pinary數。

1404 Hie with the Pie   狀态壓縮dp

1233 Necklace Decomposition 按題意分割字母.

1221 數字遊戲           n個數序列每個數每次會減少b[i]。取出m個數,求最大值.

1103 The Top-Code       字元串劃分dp,要求字典序輸出方案時的狀态表示方法。

1139 電路穩定性         遞歸處理括号對序列算電路不通機率.

1108 Online Selection   問答遊戲，n層k個回答拿了m分，求最大的回答0的個數.

1123 The Longest Walk   有向圖求任意起終點的無重複點的最長路，狀态壓縮dp

1033 City Road          求0,0走到n+1,m+1的最短路方法數，中間有一些障礙.

1176 Two Ends           二人從兩頭取數，對方貪心取大的，你盡量使得兩者的差大.

1413 Whac-a-Mole        打地鼠遊戲，求一定時間内能打到最多地鼠的方案。

1415  Honeycomb Walk    蜜蜂窩走N步回到出發地的方法數。

【二分法】

1137 河床 求一個最長的連續區間滿足其中的最小數和最大數之差不大于k。

1411 Pie  二分

【貪心】

1198 Substring          8個串排出最小字典序。（用ab<ba做比較函數排序）

1140 國王的遺産         砍不大于n/2個節點的最大樹枝

1134 積木分發           從小到大排序.

1172 Queens, Knights and Pawns 染色模拟

1193 Up the Stairs      搬箱子上樓梯.

【數學】

1302 Magic Square       奇數階的魔方構造

1125 Arnie versus the IRS 兩個日期間0-9數字出現次數統計，周末不計。

1200 Stick              奇數根木棍，不同種類的有偶數個，有一種隻有奇數個。異或

1251 Plinko             彈珠遊戲算機率

1258 It                 多項式求導

1224 速配遊戲           組合數學上經典的穩定婚姻問題。

1047 Super Snooker      連續的數和可否二分.

1448 Antimonotonicity   最長不單調子序列（f[0]>f[1]<f[2]>f[3]..）統計極點個數

1344 數列               某種規則的數列生成

1433 Optimal Parking    直接算

1259 Sum of Consecutive Prime Numbers 連續素數和

1240 Faulty Odometer    十進制數少了4的計數

1242 Suit Distribution  無聊計數

1239 Smallest Differencev 一些數位，組成差最小的兩個數

1231 The Embarrassed Cryptographer 兩個素數積，枚舉因子

1174 Square Count       數方塊數，容斥原理。

1214 信号分析           數列找規律求an=n的個數. 二進制表示時是回文。

1218 紀念郵票           同1209

1209 Sequence Sum Possibilities 求m分解成不同的連續整數和的方法數

1206 Stacking Cylinders 堆圓筒，解方程.

1203 The Cubic End      給一個1,3,7,9結尾的數求一個數的立方的尾部是原數

1199 GCD                求小于N且與N的GCD大于M的數個數.

1190 Reduced ID Number  找最小的數使得給出的所有數mod它的結果不同

1099 Packing Passengers 線性模方程

1119 Factstone Benchmark 求n!<=2^k的最大n. 兩邊取對數.

1412 Tour Guide         n個物體向各個方向做勻速運動。

1305 Who’s Winner      博弈題，找規律。

【模拟/其他】

1323 Switch text        字元串處理。

1122 Prerequisites      模拟統計學生選課。

1046 Plane Spotting     排序。

1097 LED Modding        排序。

1093 Air Express        枚舉。

1237 Paint Mix          黑白染料混合出指定灰階的染料。

1202 The Bank of Kalii  日期比較

1187 Laserbox           機器人運動模拟，dfs周遊。

1177 Take Your Vitamins 按要求做一些基本的資料統計。

1182 Context-Free Clock 鐘表時間和時針分針之間夾角的關系。

1100 Tennis Anyone      網球排名統計。

1110 ioi photos         模拟.統計

1128 DICE               判斷骰子是左手型還是右手型，模拟旋轉.(逆序可以做)

1129 ISBN               給定規律求ISBN最後一位.

1133 SPAM               輸出輸入字元串裡的合法email位址。

1401 Children of the Candy Corn 模拟左手規則走迷宮。

1438 Shopaholic         排序，隔三求和。

1306 Sorting Algorithm  基本的排序，輸出。

1205 brainf*ck          模拟解釋執行題目中定義的一種程式設計語言。 *************************程式設計題*************************sicily 1293, uva 100, pc 110101, 3n+1數鍊問題, 難度1sicily 1813 M進制數問題 sicily 1157 The hardest problem. 簡單大小比較，難度0sicily 1830 SZ Fibonacci Sequence, 遞歸函數, 難度 0sicily 1668 Score, 分支語句的使用, 難度0sicily 1147 誰拿了最多獎學金. 結構體、數組、分支，難度1sicily 1795 Table tennis, 幾何題，難度0 sicily 1798 Alice and Bob, 政策，難度1  sicily 1510 Mispelling, 字元串，難度0sicily 1561 PRIME Number, 難度1sicily 1007 To and Fro, 二維數組, 難度1sicily 1036 Crypto Columns, 二維數組,字元串,排序, 難度1*************************資料結構*************************sicily 1200 Stick. 簡單查找配對，或排序或用set，難度1sicily 1934 移動小球. 線性表，難度2sicily 1509 Rails. 難度2sicily 1768 雙棧排序sicily 1021 couples. 棧，難度2sicily 1006 Team Rankings, 棧與回溯, 難度1, 5!搜尋sicily 1443 Printer Queue, 基本隊列操作sicily 1210 二叉樹, 二叉樹周遊順序先後中轉換，挺經典的。sicily 1375 Balanced lineup, 哈希sicily 1194 Message Flood, 單詞查找, 排序後二分查找，或哈希或平衡二叉樹sicily 1022 Poor contestant Prob, 兩個堆*************************字元串相關*************************sicily 1027 MJ, Nowhere to Hide, 難度1, 直接比較字元串後排個序輸出sicily 1133 SPAM, 輸出輸入字元串裡的合法email位址。sicily 1323 Switch text, 字元串處理。sicily 1519 Longest Common Subsequence*************************排序和查找*************************sicily 1046 Plane Spotting. 排序. 難度1.sicily 1134 積木分發. 從小到大排序. 難度1.sicily 1795 Simple Sortsicily 1154 Easy sortsicily 1306 Sorting Algorithm. 難度1sicily 1351 Multi-key Sortingsicily 1628 Extended Normal Order Sortsicily 1438 Shopaholic, 排序，隔三求和, 難度1sicily 1046 Plane Spotting, 排序. 難度1sicily 1097 LED Modding, 排序*************************圖周遊*************************sicily 1155 Can I Post the letter 判斷兩點是否可達。（圖的周遊）sicily 1114 Food Cubes. 廣度優先周遊給3維空間圖染色。（dfs容易棧溢出）sicily 1156 Binary tree, 深搜, 指針, 樹的先序周遊, 難度1sicily 1034 forest, 森林的定義，求最大寬度與深度，深度優先周遊； 樹, 隊列與搜尋sicily 1424 獎金, 拓撲排序sicily 1350 Piggy banks 給出每個點出度為1的有向圖，求環的個數。（簡單）sicily 1308 Dependencies among Jobs, 圖的周遊*************************圖算法*************************sicily 1211 商人的宣傳, 難度1，有向圖矩陣乘法sicily 1031 Campus 單源最短路，dijkstrasicily 1090 Highways 最小生成樹sicily 1402 Panic Room 構圖求網絡最大流sicily 1326 Apple Tree, 建樹，求兩結點最近公共祖先。sicily 1303 Job Assignment 二分圖的最大權比對sicily 1423. 魔王bug的2色定理，最小割（用最大流求解）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 1002 Anti-Prime Sequences. 搜尋，回溯。難度2. sicily 1048 Inverso. 廣度優先搜尋BFS，二進制表示狀态判重。難度3sicily 1835 N Queens Problem. 搜尋，回溯。sicily 1444 Prime Path. 廣度優先搜尋sicily 1215 脫離地牢. 有限制的迷宮求兩人相遇的最小步驟。（廣度優先搜尋）sicily 1317 Sudoku. 數獨求解的個數。sicily 1180 Pasting Strings 給10個字元串，求一個排列使得某種權和最大，全排列搜尋。sicily 1024 Magic Island. 無向圖的最長路，深度優先搜尋DFS. 難度2sicily 1050 Numbers & Letters 回溯 DFS求5個數可否運算得到目标數, 否則輸出可得到的小于目标數的最大數.sicily 1135 飛越原野 最短時間過地圖，廣度優先搜尋.sicily 1107 Simple Puzzle 按題意搜尋，有可能有前置零，輸出排序.sicily 1150 簡單魔闆 廣度優先搜尋，全排列的hash函數設計sicily 1151 魔闆 廣度優先搜尋，全排列的hash函數設計sicily 1152 簡單的馬周遊問題，迷宮問題的可行性剪枝.sicily 1153 馬周遊問題。 同上，擴充狀态節點的時候按目标函數值排序。sicily 1378 八數位問題. 啟發式搜尋。*************************動态規劃*************************sicily 1001 Alphacode. dp基本題. 難度2sicily 1049 Mondriaan. 2*1跟1*1的磚鋪成2*n的走道的方法數.sicily 1264 Atomic Car Race. dp基本題.sicily 1342 開心的金明. 背包dpsicily 1146 采藥. 01背包, 剩餘類dpsicily 1419 On the run(牛奶快遞). dpsicily 1019 Apple Tree. 樹型dpsicily 1123 The Longest Walk 有向圖求任意起終點的無重複點的最長路，狀态壓縮dp*************************二分法/分治*************************sicily 1017 Rate of Return. 求解方程，二分. 難度2sicily 1211 商人的宣傳. 求兩點間L步到達的方法數.sicily 1137 河床. 求一個最長的連續區間滿足其中的最小數和最大數之差不大于k。sicily 1411 Pie. 二分*************************貪心*************************sicily 1198 Substring 8個串排出最小字典序。（用ab < ba做比較函數排序） sicily 1140 國王的遺産 砍不大于n/2個節點的最大樹枝sicily 1172 Queens, Knights and Pawns 染色模拟sicily 1193 Up the Stairs. 搬箱子上樓梯.*************************算術與代數*************************sicily 1813 M進制數問題. 進制轉換，難度1sicily 1201 01000001. 大整數二進制加法sicily 1240 Faulty Odometer. 十進制數少了4的計數sicily 1029 Rabbit. 高精度求和，難度2sicily 1020 Big Integer. 高精度數求模，難度2sicily 1381 a*b. 高精度乘法. 難度2*************************其他*************************sicily 1280 Permutationsicily 1134 積木分發, 貪心:從小到大排序sicily 1139 電路穩定性, 遞歸處理括号對序列算電路不通機率sicily 1149 等價表達式, 判斷表達式是否等價（遞歸求解）sicily 1211 商人的宣傳,分治, 求兩點間L步到達的方法數sicily 1028 Hanoi Tower Sequence, 梵塔問題 -> 分治，歸納 -> 有意思但要留意其資料規模較大,可以遞歸或疊代做.