负一、写在前面
零、前置
一、基础算法
0. 内容概要
包括排序、二分、前缀和、差分、双指针、离散化、区间和
1. 排序
（1）快速排序
package main
import "fmt"
func QuickSort(arr []int, l int, r int) {
if l >= r {
return
}
x, i, j := arr[(l+r)/2], l-1, r+1
for i < j {
for {
i++
if arr[i] >= x {
break
}
}
for {
j--
if arr[j] <= x {
break
}
}
if i < j {
arr[i], arr[j] = arr[j], arr[i]
}
}
QuickSort(arr, l, j)
QuickSort(arr, j+1, r)
}
func main() {
var n int
fmt.Scanln(&n)
arr := make([]int, n+5)
for i := 0; i < n; i++ {
fmt.Scan(&arr[i])
}
QuickSort(arr, 0, n-1)
for i := 0; i < n; i++ {
fmt.Printf("%d ", arr[i])
}
}
（2）归并排序
package main
import "fmt"
// https://www.acwing.com/problem/content/789/
func MergeSort(arr []int, l int, r int) {
if l >= r {
return
}
mid := (l + r) / 2
MergeSort(arr, l, mid)
MergeSort(arr, mid+1, r)
tmp := make([]int, r-l+1)
i, j, k := l, mid+1, 0
for i <= mid && j <= r {
if arr[i] < arr[j] {
tmp[k] = arr[i]
k++
i++
} else {
tmp[k] = arr[j]
k++
j++
}
}
for i <= mid {
tmp[k] = arr[i]
k++
i++
}
for j <= r {
tmp[k] = arr[j]
k++
j++
}
k = 0
for i := l; i <= r; i++ {
arr[i] = tmp[k]
k++
}
}
func main() {
var n int
fmt.Scanln(&n)
arr := make([]int, n+5)
for i := 0; i < n; i++ {
fmt.Scan(&arr[i])
}
MergeSort(arr, 0, n-1)
for i := 0; i < n; i++ {
fmt.Printf("%d ", arr[i])
}
}
2. 二分
（1）整数二分
package main
import "fmt"
// https://www.acwing.com/problem/content/791/
func main() {
var n, q int
fmt.Scanf("%d %d", &n, &q)
arr := make([]int, n+5)
for i := 0; i < n; i++ {
fmt.Scan(&arr[i])
}
var x int
for q > 0 {
fmt.Scanln(&x)
l, r := 0, n-1
for l < r {
mid := (l + r) / 2
if arr[mid] < x {
l = mid + 1
} else {
r = mid
}
}
q--
if arr[l] != x {
fmt.Println("-1 -1")
continue
}
fmt.Print(l)
l, r = 0, n-1
for l < r {
mid := (l + r + 1) / 2
if arr[mid] > x {
r = mid - 1
} else {
l = mid
}
}
fmt.Printf(" %d\n", l)
}
}
（2）浮点数二分
package main
import "fmt"
// https://www.acwing.com/problem/content/792/
func main() {
var n float64
fmt.Scanln(&n)
l, r := -1000.00, 1000.00
for r-l > 1e-7 {
mid := (l + r) / 2
if mid*mid*mid > n {
r = mid
} else {
l = mid
}
}
fmt.Printf("%.6f", l)
}
3. 前缀和
（1）一维前缀和
package main
import "fmt"
// https://www.acwing.com/problem/content/797/
func main() {
var n, m int
fmt.Scanf("%d %d", &n, &m)
a := make([]int, n+5)
sa := make([]int, n+5)
for i := 1; i <= n; i++ {
fmt.Scan(&a[i])
sa[i] = sa[i-1] + a[i]
}
var l, r int
for m > 0 {
fmt.Scanf("%d %d", &l, &r)
fmt.Println(sa[r] - sa[l-1])
m--
}
}
（2）二维前缀和
package main
import (
"bufio"
"fmt"
"os"
)
// https://www.acwing.com/problem/content/description/798/
func main() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
var n, m, q int
fmt.Scanf("%d %d %d", &n, &m, &q)
a := make([][]int, n+1)
sa := make([][]int, n+1)
for i := 0; i <= n; i++ {
a[i] = make([]int, m+1)
sa[i] = make([]int, m+1)
}
for i := 1; i <= n; i++ {
for j := 1; j <= m; j++ {
fmt.Fscan(in, &a[i][j])
sa[i][j] = sa[i-1][j] + sa[i][j-1] - sa[i-1][j-1] + a[i][j]
}
}
var x1, y1, x2, y2 int
for q > 0 {
fmt.Fscan(in, &x1, &y1, &x2, &y2)
fmt.Fprintln(out, sa[x2][y2]-sa[x2][y1-1]-sa[x1-1][y2]+sa[x1-1][y1-1])
q--
}
}
4. 差分
（1）一维差分
package main
import (
"bufio"
"fmt"
"os"
)
// https://www.acwing.com/problem/content/799/
func main() {
in := bufio.NewReader(os.Stdin)
//out := bufio.NewWriter(os.Stdout)
var n, q int
fmt.Scan(&n, &q)
a := make([]int, n+5)
sa := make([]int, n+5)
for i := 1; i <= n; i++ {
fmt.Fscan(in, &a[i])
sa[i] += a[i]
sa[i+1] -= a[i]
}
var l, r, c int
for q > 0 {
fmt.Fscan(in, &l, &r, &c)
sa[l] += c
sa[r+1] -= c
q--
}
for i := 1; i <= n; i++ {
sa[i] += sa[i-1]
fmt.Printf("%d ", sa[i])
}
}
（2）二维差分
package main
import (
"bufio"
"fmt"
"os"
)
// https://www.acwing.com/problem/content/description/800/
func insert(a [][]int, x1, y1, x2, y2, c int) {
a[x1][y1] += c
a[x2+1][y1] -= c
a[x1][y2+1] -= c
a[x2+1][y2+1] += c
}
func main() {
in := bufio.NewReader(os.Stdin)
var n, m, q int
fmt.Scan(&n, &m, &q)
a := make([][]int, n+2)
for i := 0; i <= n+1; i++ {
a[i] = make([]int, m+2)
}
var x int
for i := 1; i <= n; i++ {
for j := 1; j <= m; j++ {
fmt.Fscan(in, &x)
insert(a, i, j, i, j, x)
}
}
var x1, y1, x2, y2 int
for q > 0 {
fmt.Fscan(in, &x1, &y1, &x2, &y2, &x)
insert(a, x1, y1, x2, y2, x)
q--
}
for i := 1; i <= n; i++ {
for j := 1; j <= m; j++ {
a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1]
}
}
for i := 1; i <= n; i++ {
for j := 1; j <= m; j++ {
fmt.Printf("%d ", a[i][j])
}
fmt.Println()
}
}
5. 合并区间
package main
import (
"bufio"
"fmt"
"os"
"sort"
)
//https://www.acwing.com/problem/content/description/805/
type seg struct {
l int
r int
}
func main() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
var n int
fmt.Fscan(in, &n)
a := make([]seg, n)
for i := 0; i < n; i++ {
fmt.Fscan(in, &a[i].l, &a[i].r)
}
sort.Slice(a,
func(i, j int) bool {
return a[i].l <= a[j].l
})
ans := 0
st, ed := a[0].l, a[0].r
for i := 1; i < n; i++ {
now := a[i]
if ed < now.l {
ans++
st = now.l
ed = now.r
} else {
st = st
if ed < now.r {
ed = now.r
}
}
}
fmt.Println(ans + 1)
}
二、数据结构
0. 内容概要
包括并查集、树状数组、线段树
三、搜索与图论
0. 内容概要
包括DFS、BFS、最短路、拓扑排序、最小生成树、LCA
四、数论
0. 内容概要
包括试除法、埃氏筛、gcd与lcm、快速幂与逆元、组合数
五、动态规划
0. 内容概要
包括背包问题、线性DP、区间DP、树形DP