プログラミングテーマの分類

15199 ワード

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[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