《算法竞赛入门经典——训练指南》实用数据结构

时间:2022-05-05 09:53:57

基础数据结构

例题

例题1 UVa11995    AC I Can Guess the Data Structure! ADT  题解
例题2 UVa11991    AC Easy Problem from Rujia Liu 排序或者善用STL  题解
例题3 LA3135      AC Argus 优先队列;模拟    题解
例题4 UVa11997   AC K Smallest Sums 优先队列;有序表合并 题解
例题5 LA3644      AC X-Plosives

并查集                        题解

例题6 LA3027     AC Corporative Network 加权并查集                 题解

习题

UVa11988      AC Broken Keyboard (a.k.a. Beiju Text) 模拟;链表               题解
UVa11645 Hoax or what 最大-最小堆或者STL的set
LA4487 Exclusive-OR 加权并查集
UVa11987 Almost Union-Find

并查集;需要一点技

LA5908 Tracking RFIDs 规模不大,不用高级数据结构
LA3977 Summits 用数据结构加速算法
LA3634 The SetStack Computer 模拟;数据结构


区间信息维护

例题

例题7 LA4329      AC Ping pong Fenwick树;类似逆序对  题解
例题8 UVa11235  AC Frequent Values RMQ         题解
例题9 LA3938      AC Ray, pass me the dishes 线段树;区间查询  题解
例题10 UVa11992  AC Fast Matrix Operations 线段树;区间修改;懒标记传递   题解  

习题

LA2191 Potentiometers      AC Fenwick树                   题解
LA5902 Movie collection    AC Fenwick树                   题解
UVa12299 RMQ with shifts     AC 线段树;单点修改,区间查询  题解
LA4108 Skyline 线段树
UVa11525 Permutations 递推;线段树(或二分+Fenwick树)
LA4730 Kingdom 并查集;线段树
LA5694 Adding New Machine 线段树;组合计数
LA5698 Draw a Mess 线段树可以做,但并查集更好
LA4013 A Sequence of Numbers 转化为区间问题;预处理
LA5915 Flights

字符串算法

例题

例题11 LA3942 Remember the Word 用Trie加速动态规划
例题12 UVa11732 strcmp() Anyone? Trie的性质
例题13 LA3026 Period KMP算法的失配函数
例题14 LA4670 Dominating Patterns AC自动机
例题15 UVa11468 Substring AC自动机上的算法
例题16 UVa11019 Matrix Matcher 二维匹配;AC自动机
例题17 UVa11107 Life Forms 后缀数组+height数组
例题18 LA4513 Stammering Aliens LCP;hash函数

习题

UVa11488 Hyper Prefix Sets Trie的应用
LA5913 Dictionary Size 前缀;后缀;字符串集合
LA3703 Billing Tables Trie的应用
LA2755 Hidden Password 求字符串的最小表示
LA3907 Puzzle 给s个禁止子串,求不含它们的最长串
LA4126 Password Suspects 字符串的动态规划
UVa10829 L-Gap Substrings 后缀数组
LA3490 Generator 自动机;数学期望;数学推导
LA4769 Fuzzy Google Suggest 模糊查找
LA4975 Casting Spells 有难度;需要配合其他数据结构
LA5766 GRE Words 用串算法加速动态规划
LA4619 Accountant notes AC自动机的应用。有难度

排序二叉树

例题

例题19 UVa11020 Efficient Solutions 维护点集;单调性
例题20 LA5031 Graph and Queries 名次树;并查集;时光倒流
例题21 UVa11922 Permutation Transformer 伸展树;和分裂合并的序列
例题22 UVa11996 Jewel Magic 字符串;Hash函数;伸展树

习题

LA4847 Binary Search Tree 和BST有关的计数问题
LA5705 Very Boring Homework BST快速模拟;递归。注意栈溢出
LA3525 Wild West 扫描法;维护点集;单调性(或线段树)
LA3961 Robotic Sorting 伸展树
LA4976 Defense Line 维护点集;单调性
UVa12419 Heap Manager