プログラミングテーマ分類(編集)
18797 ワード
1.
2.
3.
4.
5.
6.
7. ： ，
8. /
9. /
10.
11.
12.
13.
14.
15. , ,
【 】
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 1232 Electrical Outlets. ， 0
sicily 1388 Quicksum. ， 0
sicily 1324 Score. ， 0
sicily 1157 The hardest problem. ， 0
sicily 1147 . 、 、 ， 1
sicily 1051. Biker's Trip Odomete.
sicily 1795. Table tennis. .
sicily 1798. Alice and Bob. . 1
sicily 1087 Funny game. . 1
sicily 1510 Mispelling, , 0
sicily 1500 Prime Gap. . 1.
sicily 1561 PRIME Number. n . 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 . 2.
sicily 1325 Digit Generator. . 0
sicily 1154 easy sort. . 0
sicily 1636. show me the money. . 0
sicily 1814 . . 1.
sicily 1815
sicily 1816
sicily 1817
sicily 1818
sicily 1765 . ， 。
【 】
/* Data Structure:
Stacks and Queues
Binary Search Tree
Hash Table
Dictionaries (set, map)
Priority Queues
Disjoint Sets
tries
Suffix Trees
B-Trees
Kd-Trees
Skip-Lists
Balanced Trees: AVL Tree, Splay Tree, Red-Black Tree
*/
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 1052. Candy Sharing Game. .
sicily 1200 Stick. ， set,multiset,map， 1
sicily 1486 . map 。 2.
sicily 1819 Matrix. ， bitset vector。 2
sicily 1194 Message Flood. 。 , set, trie 2
sicily 1931 . ， 2
sicily 1003. Hit or Miss. ， . 2.5
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 . ， . ，BFS. 3
sicily 1082 manager. ，
. 3.
sicily 2543. 。 。 。
sicily 1490. Tree Grafting. ， ， DFS 。
sicily 1838. Sub Tree. m-ary ， .
sicily 1875. Small tree. .
sicily 1063. Who's the Boss. ， ，
sicily 1042. Squadtrees.
sicily 1088. Cows. ， [S,E] S ，S E ， E ， 。
sicily 1375 Balanced Lineup.
sicily 1149 . （ ）
sicily 1156. Binary tree. ，
sicily 1310. Right-Heavy Tree. ， ； ， O(N) O(NlogN)。
sicily 1426 Phone List. ，trie 。
sicily 1686. Happy Children's Day.
sicily 1136 . n m 。 /RMQ
sicily 1092 Stars in Your Window .
【 】
/*
String Problems:
String Matching
Approximate String Matching
Text Compression
Cryptography
Longest Common Substring/Subsequence
Shortest Common Superstring
*/
pc 110302, uva 10010, Where's Waldorf,
pc 110304, uva 850, Crypt Kicker II,
pc 110306 File Fragmentation,
pc 110307 Doublets,
sicily 1753. .
sicily 1129. ISBN . ISBN .
sicily 1133. SPAM. email 。
sicily 1323. Switch text. 。
sicily 1035. DNA matching. 2.
sicily 1299. Academy Award. . 2.
sicily 1282. Computer Game. . KMP. 3.
【 】
/*
Sorting: Insertion Sort, Selection Sort, Heapsort, Mergesort, Quicksort, Counting Sort, Bucket Sort
Searching: Sequence Search, Binary Search
Median and Selection
*/
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 1046 Plane Spotting. . 2.
sicily 1097 LED Modding. .
sicily 1134 . . 1.
sicily 1154. Easy sort. . 1.
sicily 1198 Substring. ， . 1.
sicily 1252 Defining Moment. .
sicily 1306. Sorting Algorithm. ,O(nlogn) . 2.
sicily 1341 . n ， 。 1.
sicily 1351. Multi-key Sorting. . 2.
sicily 1438. Shopaholic. ， . 1.
sicily 1482. . key . 2.
sicily 1532. Binary Search. 4.
sicily 1628. Extended Normal Order Sort. 4.
sicily 1641. Binary Searchable. 2.
sicily 1775. Simple Sort. key . 3.
sicily 1930. . . 2.
【 】
/* Graph Travasal
Breadth-First Search and Applications: Connected Components, Two-Coloring Graphs,
Depth-First Search and Applications: Finding Circles, Articulation Vertices ,
Topological Sorting, Strongly Connected Componensts,
*/
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 1424 .
sicily 1030 Task Scheduling. . 4
sicily 1155 Can I Post the letter 。（ ）
sicily 1308 Dependencies among Jobs. N ， ， ， . BFS. 2
sicily 1034 Forest. ， .
sicily 1068. Euro Efficiency. 6 ， 100 . . 2.
sicily 1114 Food Cubes 3 。（dfs ）
sicily 1187 Laserbox N×N ， M ， ， 90 。 ，
， ， “0 0”。dfs 。
sicily 1304. Delivering Food. ， . 4
【 】
/*Graph Problems
1. Polynomial-Time Problems
Connected Components
Topological Sorting
Minimum Spanning Tree
Shortest Path
Transitive Closure and Reduction
Mathcing
Eulerian Cycle/Chinese Postman
Edge and Vertex Connectivity
Network Flow
2. Hard Problems
Clique
Independent Set
Vertex Cover
Traveling Salesman Problem
Hamitonian Cycle
Graph Partition
Vertex Coloring
Edge Coloring
Graph Isomorphism
Steiner Tree
Feedback Edge/Vertex Set
*/
pc 111001, uva 10034, Freckles, 2
pc 111002, uva 10054, The Necklace, 3, (USE UVA JUDGE -- NOT PC JUDGE)
pc 111006, uva 10199, Tourist Guide, 3
pc 111007, uva 10249, The Grand Dinner, 4, (USE UVA JUDGE -- 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 Problem Setter, 3
sicily 1031. Campus. ，dijkstra. 3。
sicily 1321. Robot. ，dijkstra. 3。
sicily 1090. Highways. 。 2。
sicily 1402. Panic Room.
sicily 1303. Job Assignment.
sicily 1684. Christmas. ， ，
sicily 1192 Guardian of Decency ， 。
sicily 1211. . ， ，O(n^3*logL)； ,O(n*m*L)。
sicily 1350. Piggy banks. 1 ， . ， 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 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 1019. Apple tree. DFS dp.
sicily 1835 N Queens Problem. ， 。
sicily 1444 Prime Path
sicily 1428. B Baby Climber( ). ，BFS
sicily 1048 Inverso. BFS， ; DFS。 3
sicily 1317 Sudoku. 。
sicily 1171 The Game of Efil 2^16 dfs
sicily 1219 . ，min-max
sicily 1215 . 。（ ）
sicily 1180 Pasting Strings 10 ， ， 。
sicily 1024 Magic Island. . BFS DFS. 2
sicily 1050 Numbers & Letters DFS 5 , .
sicily 1135 ， .
sicily 1107 Simple Puzzle ， ， .
sicily 1150 . ，
sicily 1151 .
sicily 1515 C.
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 1782. Knapsack. 01 .
sicily 1342. . 01 .
sicily 1146. . 01 , sicily 1342.
sicily 1077. Case Machine. .
sicily 1750. . .
sicily 1346. . .
sicily 1091. Maximum Sum. m .
sicily 1888. Circular Sequence. MAX， ， MIN， MAX-MIN ， MAX .
sicily 1564. HOUSING. .
sicily 1902. Counting Problem. .
sicily 1060. Bridging Signals. .
sicily 1685. Missile. . ，O(n^2).
sicily 1448. Antimonotonicity. （f[0]>f[1]<f[2]>f[3]..） . ， O(n) .
sicily 1345. . , dp.
sicily 1176 Two Ends. ， ， . dp.
sicily 1563. GECKO. dp.
sicily 1822. Fight Club. dp.
sicily 1326. 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 1225. . + . dp.
sicily 1898. Tree. ， ， ， ， . dp.
sicily 2681. Tree. ， 。 ， （ ， ）。 . dp.
sicily 1404 Hie with the Pie. dp.
sicily 1123. The Longest Walk. ， dp.
sicily 1148. . ， .
sicily 1103 The Top-Code. dp, .
sicily 1001. Alphacode. dp .
sicily 1010. Zipper. dp.
sicily 1011. Lenny's Lucky Lotto. dp.
sicily 1049. Mondriaan. 2*1 1*1 2*n %10. DP
sicily 1057. Rhyme Schemes. dp.
sicily 1073. Pearls. dp.
sicily 1081. Game. dp.
sicily 1108. Online Selection. ，n k m ， 0 .
sicily 1121. Tri Tiling. 2*1 3*n . DP.
sicily 1138. . dp.
sicily 1158. Pick numbers. M*N ， （1，1）， （M，N）， ， ，
. DFS. 2
sicily 1166. Computer Transformatation. dp.
sicily 1211. . dp. 3
sicily 1221. . n b[i], m , .
sicily 1222. . word , hash .
sicily 1264. Atomic Car Race. dp .
Sicily 1373. Cows Of The Round Table. dp.
sicily 1274. Pascal's Travels. dp.
sicily 1419. On the run. . dp.
sicily 1687. Permutation. dp.
sicily 1828. Minimal. dp.
【 / / 】
sicily 1355 The Bus. ， ， STL map .
sicily 1169 ACM(ACronymMaker) .
sicily 1163 Tour. （ p314）
sicily 1233 Necklace Decomposition .
sicily 1197 Hotel , .
sicily 1120 Walk Through the Forest , 1 2 .
sicily 1091. Maximum Sum ， .
sicily 1098 Marching in the Corp , .
sicily 1327 Pinary k Pinary 。
sicily 1233 Necklace Decomposition .
sicily 1139 .
sicily 1033 City Road 0,0 n+1,m+1 ， .
sicily 1413 Whac-a-Mole ， 。
sicily 1415 Honeycomb Walk N 。
【 】
sicily 1017 Rate of Return. ， . 2
sicily 1211 L .
sicily 1137 . k。
sicily 1376. Monthly Expense. N ， M ， . ， . 3
sicily 1441 Pie
sicily 1454. Pseudoprime numbers. ， ， 。 3
【 】
sicily 1739. Helpful Paper. .
sicily 1717. Computer. . + .
sicily 1198 Substring 8 。（ ab<ba ）
sicily 1140 . n/2
sicily 1172 Queens, Knights and Pawns
sicily 1193 Up the Stairs .
【 】
/*
Numerical Problems:
Solving Linear Equations
Bandwidth Reduction
Matrix Multiplication
Determinants and Permantents
Constrained and Unconstrined Optimization
Linear Programing
Random Number Generation
Factoring and Primality Testing
Arbitrary-Precision Arithmetic
Kanpsack Prpblem
Discret Fourier Transform
*/
/*
： ，
： ，
*/
pc 110502 Reverse and Add
pc 110503 The Archeologists' Dilemma
pc 110504 Ones
pc 110505 A multiplication game
pc 110702 Carmichael Numbers (USE UVA JUDGE -- NOT PC JUDGE)
pc 110704 Factovisors
pc 110707 Marbles
pc 110708 Repackaging
sicily 1040. Polly Nomials. . 2
sicily 1813 M . ， 1
sicily 1201 01000001.
sicily 1159 Sum. .
sicily 1029 Rabbit. ， ， 2
sicily 1020 Big Integer. ， 2
sicily 1381 a * b. . 2
sicily 1240 Faulty Odometer. 4
sicily 1294. . a,b,c (a^b) mod c.
sicily 1422. Table Tennis. ， 。 a b
sicily 1363. Semi-prime H-numbers. H-numbers: 1, 5, 9, 13, 17, 21,25,29,…;
H-Prime: 1×h h， 5,9,13,17,21,29,…;
H-Composites:25, 45, 65, 81, 85, …;
H-SimiPrime: H-Prime ， 25, 45, 65, 81, 85, 105, 117, …;
125 ;
N， 1-N . 2
【 】
/*
Combinatorial Problems:
Median and Selection
Generating Permutations
Generating Subsets
Generating Partitions
Generating Graphs
Generating Calculations
Job Scheduling
Satisfiability
*/
pc 110603 Counting
pc 110604 Expressions
pc 110606 The Priest Mathematician
pc 110607 Selfdescribing Sequence
sicily 1370. How many 0's?. 0.
sicily 1089 Farey Sequence. Farey Sequence , ： a = (a1^p1)*(a2^p2)...(ak^pk), a1,...,ak ， F(a)=a*(1-1/a1)*(1-1/a2)*...*(1-1/ak). 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 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)。
sicily 1009. Mersenne Composite N. .
【 】
sicily 1251 Plinko
sicily 1258 It
sicily 1047 Super Snooker .
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 1052. Candy Sharing Game. .
sicily 1122 Prerequisites 。
sicily 1093 Air Express 。
sicily 1237 Paint Mix 。
sicily 1202 The Bank of Kalii
sicily 1177 Take Your Vitamins 。
sicily 1182 Context-Free Clock 。
sicily 1100 Tennis Anyone 。
sicily 1110 ioi photos .
sicily 1128 DICE ， .( )
sicily 1401 Children of the Candy Corn 。
sicily 1205 brainf*ck
【 】
/* Computatinal Geometry:
Robust Geometric Primitives
Convex Hull
Triangulation
Voronoi Diagrams
Nearest Neighbor Search
Range Search
Point Location
Intersection Detection
Bin Packing
Medial-Axis Transform
Polygon Partitioning
Simplifying Polygons
Sharpe Similarity
Motion Planning
Maintaining Line Arrangements
Minkowski Sum
*/
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 . 2
sicily 1045 Space Management ， .
sicily 1145 O(n)
sicily 1223 ，
sicily 1216
sicily 1118 War on Weather 。
【 】
sicily 1278. Soldiers
sicily 1006. Team Rankings. 5 ABCDE .