算法竞赛入门经典第一版

[TOC]

算法竞赛入门经典第一版

此repo为刘汝佳算法竞赛入门经典第一版中例题对应OJ题库及解答。

第5章基础题目选解

5.1 字符串

Example	Problem	Solution
5.1.1 WERTYU	UVa 10082 - WERTYU	C++
5.1.2 TeX括号	UVa 272 - TEX Quotes	C++
5.1.3 周期串	UVa 455 - Periodic Strings	C++

5.2 高精度计算

Example	Problem	Solution
5.2.1 小学生算术	UVa 10035 - Primary Arithmetic	C++
5.2.2 阶乘的精确值	UVa 623 - 500!	C++

5.3 排序与检索

Example	Problem	Solution
5.3.1 6174问题	NYOJ 57 6174问题	C++
5.3.2 字母重排	UVa 642 - Word Amalgamation	C++

5.4 数学基础

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

第六章数据结构基础

6.1 栈和队列

Example	Problem	Solution
6.1.1 卡片游戏	UVa 10935 - Throwing cards away I	C++
6.1.2 铁轨	UVa 514 - Rails	C++

6.2 链表

Example	Problem	Solution
6.2.1 移动小球	NOJ 1099 移动小球	C++

6.3 二叉树

Example	Problem	Solution
6.3.1 小球下落	UVa 679 - Dropping Balls	C++
6.3.2 层次遍历	UVa 122 - Trees on the level	C++
6.3.3 二叉树重建	UVa 536 - Tree Recovery	C++

6.4 图

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

第七章暴力求解法

7.1 简单枚举

Example	Problem	Solution
7.1.1 除法	UVa 725 - Division	C++
7.1.2 最大乘积	UVa 11059 - Maximum Product	C++
7.1.3 分数拆分	UVa 10976 - Fractions Again?!	C++
7.1.4 双基回文数	OpenJudge 4831 双基回文数	C++

7.2 枚举排列

Example	Problem	Solution
7.2.1 生成1~n的排列/7.2.2 生成可重集的排列	UVa 10098 - Generating Fast	C++
7.2.4 下一个排列	LeetCode 31. Next Permutation	C++

7.3 子集生成

Example	Problem	Solution
7.3 子集生成	POJ 2718 Smallest Difference	C++

7.4 回溯法

Example	Problem	Solution
7.4.1 八皇后问题	UVa 750 - 8 Queens Chess Problem	C++
7.4.2 素数环	UVa 524 - Prime Ring Problem	C++
7.4.3 困难的串	UVa 129 - Krypton Factor	C++
7.4.4 带宽	UVa 140 - Bandwidth	C++

7.5 隐式树的遍历

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

第八章高效算法设计

8.1 算法初步分析

Example	Problem	Solution
8.1 最大连续和	HDUOJ 1003 Max Sum	C++

8.2 再谈排序与检索

Example	Problem	Solution
8.2.1_1 归并排序	LintCode 463. Sort Integers	C++
8.2.1_2 逆序对数	POJ 1804 Brainman	C++
8.2.2 快速排序	SJTUOJ 1525. 第K小的数	C++
8.2.3 二分查找	LintCode 457. Classical Binary Search	C++

8.4 递归与分治

Example	Problem	Solution
8.3.1 棋盘覆盖问题	NYOJ 45 棋盘覆盖	C++
8.3.2 循环日程表问题	NoneOJ 1 Cycle Schedule	C++
8.3.3 巨人与鬼	UVa 1411 - Ants	C++
8.3.4 非线性方程求根	UVa 10341 - Solve It	C++
8.3.5 最大值最小化	UVa 714 - Copying Books	C++

8.3 贪心法

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

第九章动态规划初步

9.1 数字三角形

Example	Problem	Solution
9.1 数字三角形	POJ 1163 The Triangle	Java

9.2 DAG上的动态规划

