算法竞赛入门经典经典例题及习题题解

Github仓库
有些例题没找到完全相同的题目，找了类似的。

文章目录

算法竞赛入门经典第一版

第5章 基础题目选解

5.1 字符串

ExampleProblemSolution
5.1.1 WERTYUUVa 10082 - WERTYUC++
5.1.2 TeX括号UVa 272 - TEX QuotesC++
5.1.3 周期串UVa 455 - Periodic StringsC++

5.2 高精度计算

ExampleProblemSolution
5.2.1 小学生算术UVa 10035 - Primary ArithmeticC++
5.2.2 阶乘的精确值UVa 623 - 500!C++

5.3 排序与检索

ExampleProblemSolution
5.3.1 6174问题NYOJ 57 6174问题C++
5.3.2 字母重排UVa 642 - Word AmalgamationC++

5.4 数学基础

ExampleProblemSolution
5.4.1 Cantor的数表UVa 264 - Count on CantorC++
5.4.2 因子和阶乘UVa 160 - Factors and FactorialsC++
5.4.3 果园里的树UVa 143 - Orchard TreesC++
5.4.4 多少块土地UVa 10213 - How Many Pieces of Land ?C++/Java

第六章 数据结构基础

6.1 栈和队列

ExampleProblemSolution
6.1.1 卡片游戏UVa 10935 - Throwing cards away IC++
6.1.2 铁轨UVa 514 - RailsC++

6.2 链表

ExampleProblemSolution
6.2.1 移动小球NOJ 1099 移动小球C++

6.3 二叉树

ExampleProblemSolution
6.3.1 小球下落UVa 679 - Dropping BallsC++
6.3.2 层次遍历UVa 122 - Trees on the levelC++
6.3.3 二叉树重建UVa 536 - Tree RecoveryC++

6.4 图

ExampleProblemSolution
6.4.1 黑白图像UVa 572 - Oil DepositsC++
6.4.2 走迷宫POJ 3984 迷宫问题C++
6.4.3 拓扑排序HDUOJ 1285 确定比赛名次C++
6.4.4 欧拉回路POJ 1041 John’s tripC++

第七章 暴力求解法

7.1 简单枚举

ExampleProblemSolution
7.1.1 除法UVa 725 - DivisionC++
7.1.2 最大乘积UVa 11059 - Maximum ProductC++
7.1.3 分数拆分UVa 10976 - Fractions Again?!C++
7.1.4 双基回文数OpenJudge 4831 双基回文数C++

7.2 枚举排列

ExampleProblemSolution
7.2.1 生成1~n的排列/7.2.2 生成可重集的排列UVa 10098 - Generating FastC++
7.2.4 下一个排列LeetCode 31. Next PermutationC++

7.3 子集生成

ExampleProblemSolution
7.3 子集生成POJ 2718 Smallest DifferenceC++

7.4 回溯法

ExampleProblemSolution
7.4.1 八皇后问题UVa 750 - 8 Queens Chess ProblemC++
7.4.2 素数环UVa 524 - Prime Ring ProblemC++
7.4.3 困难的串UVa 129 - Krypton FactorC++
7.4.4 带宽UVa 140 - BandwidthC++

7.5 隐式树的遍历

ExampleProblemSolution
7.5.1_1 最优程序POJ 1480 Optimal ProgramsC++
7.5.1_2 埃及分数UVa 12558 - Egyptian Fractions (HARD version)C++
7.5.2 倒水问题UVa 10603 - FillC++
7.5.3 八数码问题Vijos 1360 八数码问题C++

第八章 高效算法设计

8.1 算法初步分析

ExampleProblemSolution
8.1 最大连续和HDUOJ 1003 Max SumC++

8.2 再谈排序与检索

ExampleProblemSolution
8.2.1_1 归并排序LintCode 463. Sort IntegersC++
8.2.1_2 逆序对数POJ 1804 BrainmanC++
8.2.2 快速排序SJTUOJ 1525. 第K小的数C++
8.2.3 二分查找LintCode 457. Classical Binary SearchC++

8.4 递归与分治

