《算法竞赛入门经典——训练指南》第一章—算法设计基础

这是第一章的所有例题和课后习题,寒假前的任务,尽量刷吧。。。

问题求解策略

例题

例题 1 UVa11292 The Dragon of Loowater 排序后用贪心法
例题 2 UVa11729 Commando War 用贪心法求最优排列;用“相邻交换法”证明正确性
例题 3 UVa11300 Spreading The Wealth 用代数法进行数学推导;中位数
例题 4 LA3708 Graveyard 推理;参考系
例题 5 UVa10881 Piotr's Ants 等效变换;排序
例题 6 LA2995 Image is Everything 三维坐标系;迭代更新
例题 7 UVa11464 Even Party 部分枚举;递推
例题 8 LA3401 Colored Cubes 部分枚举;贪心
例题 9 UVa11210 Chinese Mahjong 回溯法;以中国麻将为背景
例题 10 UVa11384 Help is needed for Dexter 问题转化;递归
例题 11 UVa10795 A Different Task 汉诺塔问题;递归
例题 12 LA3971 Assemble 二分法;贪心
例题 13 LA3635 Pie 二分法
例题 14 UVa11520 Fill the Square 求字典序最小的解;贪心
例题 15 LA3902 Network 树上的最优化问题;贪心
例题 16 LA3177 Beijing Guards 二分法;贪心

习题

UVa11636 Hello World!
UVa11039 Building Designing
LA3213 Ancient Cipher
LA3602 DNA Consensus String
UVa10970 Big Chocolate 不需要动态规划
UVa10340 All in All
UVa10382 Watering Grass 经典模型;贪心
UVa10905 Children's Game 贪心。容易想错!建议编程并提交 题解1
LA4254 Processor 二分法
UVa11627 Slalom 二分法
UVa11134 Fabled Rooks 经典问题的变形
UVa11100 The Trip, 2007
LA4725 Airport
LA4850 Installations
LA3266 Tian Ji - The Horse Racing 有多种方法
UVa11389 The Bus Driver Problem 有多种方法
LA4094 Wonder Team
LA3303 Songs 相邻交换法
LA2757 Supermarket 经典问题
LA3507 Keep the Customer Satisfied 经典问题的变形
LA4234 Ugly Windows 注意细节
LA4238 Priest John's Busiest Day 认真分析题目
LA4636 Cubist Artwork 有趣的题目;逻辑推理
LA4253 Archery 枚举。注意特殊情况和精度
LA3667 Ruler 搜索
LA5693 Compress the String 搜索。需要优化
LA5704 Yummy Triangular Pizza 回溯法。https://oeis.org/A006534
UVa10825 Anagram andMultiplication 枚举(需要猜想)
UVa10639 Square Puzzle 回溯法。注意细节
LA3403 Mobile Computing 枚举二叉树
LA3406 Bingo 注意枚举方式
LA3621 Power Calculation 经典的搜索题目;注意优化
LA2108 Houses Divided 搜索;需要优化
LA5842 Equipment 需认真分析题目
LA5844 Leet 以“火星文”为背景的题目
LA4644 Hobby on Rails 比较繁琐的搜索题目

高效算法设计

例题

例题 17 UVa11462 Age Sort 排序后用贪心法
例题 18 UVa11078 Open Credit System 扫描、维护最大值
例题 19 UVa11549 Calculator Conundrum Floyd判圈算法
例题 20 LA3905 Meteor 线性扫描;事件点处理
例题 21 LA2678 Subsequence 线性扫描;前缀和;单调性
例题 22 LA3029 City Game 递推;扫描法
例题 23 LA3695 Distant Galaxy 枚举;线性扫描
例题 24 UVa10755 Garbage heap 前缀和、降维、递推
例题 25 LA2965 Jurassic Remains 中途相遇法

习题

LA2963 Hypertransmission 扫描;维护信息
UVa10827 Maximum sum on a torus 前缀和;降维
UVa10125 Sumsets 中途相遇法
UVa10763 Foreign Exchange 快速检索
UVa10391 Compound Words 字符串检索;哈希表
UVa11054 Wine trading in Gergovia 扫描法
LA4726 Average 树形结合或者单调队列
LA4851 Restaurant
LA4950 Selling Land
LA4356 Fire-Control System 扫描法
LA2689 Cricket Field 在W*H网格里找一个最大空正方形
LA5052 Genome Evolution
LA3716 DNA Regions 利用数学变形或者数形结合
LA4629 Knowledge for the masses
LA4621 Cav
LA3693 Balancing the Scale 用空间换时间 题解1
LA4294 Shuffle 有多种方法
LA5848 Soju
LA4062 You are around me ...
原文地址:https://www.cnblogs.com/pony1993/p/2766949.html