Example	Problem	Solution
9.2_1 嵌套矩形	NYOJ 16 矩形嵌套	C++
9.2_2 硬币问题	Liuser's OJ 725 硬币问题	C++

9.3 0-1背包问题

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

9.4 递归结构中的动态规划

Example	Problem	Solution
9.4.1 表达式上的动态规划	UVa 348 - Optimal Array Multiplication Sequence	C++
9.4.2 凸多边形上的动态规划	UVa 1331 - Minimax Triangulation	C++
9.4.3 树上的动态规划	UVa 1220 - Party at Hali-Bula	C++

9.5 集合上的动态规划

Example	Problem	Solution
9.5 集合上的动态规划	UVa 10911 - Forming Quiz Teams	C++

第10章数学概念与方法

10.1 数论初步

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

10.2 排列与组合

Example	Problem	Solution
10.2.1 无关的元素	UVa 1635 - Irrelevant Elements	C++
10.2.2_1 约数的个数	UVa 294 - Divisors	C++
10.2.2_2 小于n且与n互素的个数	UVa 10820 - Send a Table	C++
10.2.4 离散概率初步	LightOJ 1104 Birthday Paradox	C++

10.3 递推关系

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

第11章图论模型与算法

11.1 再谈树

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

11.2 最短路问题

Example	Problem	Solution
11.2.1-3 Dijkstra算法	HDUOJ 2544 最短路	C++
11.2.4 Bellman-Ford算法	POJ 3259 Wormholes	C++

11.3 网络流初步

Example	Problem	Solution
11.3.2 增广路算法	HDUOJ 1532 Drainage Ditches	C++
11.3.3 最小割最大流定理	HDUOJ 3987 Harry Potter and the Forbidden Forest	C++
11.3.4 最小费用最大流问题		C++

算法竞赛入门经典第二版

第3章数组和字符串

例题

Example	Problem	Solution
例题3-1	UVa 272 - TEX Quotes	C++
例题3-2	UVa 10082 - WERTYU	C++
例题3-3	UVa 401 - Palindromes	C++
例题3-4	UVa 340 - Master-Mind Hints	C++
例题3-5	UVa 1583 - Digit Generator	C++
例题3-6	UVa 1584 - Circular Sequence	C++

习题

Example	Problem	Solution
习题3-1	UVa 1585 - Score	C++
习题3-2	UVa 1586 - Molar mass	C++
习题3-3	UVa 1225 - Digit Counting	C++
习题3-4	UVa 455 - Periodic Strings	C++
习题3-5	UVa 227 - Puzzle	C++
习题3-6	UVa 232 - Crossword Answers	C++
习题3-7	UVa 1368 - DNA Consensus String	C++
习题3-8	UVa 202 - Repeating Decimals	C++
习题3-9	UVa 10340 - All in All	C++
习题3-10	UVa 1587 - Box	C++
习题3-11	UVa 1588 - Kickdown	C++
习题3-12	UVa 11809 - Floating-Point Numbers	C++

第4章函数和递归

例题

Example	Problem	Solution
例题4-1	UVa 1339 - Ancient Cipher	C++
例题4-2	UVa 489 - Hangman Judge	C++
例题4-3	UVa 133 - The Dole Queue	C++
例题4-4	UVa 213 - Message Decoding	C++
例题4-5	UVa 512 - Spreadsheet Tracking	C++
例题4-6	UVa 12412 - A Typical Homework (a.k.a Shi Xiong Bang Bang Mang)	C++

习题

Example	Problem	Solution
习题4-1	UVa 1589 - Xiangqi	C++
习题4-2	UVa 201 - Squares	C++
习题4-3	UVa 220 - Othello	C++
习题4-4	UVa 253 - Cube painting	C++
习题4-5	UVa 1590 - IP Networks	JAVA
习题4-6	UVa 508 - Morse Mismatches	JAVA
习题4-7	UVa 509 - RAID!	JAVA
习题4-8	UVa 12108 - Extraordinarily Tired Students	JAVA
习题4-9	UVa 1591 - Data Mining	JAVA
习题4-10	UVa 815 - Flooded!	JAVA

