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

例题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

加权并查集 题解

UVa11645

Hoax or what

最大-最小堆或者STL的set

LA4487

Exclusive-OR

加权并查集

UVa11987

Almost Union-Find

并查集；需要一点技巧

LA5908

Tracking RFIDs

规模不大，不用高级数据结构

LA3977

Summits

用数据结构加速算法

LA3634

The SetStack Computer

模拟；数据结构

例题8

UVa11235 AC

Frequent Values

RMQ 题解

例题9

LA3938 AC

Ray, pass me the dishes

线段树；区间查询 题解

例题10

UVa11992 AC

Fast Matrix Operations

线段树；区间修改；懒标记传递 题解

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

例题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函数

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自动机的应用。有难度

例题20

LA5031

Graph and Queries

名次树；并查集；时光倒流

例题21

UVa11922

Permutation Transformer

伸展树；和分裂合并的序列

例题22

UVa11996

Jewel Magic

字符串；Hash函数；伸展树

LA5705

Very Boring Homework

BST快速模拟；递归。注意栈溢出

LA3525

Wild West

扫描法；维护点集；单调性（或线段树）

LA3961

Robotic Sorting

伸展树

LA4976

Defense Line

维护点集；单调性

UVa12419

Heap Manager