Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: Uva Problem Set Volume 1: 100-199 
发信站: 哈工大紫丁香 (2002年08月13日18:53:50 星期二), 站内信件

Uva Problem Set Volume 1: 100-199
题号名称
 正确率
 算法
 来源
 备注

100 The 3n + 1 problem
 24.9 %
 模拟+记忆化
 DUKE90


101 The Blocks Problem
 29.9 %
 模拟
 DUKE90


102 Ecological Bin Packing
 38.4 %
 枚举
 DUKE90


103 Stacking Boxes
 40.9 %
 排序+DP
 DUKE90


104 Arbitrage
 16.7 %
 Floyd-Warshall
 DUKE90


105 The Skyline Problem
 41.5 %
 自左向右扫描
 DUKE90


106 Fermat vs. Pythagoras
 10.4 %
 数学+枚举
 DUKE91
 推荐

107 The Cat in the Hat
 12.4 %
 数学+枚举+高精度
 DUKE91
 推荐

108 Maximum Sum
 41.0 %
 DP, O(N^2)
 DUKE91


109 SCUD Busters
 29.3 %
 几何综合题
 DUKE91


110 Meta-Loopless Sorts
 11.6 %
 有趣的排序，字符串综合题
 DUKE91
 推荐

111 History Grading
 26.1 %
 DP,注意题目理解
 DUKE91


112 Tree Summing
 19.1 %
 简单的回溯搜索。注意输入
 DUKE92


113 Power of Cryptography
 31.2 %
 用double可以直接通过!!
 DUKE92


114 Simulation Wizardry
 22.7 %
 模拟
 DUKE92


115 Climbing Trees
 33.8 %
 用父亲表式法建树
 DUKE92


116 Unidirectional TSP
 34.7 %
 简单的DP
 DUKE92


117 The Postal Worker Rings Once
 53.4 %
 Dijkstra
 DUKE92


118 Mutant Flatworld Explorers
 36.9 %
 模拟
 DUKE93


119 Greedy Gift Givers
 37.2 %
 模拟。注意输入
 DUKE93


120 Stacks of Flapjacks
 51.3 %
 逐个归位
 DUKE93


121 Pipe Fitters
 39.7 %
 数学。注意有一边小于1的情况
 DUKE93


122 Trees on the level
 26.2 %
 BFS。注意输入的处理。
 DUKE93


123 Searching Quickly
 38.9 %
 字符串处理。直接做就可以了
 DUKE93


124 Following Orders
 45.4 %
 拓扑排序
 DUKE93


125 Numbering Paths
 33.4 %
 Floyd算法变形
 DUKE93


126 The Errant Physicist
 40.4 %
 模拟
 NZ89
 推荐给初学者

127 ``Accordian'' Patience
 17.3 %
 模拟。可以用链表。你的程序快吗？
 NZ89
 推荐

128 Software CRC
 32.0 %
 同余
 NZ89


129 Krypton Factor
 33.5 %
 回溯。注意优化判断算法
 NZ89


130 Roman Roulette
 39.1 %
 JOSEPH问题的一种。模拟
 NZ89


131 The Psychic Poker Player
 49.5 %
 模拟
 NZ89


132 Bumpy Objects
 40.8 %
 凸包+角度判断（可以用余弦定理）
 NZ90


133 The Dole Queue
 58.1 %
 模拟
 NZ90


134 Loglan-A Logical Language
 22.8 %
 扫描+替换
 NZ90
 推荐

135 No Rectangles
 9.5 %
 数学方法
 NZ90
 强烈推荐

136 Ugly Numbers
 37.6 %
 堆
 NZ90


137 Polygons
 24.6 %
 多边形算法
 NZ90


138 Street Numbers
 55.0 %
 数学方法
 NZ90
 推荐给初学者

139 Telephone Tangles
 2.5 %
 很阴险的模拟题
 NZ90


140 Bandwidth
 40.9 %
 很不错的搜索题目
 NZ91
 推荐

141 The Spot Game
 48.6 %
 用HASH
 NZ91


142 Mouse Clicks
 66.1 %
 模拟
 NZ91


143 Orchard Trees
 3.3 %
 几何问题。可以用分层扫描
 NZ91


144 Student Grants
 52.5 %
 模拟
 NZ91


145 Gondwanaland Telecom
 28.3 %
 模拟.注意时间跨越一天的情况。
 NZ91


146 ID Codes
 49.3 %
 这个有标准算法的
 NZ91


147 Dollars
 39.1 %
 DP.注意输入的时候要四舍五入
 NZ91