第5章 C++与STL入门

例题

Example	Problem	Solution
例题5-1	UVa 10474 - Where is the Marble?	JAVA
例题5-2	UVa 101 - The Blocks Problem	JAVA
例题5-3	UVa 10815 - Andy's First Dictionary	JAVA
例题5-4	UVa 156 - Ananagrams	JAVA
例题5-5	UVa 12096 - The SetStack Computer	JAVA
例题5-6	UVa 540 - Team Queue	JAVA
例题5-7	UVa 136 - Ugly Numbers	JAVA
例题5-8	UVa 400 - Unix ls	JAVA
例题5-9	UVa 1592 - Database	JAVA
例题5-10	UVa 207 - PGA Tour Prize Money	JAVA
例题5-11	UVa 814 - The Letter Carrier's Rounds	JAVA
例题5-12	UVa 221 - Urban Elevations	JAVA

习题

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

第6章数据结构基础

6.1 再谈栈和队列

例题

Example	Problem	Solution
例题6-1	210 - Concurrency Simulator	JAVA
例题6-2		JAVA

剑指offer第二版

Example	Problem	Solution
2.3.1 数组（面试题3）	数组中重复的数字
2.3.1 数组（面试题4）	二维数组中的查找
2.3.2 字符串（面试题5）	替换空格
2.3.3 链表（面试题6）	从尾到头打印链表

巩固

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

最小生成树

UVa 1395 - Slim Span

