## BSGS（Baby steps giant steps）算法学习笔记

BSGS算法的本质，就是个分块啊，而分块的本质就是暴力乱搞…所以BSGS看起来很高大上的算法不过是暴力乱搞2333

BSGS算法学习小记（大步小步算法）

## bzoj2002: [Hnoi2010]Bounce 弹飞绵羊 (分块)

http://www.lydsy.com/JudgeOnline/problem.php?id=2002

## codeforces 13 E. Holes (分块)

http://codeforces.com/problemset/problem/13/E

n 个整数a[i] 表示进入i这个洞之后会跑到 i+a[i]….

## hdu 4638 Group

http://acm.hdu.edu.cn/showproblem.php?pid=4638

## hdu 5213 lucky （莫队算法）

http://acm.hdu.edu.cn/showproblem.php?pid=5213

## codeforces 220 B. Little Elephant and Array

http://codeforces.com/contest/220/problem/B

## （莫队算法的学习）bzoj 2038 [2009国家集训队]小Z的袜子(hose)

2038: [2009国家集训队]小Z的袜子(hose)

Time Limit: 20 Sec Memory Limit: 259 MB
Submit: 5327 Solved: 2461
[Submit][Status][Discuss]
Description

Input

Output

Sample Input

6 4

1 2 3 3 3 2

2 6

1 3

3 5

1 6

Sample Output

2/5

0/1

1/1

4/15

【样例解释】

【数据规模和约定】

30%的数据中 N,M ≤ 5000；

60%的数据中 N,M ≤ 25000；

100%的数据中 N,M ≤ 50000，1 ≤ L < R ≤ N，Ci ≤ N。

## hdoj4391 Paint The Wall

http://acm.hdu.edu.cn/showproblem.php?pid=4391

## hdoj 1754 I hate it

http://acm.hdu.edu.cn/showproblem.php?pid=1754

## codeforces #319 div 2 E C. Points on Plane (分块)

Let’s split rectangle 106 × 106 by vertical lines into 1000 rectangles 103 × 106. Let’s number them from left to right. We’re going to pass through points rectangle by rectangle. Inside the rectangle we’re going to pass the points in increasing order of y-coordinate if the number of rectangle is even and in decreasing if it’s odd.

Let’s calculate the maximum length of such a way. The coordinates are independent. By y-coordinate we’re passing 1000 rectangles from0 to 106, 109 in total. By x-coordinate we’re spending 1000 to get to the next point of current rectangle and 2000 to get to next rectangle. That means, 2 * 109 + 2000000 in total, which perfectly fits.

The complexity is O(n * log(n))

并不会做，看了题解写的，感觉好神奇…