## Practical data structure of "Introduction to algorithm competition classic training guide"

xindoo 2021-01-22 14:17:45
practical data structure introduction algorithm

# Infrastructure

## Example

Example 1

UVa11995 AC

I Can Guess the Data Structure!

Example 2

UVa11991 AC

Easy Problem from Rujia Liu

Sort or make good use of STL Answer key

Example 3

LA3135 AC

Argus

Priority queue ; simulation Answer key

Example 4

UVa11997 AC

K Smallest Sums

Priority queue ; Ordered table merging Answer key

Example 5

LA3644 AC

X-Plosives

Union checking set Answer key

Example 6

LA3027 AC

Corporative Network

Weighted union search Answer key

## exercises

UVa11988 AC

Broken Keyboard (a.k.a. Beiju Text)

UVa11645

Hoax or what

Maximum - The smallest heap or STL Of set

LA4487

Exclusive-OR

Weighted union search

UVa11987

Almost Union-Find

Union checking set ; It takes a little skill

LA5908

Tracking RFIDs

Not large in scale , No advanced data structures

LA3977

Summits

Speed up the algorithm with data structure

LA3634

The SetStack Computer

simulation ; data structure

# Interval information maintenance

## Example

Example 7

LA4329 AC

Ping pong

Fenwick Trees ; It's similar to reverse order Answer key

Example 8

UVa11235 AC

Frequent Values

Example 9

LA3938 AC

Ray, pass me the dishes

Line segment tree ; Interval query Answer key

Example 10

UVa11992 AC

Fast Matrix Operations

Line segment tree ; Interval modification ; Lazy tag passing Answer key

## exercises

LA2191

Potentiometers AC

Fenwick Trees Answer key

LA5902

Movie collection AC

Fenwick Trees Answer key

UVa12299

RMQ with shifts AC

Line segment tree ; Single point modification , Interval query Answer key

LA4108

Skyline

Line segment tree

UVa11525

Permutations

Recurrence ; Line segment tree （ Or two points +Fenwick Trees ）

LA4730

Kingdom

Union checking set ; Line segment tree

LA5694

Line segment tree ; Combination count

LA5698

Draw a Mess

Line tree can do , But it's better not to search

LA4013

A Sequence of Numbers

It turns into an interval problem ; Preprocessing

LA5915

Flights

# String algorithm

## Example

Example 11

LA3942

Remember the Word

use Trie Accelerate dynamic planning

Example 12

UVa11732

strcmp() Anyone?

Trie The nature of

Example 13

LA3026

Period

KMP The mismatch function of the algorithm

Example 14

LA4670

Dominating Patterns

AC automata

Example 15

UVa11468

Substring

AC Algorithms on automata

Example 16

UVa11019

Matrix Matcher

Two dimensional matching ;AC automata

Example 17

UVa11107

Life Forms

The suffix array +height Array

Example 18

LA4513

Stammering Aliens

LCP;hash function

## exercises

UVa11488

Hyper Prefix Sets

Trie Application

LA5913

Dictionary Size

Prefix ; suffix ; String collection

LA3703

Billing Tables

Trie Application

LA2755

Find the minimum representation of a string

LA3907

Puzzle

to s A forbidden substring , Find the longest string without them

LA4126

Dynamic programming of strings

UVa10829

L-Gap Substrings

The suffix array

LA3490

Generator

automata ; Mathematical expectation ; Mathematical derivation

LA4769

Fuzzy search

LA4975

Casting Spells

Difficult ; Need to work with other data structures

LA5766

GRE Words

Accelerating dynamic programming with string algorithm

LA4619

Accountant notes

AC The application of automata . Difficult

# Sort binary trees

## Example

Example 19

UVa11020

Efficient Solutions

Maintain point set ; monotonicity

Example 20

LA5031

Graph and Queries

Ranking tree ; Union checking set ; Back in time

Example 21

UVa11922

Permutation Transformer

Stretch the tree ; And split and merged sequences

Example 22

UVa11996

Jewel Magic

character string ;Hash function ; Stretch the tree

## exercises

LA4847

Binary Search Tree

and BST About the counting problem

LA5705

Very Boring Homework

BST Fast simulation ; recursive . Note the stack overflow

LA3525

Wild West

Scanning ; Maintain point set ; monotonicity （ Or line tree ）

LA3961

Robotic Sorting

Stretch the tree

LA4976

Defense Line

Maintain point set ; monotonicity

UVa12419

Heap Manager

Participation of this paper Tencent cloud media sharing plan , You are welcome to join us , share .

https://javamana.com/2021/01/20210122141431992W.html