Name		Name	Last commit message	Last commit date
Latest commit History 540 Commits
51Nod_1242-Nth_Fibonacci		51Nod_1242-Nth_Fibonacci
BeginOJ_1377-N_K_Set		BeginOJ_1377-N_K_Set
HDUOJ_1003-Max_Sum		HDUOJ_1003-Max_Sum
HDUOJ_1248-Ice_Throne		HDUOJ_1248-Ice_Throne
HDUOJ_1285-Determine_the_Place_of_Competition		HDUOJ_1285-Determine_the_Place_of_Competition
HDUOJ_1532-Drainage_Ditches		HDUOJ_1532-Drainage_Ditches
HDUOJ_1596-find_the_safest_road		HDUOJ_1596-find_the_safest_road
HDUOJ_1863-Smooth_Project		HDUOJ_1863-Smooth_Project
HDUOJ_2544-Shortest		HDUOJ_2544-Shortest
HDUOJ_2602-Bone_Collector		HDUOJ_2602-Bone_Collector
HDUOJ_3826-Squarefree_number		HDUOJ_3826-Squarefree_number
HDUOJ_3987-Harry_Potter_and_the_Forbidden_Forest		HDUOJ_3987-Harry_Potter_and_the_Forbidden_Forest
HITOJ_1868-Eight_digital		HITOJ_1868-Eight_digital
LeetCode_31-Next_Permutation		LeetCode_31-Next_Permutation
LightOJ_1104-Birthday_Paradox		LightOJ_1104-Birthday_Paradox
LintCode_457-Classical_Binary_Search		LintCode_457-Classical_Binary_Search
LintCode_463-Sort_Integers		LintCode_463-Sort_Integers
LiusersOJ_725-Coin_Problem		LiusersOJ_725-Coin_Problem
Lutece_469-Division_expression		Lutece_469-Division_expression
NOJ_1099-Moving_Ball		NOJ_1099-Moving_Ball
NOJ_1269-Select_Disjoint_Interval		NOJ_1269-Select_Disjoint_Interval
NOJ_1406-the_kth_minimum_number		NOJ_1406-the_kth_minimum_number
NYOJ_16-Nested_Rectangle		NYOJ_16-Nested_Rectangle
NYOJ_20-Awkward_Country		NYOJ_20-Awkward_Country
NYOJ_45-Checkerboard_Coverage		NYOJ_45-Checkerboard_Coverage
NYOJ_57-6174		NYOJ_57-6174
NYOJ_71-Travel_on_canoes		NYOJ_71-Travel_on_canoes
NoneOJ_1-Cycle_Schedule		NoneOJ_1-Cycle_Schedule
NoneOJ_2-Optimal_Loading		NoneOJ_2-Optimal_Loading
NoneOJ_3-Partial_Bag		NoneOJ_3-Partial_Bag
NoneOJ_4-Interval_Coverage		NoneOJ_4-Interval_Coverage
NoneOJ_5-Coding		NoneOJ_5-Coding
NoneOJ_6-Big_Int_Module		NoneOJ_6-Big_Int_Module
NoneOJ_7-Power_Module		NoneOJ_7-Power_Module
OpenJudge_4831-Double_Base_Palindrome_Number		OpenJudge_4831-Double_Base_Palindrome_Number
OpenJudge_Bailian_4147-Hanoi		OpenJudge_Bailian_4147-Hanoi
POJ_1041-John's_trip		POJ_1041-John's_trip
POJ_1061-Frogs_date		POJ_1061-Frogs_date
POJ_1163-The_triangle		POJ_1163-The_triangle
POJ_1480-Optimal_Programs		POJ_1480-Optimal_Programs
POJ_1686-Lazy_Math_Instructor		POJ_1686-Lazy_Math_Instructor
POJ_1804-Brainman		POJ_1804-Brainman
POJ_2142-The_Balance		POJ_2142-The_Balance
POJ_2718-Smallest_Difference		POJ_2718-Smallest_Difference
POJ_3259-Wormholes		POJ_3259-Wormholes
POJ_3984-Maze_Problem		POJ_3984-Maze_Problem
SJTUOJ_1525-the_kth_minimum_number		SJTUOJ_1525-the_kth_minimum_number
UVa_10034-Freckles		UVa_10034-Freckles
UVa_10035-Primary_Arithmetic		UVa_10035-Primary_Arithmetic
UVa_10082-WERTYU		UVa_10082-WERTYU
UVa_10085-The_most_distant_state		UVa_10085-The_most_distant_state
UVa_10098-Generating_Fast		UVa_10098-Generating_Fast
UVa_101-The_Blocks_Problem		UVa_101-The_Blocks_Problem
UVa_10148-Advertisement		UVa_10148-Advertisement
UVa_10213-How_Many_Pieces_of_land		UVa_10213-How_Many_Pieces_of_land
UVa_10340-All_in_All		UVa_10340-All_in_All
UVa_10341-Solve_it		UVa_10341-Solve_it
UVa_10474-Where_is_the_Marble		UVa_10474-Where_is_the_Marble
UVa_10603-Fill		UVa_10603-Fill
UVa_10815-Andy's_First_Dictionary		UVa_10815-Andy's_First_Dictionary
UVa_10820-Send_a_Table		UVa_10820-Send_a_Table
UVa_10911-Forming_Quiz_Teams		UVa_10911-Forming_Quiz_Teams
UVa_10935-Throwing_cards_away_I		UVa_10935-Throwing_cards_away_I
UVa_10976-Fractions_Again?!		UVa_10976-Fractions_Again?!
UVa_11059-Maximum_Product		UVa_11059-Maximum_Product
UVa_1151-Buy_or_Build		UVa_1151-Buy_or_Build
UVa_11809-Floating_Point_Numbers		UVa_11809-Floating_Point_Numbers
UVa_12096-The_SetStack_Computer		UVa_12096-The_SetStack_Computer
UVa_12108-Extraordinarily_Tired_Sdudents		UVa_12108-Extraordinarily_Tired_Sdudents
UVa_122-Trees_on_the_level		UVa_122-Trees_on_the_level
UVa_1220-Party_at_Hali-Bula		UVa_1220-Party_at_Hali-Bula
UVa_12219-Common_Subexpression_Elimination		UVa_12219-Common_Subexpression_Elimination
UVa_1225-Digit_Counting		UVa_1225-Digit_Counting
UVa_12412-A_Typical_Homework		UVa_12412-A_Typical_Homework
UVa_12558-Egyptian_Fractions_HARD_version		UVa_12558-Egyptian_Fractions_HARD_version
UVa_129-Krypton_Factor		UVa_129-Krypton_Factor
UVa_133-The_Dole_Queue		UVa_133-The_Dole_Queue
UVa_1331-Minimax_Triangulation		UVa_1331-Minimax_Triangulation
UVa_1339-Ancient_Cipher		UVa_1339-Ancient_Cipher
UVa_136-Ugly_Numbers		UVa_136-Ugly_Numbers
UVa_1368-DNA_Consensus_String		UVa_1368-DNA_Consensus_String
UVa_1395-Slim_Span		UVa_1395-Slim_Span
UVa_140-Bandwidth		UVa_140-Bandwidth
UVa_1411-Ants		UVa_1411-Ants
UVa_143-Orchard_Trees		UVa_143-Orchard_Trees
UVa_156-Ananagrams		UVa_156-Ananagrams
UVa_1583-Digit_Generator		UVa_1583-Digit_Generator
UVa_1584-Circular_Sequence		UVa_1584-Circular_Sequence
UVa_1585-Score		UVa_1585-Score
UVa_1586-Molar_mass		UVa_1586-Molar_mass
UVa_1587-Box		UVa_1587-Box
UVa_1588-Kickdown		UVa_1588-Kickdown
UVa_1589-Xiangqi		UVa_1589-Xiangqi
UVa_1590-IP_Networks		UVa_1590-IP_Networks
UVa_1591-Data_Mining		UVa_1591-Data_Mining
UVa_160-Factors_and_Factorials		UVa_160-Factors_and_Factorials
UVa_1635-Irrelevant_Elements		UVa_1635-Irrelevant_Elements
UVa_201-Squares		UVa_201-Squares
UVa_202-Repeating_Decimals		UVa_202-Repeating_Decimals
UVa_207-PGA_Tour_Prize_Money		UVa_207-PGA_Tour_Prize_Money

