基础数据结构
例题
例题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 |