148 Anagram checker
 34.8 %
 简单的搜，不过要程序高效也不容易
 NZ92


149 Forests
 29.9 %
 不错的几何题目
 NZ92
 强烈推荐

150 Double Time
 17.9 %
 日期模拟
 NZ92


151 Power Crisis
 61.5 %
 模拟
 NZ92
 推荐

152 Tree's a Crowd
 49.7 %
 用分治法可以加速
 NZ92


153 Permalex
 37.9 %
 递推
 NZ92


154 Recycling
 55.0 %
 枚举
 NZ92


155 All Squares
 70.2 %
 递归或者迭代
 NZ92


156 Ananagrams
 46.5 %
 用二分检索树可以提高效率
 NZ93


157 Route Finding
 26.2 %
 dijkstra
 NZ93


158 Calendar
 15.9 %
 模拟
 NZ93


159 Word Crosses
 50.8 %
 简单的搜索
 NZ93


160 Factors and Factorials
 39.8 %
 简单的数学计算
 NZ93


161 Traffic Lights
 32.9 %
 虽然是模拟，但是弄不好效率会很低
 NZ93
 推荐

162 Beggar My Neighbour
 41.4 %
 扑克模拟
 NZ93


163 City Directions
 20.6 %
 不错的模拟题
 NZ93
 强烈推荐

164 String Computer
 21.8 %
 除了DP，还有另外一种不错的方法...
 SP91
 推荐

165 Stamps
 25.3 %
 就是分区联赛那道题目。搜索+DP
 SP91


166 Making Change
 33.6 %
 递推
 SP91


167 The Sultan's Successors
 55.0 %
 预处理+搜索
 SP91


168 Theseus and the Minotaur
 52.6 %
 模拟
 SP91


169 Xenosemantics
 8.7 %
 很不错的字符串处理题目
 SP91
 推荐

170 Clock Patience
 46.5 %
 模拟
 SP91


171 Car Trialling
 18.7 %
 扫描+替换
 SP91


172 Calculator Language
 22.7 %
 一般的表达式求值
 SP92


173 Network Wars
 3.1 %
 又一道很阴险的模拟题目
 SP92
 推荐

174 Strategy
 31.7 %
 字符串处理+表达式处理
 SP92
 推荐

175 Keywords
 36.9 %
 字符串处理
 SP92


176 City Navigation
 19.7 %
 算法是BFS，不过预处理比较繁
 SP92


177 Paper Folding
 59.2 %
 递推
 SP92
 推荐给初学者做

178 Shuffling Patience
 42.8 %
 扑克模拟
 SP92


179 Code Breaking
 21.5 %
 枚举
 SP93


180 Eeny Meeny
 23.9 %
 模拟
 SP93


181 Hearts
 50.6 %
 模拟
 SP93


182 Bonus Bonds
 51.1 %
 分段再递推
 SP93
 推荐给初学者做

183 Bit Maps
 30.3 %
 直接做
 SP93


184 Laser Lines
 42.5 %
 注意利用坐标为整数的条件加速
 SP93
 推荐

185 Roman Numerals
 57.8 %
 模拟+搜索
 SP93


186 Trip Routing
 42.9 %
 dijkstra
 SCNA89


187 Transaction Processing
 46.7 %
 模拟
 SCNA89


188 Perfect Hash
 62.0 %
 模拟
 SCNA89


189 Pascal Program Lengths
 30.4 %
 比较麻烦的字符串处理
 SCNA89


190 Circle Through Three Points
 41.9 %
 如果用待定系数法，注意不要除0。
 SCNA89


191 Intersection
 15.3 %
 用叉积比较简单
 SWERC95


192 Synchronous Design
 31.0 %
 求关键路径
 SWERC95


193 Graph Coloring
 26.5 %
 求最大独立集。看你搜索够不够快
 SWERC95
 推荐给初学者做

194 Triangle
 12.4 %
 算法很简单但又很麻烦很无奈的题目
 SWERC95
 强烈推荐

195 Anagram
 7.8 %
 应该是很简单的，不知道为什么错
 SWERC95


196 Spreadsheet
 22.6 %
 不断的计算可以算出的值
 SWERC95


197 Cube
 3.8 %
 很不错的搜索题目
 SWERC95
 强烈推荐

198 Peter's Calculator
 19.8 %
 挺麻烦的表达式处理
 SWERC95
 推荐

199 Partial differential equations
 18.4 %
 只要题目理解清楚了，还是很容易的
 SWERC95
 推荐给初学者做

--
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]