lusunn111/AOAPC

Folders and files

Latest commit

History

Repository files navigation

算法竞赛入门经典第一版

第5章 基础题目选解

5.1 字符串

5.2 高精度计算

5.3 排序与检索

5.4 数学基础

第六章 数据结构基础

6.1 栈和队列

6.2 链表

6.3 二叉树

6.4 图

第七章 暴力求解法

7.1 简单枚举

7.2 枚举排列

7.3 子集生成

7.4 回溯法

7.5 隐式树的遍历

第八章 高效算法设计

8.1 算法初步分析

8.2 再谈排序与检索

8.4 递归与分治

8.3 贪心法

第九章 动态规划初步

9.1 数字三角形

9.2 DAG上的动态规划

9.3 0-1背包问题

9.4 递归结构中的动态规划

9.5 集合上的动态规划

第10章 数学概念与方法

10.1 数论初步

10.2 排列与组合

10.3 递推关系

第11章 图论模型与算法

11.1 再谈树

11.2 最短路问题

11.3 网络流初步

算法竞赛入门经典第二版

第3章 数组和字符串

例题

习题

第4章 函数和递归

例题

习题

第5章 C++与STL入门

例题

习题

第6章 数据结构基础

6.1 再谈栈和队列

例题

剑指offer第二版

巩固

About

Resources

Stars

Watchers

Forks

Releases

Packages 0

Languages

第5章基础题目选解

第六章数据结构基础

第七章暴力求解法

第八章高效算法设计

第九章动态规划初步

第10章数学概念与方法

第11章图论模型与算法

第3章数组和字符串

第4章函数和递归

第6章数据结构基础

Packages