ExampleProblemSolution
8.3.1 棋盘覆盖问题NYOJ 45 棋盘覆盖C++
8.3.2 循环日程表问题NoneOJ 1 Cycle ScheduleC++
8.3.3 巨人与鬼UVa 1411 - AntsC++
8.3.4 非线性方程求根UVa 10341 - Solve ItC++
8.3.5 最大值最小化UVa 714 - Copying BooksC++

8.3 贪心法

ExampleProblemSolution
8.4.1 最优装载问题NoneOJ 2 Optimal LoadingJava
8.4.2 部分背包问题NoneOJ 3 Partial BagJava
8.4.3 乘船问题NYOJ 71 独木舟上的旅行C++
8.4.4 选择不相交区间NOJ 1269 区间相交问题Java
8.4.5 区间选点问题UVa 10148 - AdvertisementC++
8.4.6 区间覆盖问题NoneOJ 4 Interval CoverageC++
8.4.7 Huffman编码NoneOJ 5 CodingC++

第九章 动态规划初步

9.1 数字三角形

ExampleProblemSolution
9.1 数字三角形POJ 1163 The TriangleJava

9.2 DAG上的动态规划

ExampleProblemSolution
9.2_1 嵌套矩形NYOJ 16 矩形嵌套C++
9.2_2 硬币问题Liuser’s OJ 725 硬币问题C++

9.3 0-1背包问题

ExampleProblemSolution
9.3_1 物品无限的背包问题HDUOJ 1248 寒冰王座C++
9.3_2 0-1背包问题HDUOJ 2602 Bone CollectorC++

9.4 递归结构中的动态规划

ExampleProblemSolution
9.4.1 表达式上的动态规划UVa 348 - Optimal Array Multiplication SequenceC++
9.4.2 凸多边形上的动态规划UVa 1331 - Minimax TriangulationC++
9.4.3 树上的动态规划UVa 1220 - Party at Hali-BulaC++

9.5 集合上的动态规划

ExampleProblemSolution
9.5 集合上的动态规划UVa 10911 - Forming Quiz TeamsC++

第10章 数学概念与方法

10.1 数论初步

ExampleProblemSolution
10.1.1 除法表达式Lutece 469 除法表达式C++
10.1.2 无平方因子的数HDUOJ 3826 Squarefree numberC++
10.1.3 直线上的点POJ 1061 青蛙的约会C++
10.1.4_1 大整数取模NoneOJ 6 Big Int ModuleC++
10.1.4_2 幂取模NoneOJ 7 Power ModuleC++
10.1.4_3 模线性方程POJ 2142 The BalanceC++

10.2 排列与组合

ExampleProblemSolution
10.2.1 无关的元素UVa 1635 - Irrelevant ElementsC++
10.2.2_1 约数的个数UVa 294 - DivisorsC++
10.2.2_2 小于n且与n互素的个数UVa 10820 - Send a TableC++
10.2.4 离散概率初步LightOJ 1104 Birthday ParadoxC++

10.3 递推关系

ExampleProblemSolution
10.3.1 汉诺塔OpenJudge_Bailian 4147 HanoiC++
10.3.2 Fibonacci数列51Nod-1242 斐波那契数列的第N项C++
10.3.3 Catalan数UVa 991 - Safe SalutationsC++
10.3.4 危险的组合UVa 580 - Critical MassC++
10.3.5 统计n-k中特殊集的数目入门OJ 1377 N-K集合C++

第11章 图论模型与算法

11.1 再谈树

ExampleProblemSolution
11.1.1 无根树转有根树NYOJ 20 吝啬的国度派生类可以访问基类中的protectedC++
11.1.2 表达式树POJ 1686 Lazy Math InstructorC++
11.1.3 最小生成树UVa 10034 - FrecklesC++
11.1.4 并查集HDUOJ 1863 畅通工程C++

11.2 最短路问题

ExampleProblemSolution
11.2.1-3 Dijkstra算法HDUOJ 2544 最短路C++
11.2.4 Bellman-Ford算法POJ 3259 WormholesC++

11.3 网络流初步

ExampleProblemSolution
11.3.2 增广路算法HDUOJ 1532 Drainage DitchesC++
11.3.3 最小割最大流定理HDUOJ 3987 Harry Potter and the Forbidden ForestC++
11.3.4 最小费用最大流问题C++

算法竞赛入门经典第二版

第3章 数组和字符串

例题

ExampleProblemSolution
例题3-1UVa 272 - TEX QuotesC++
例题3-2UVa 10082 - WERTYUC++
例题3-3UVa 401 - PalindromesC++
例题3-4UVa 340 - Master-Mind HintsC++
例题3-5UVa 1583 - Digit GeneratorC++
例题3-6UVa 1584 - Circular SequenceC++

习题

ExampleProblemSolution
习题3-1UVa 1585 - ScoreC++
习题3-2UVa 1586 - Molar massC++
习题3-3UVa 1225 - Digit CountingC++
习题3-4UVa 455 - Periodic StringsC++
习题3-5UVa 227 - PuzzleC++
习题3-6UVa 232 - Crossword AnswersC++
习题3-7UVa 1368 - DNA Consensus StringC++
习题3-8UVa 202 - Repeating DecimalsC++
习题3-9UVa 10340 - All in AllC++
习题3-10UVa 1587 - BoxC++
习题3-11UVa 1588 - KickdownC++
习题3-12UVa 11809 - Floating-Point NumbersC++

第4章 函数和递归

例题

ExampleProblemSolution
例题4-1UVa 1339 - Ancient CipherC++
例题4-2UVa 489 - Hangman JudgeC++
例题4-3UVa 133 - The Dole QueueC++
例题4-4UVa 213 - Message DecodingC++
例题4-5UVa 512 - Spreadsheet TrackingC++
例题4-6UVa 12412 - A Typical Homework (a.k.a Shi Xiong Bang Bang Mang)C++

习题

ExampleProblemSolution
习题4-1UVa 1589 - XiangqiC++
习题4-2UVa 201 - SquaresC++
习题4-3UVa 220 - OthelloC++
习题4-4UVa 253 - Cube paintingC++
习题4-5UVa 1590 - IP NetworksJAVA
习题4-6UVa 508 - Morse MismatchesJAVA
习题4-7UVa 509 - RAID!JAVA
习题4-8UVa 12108 - Extraordinarily Tired StudentsJAVA
习题4-9UVa 1591 - Data MiningJAVA
习题4-10UVa 815 - Flooded!JAVA

第5章 C++与STL入门

例题

ExampleProblemSolution
例题5-1UVa 10474 - Where is the Marble?JAVA
例题5-2UVa 101 - The Blocks ProblemJAVA
例题5-3UVa 10815 - Andy’s First DictionaryJAVA
例题5-4UVa 156 - AnanagramsJAVA
例题5-5UVa 12096 - The SetStack ComputerJAVA
例题5-6UVa 540 - Team QueueJAVA
例题5-7UVa 136 - Ugly NumbersJAVA
例题5-8UVa 400 - Unix lsJAVA
例题5-9UVa 1592 - DatabaseJAVA
例题5-10UVa 207 - PGA Tour Prize MoneyJAVA
例题5-11UVa 814 - The Letter Carrier’s RoundsJAVA
例题5-12UVa 221 - Urban ElevationsJAVA

习题

ExampleProblemSolution
习题5-1UVa 1593 - Alignment of Code
习题5-2UVa 1594 - Ducci Sequence
习题5-3UVa 10935 - Throwing cards away I solved
习题5-4UVa 10763 - Foreign Exchange
习题5-5UVa 10391 - Compound Words
习题5-6UVa 1595 - Symmetry
习题5-7UVa 12100 - Printer Queue
习题5-8UVa 230 - Borrowers
习题5-9UVa 1596 - Bug Hunt
习题5-10UVa 1597 - Searching the Web
习题5-11UVa 12504 - Updating a Dictionary
习题5-12UVa 511 - Do You Know the Way to San Jose?
习题5-13UVa 822 - Queue and A
习题5-14UVa 1598 - Exchange
习题5-15UVa 12333 - Revenge of Fibonacci
习题5-16UVa 212 - Use of Hospital Facilities

第6章 数据结构基础

6.1 再谈栈和队列

例题

ExampleProblemSolution
例题6-1210 - Concurrency SimulatorJAVA
例题6-2JAVA

巩固

表达式树
UVa 12219 - Common Subexpression Elimination(https://github.com/Ubuntu1996/AOAPC/tree/master/UVa_12219-Common_Subexpression_Elimination)

最小生成树

UVa 1395 - Slim Span

版权声明：本文为Utopiabuntu原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。