### 题目描述

1. 插入一个字符
2. 删除一个字符
3. 替换一个字符

#### 样例

horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

### 算法1

##### (动态规划) $O(n^2)$

1. 当s[i] == s[j]时，f[i][j] = f[i-1][j-1]
2. 当s[i] != s[j]时，f[i][j] 可以从三个状态转移，删除第i个字符，删除第j个字符，修改第i个或第j个字符，分别对应f[i-1][j], f[i][j-1], f[i-1][j-1]，取最小，然后+1。

#### Golang 代码

func minDistance(word1 string, word2 string) int {
slen1, slen2 := len(word1), len(word2)
f := make([][]int, slen1+1)
for i := range f {
f[i] = make([]int, slen2+1)
for j :=range f[i] {
f[i][j] = 1<<31 - 1
}
}
for i := 0; i <= slen1; i++ {
f[i][0] = i
}
for i := 0; i <= slen2; i++ {
f[0][i] = i
}
for i := 0; i < slen1; i++ {
for j := 0; j < slen2; j++ {
if word1[i] == word2[j] {
f[i+1][j+1] = f[i][j]
} else {
f[i+1][j+1] = min(min(f[i][j+1], f[i+1][j]), f[i][j]) + 1
}
}
}
return f[slen1][slen2]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}

### 算法1

#### Golang 代码

func longestPalindrome(s string) string {
n := len(s)
f := make([][]bool, n)
for i := range f {
f[i] = make([]bool, n)
f[i][i] = true
}
for step := 2; step <= n; step++ {
for i := 0; i <= n-step; i++ {
j := i+step-1
f[i][j] = s[i] == s[j] && ((i+1 <= j-1 &&f[i+1][j-1]) || i+1 > j-1)
}
}
for step := n; step >= 1; step-- {
for i := 0; i <= n-step; i++ {
j := i+step-1
if f[i][j] {
return s[i:j+1]
}
}
}
return ""
}
func max(a, b int) int {
if a > b {
return a
}
return b
}

### 算法2

blablabla

#### Golang 代码

func longestPalindrome(s string) string {
n := len(s)
mana := make([]byte, 2*n+1)
for i := 0; i < n; i++ {
mana[2*i] = '*'
mana[2*i+1] = s[i]
}
mana[2*n] = '*'
var lim, last int
res := 0
resIdx := 0
var resstr []byte
for i := 0; i < 2*n+1; i++ {
if i < lim {
}
k := 1
for i + k < 2*n+1 && i-k >= 0 {
if mana[i+k] == mana[i-k] {
k++
} else {
break
}
}
last = i
}
}

}
//fmt.Println(res, resIdx)
for k := resIdx-res; k <= resIdx+res; k++ {
if mana[k] != '*' {
resstr = append(resstr, mana[k])
}
}
return string(resstr)
}
func min(a, b int) int {
if a > b {
return b
}
return a
}

### 算法1

#### Golang 代码

func rob(nums []int) int {
n := len(nums)
if n == 0 {
return 0
} else if n == 1 {
return nums[0]
} else if n == 2 {
return max(nums[1], nums[0])
}
f := make([][2]int, n)
f[0][1] = nums[0]
for i := 1; i < n; i++ {
f[i][0] = max(f[i-1][0], f[i-1][1])
f[i][1] = f[i-1][0] + nums[i]
}
res := f[n-1][0]
f[1][0], f[1][1] = 0, nums[1]
for i := 2; i < n; i++ {
f[i][0] = max(f[i-1][0], f[i-1][1])
f[i][1] = f[i-1][0] + nums[i]
}
res = max(res, f[n-1][1])
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}

blablabla

blablabla

### 算法1

##### ($\mathcal{Tarjin}$缩点) $\mathcal O(n+m)$

$\mathbb 1$. 暴力做法直接建反图，枚举每个点看能否到达所有点，时间复杂度为平方级别，略高。

$\mathbb 2$. 优化做法是利用tarjin算法先将图缩点变成有向无环图，则在该图中，出度为0的强连通分量若只有一个，则说明有解，否则无解，而解的数量就是该出度为0的强连通分量的点的个数。

$\mathbb 3$. Tarjin算法复习：核心是通过dfs记录时间戳的方式，看能否遇见之前访问过的时间戳，遇到了说明就成环了，更新一路的时间戳。还需要通过栈来保存dfs访问节点的顺序，当碰到一个强连通分量的顶点后，就可以将此强连通分量出栈。

$\mathbb 4$. Tarjin重点数组：dfn保存节点的实际访问时间戳，low保存节点及它所有的子孙节点可以访问到的最小时间戳，若无环则dfn都等于low，并递增，若有环，则low要被更新为之前访问某点的dfn，因此会变小。stk保存所有还未形成强连通分量的点，instk标记点是否还在栈中。还需要视题目要求保存每个分量内点的个数，每个点对应哪个分量。同时最重要的一点，由于dfs的性质，最先形成的强连通分量一定在拓扑图中排最后，所以强连通分量的逆序即是拓扑序，这个性质可以保证不需要再进行拓扑排序了。

#### Golang 代码

package main
import (
"os"
"bufio"
"strings"
"strconv"
"fmt"
)
func main() {
sc := bufio.NewScanner(os.Stdin)
buf := make([]byte, 1024*1024)
sc.Buffer(buf, len(buf))
sc.Scan()
str := strings.Fields(sc.Text())
n, _ := strconv.Atoi(str[0])
m, _ := strconv.Atoi(str[1])
head, next, to := make([]int, n+1), make([]int, m+1), make([]int, m+1)
cnt := 0
scc_cnt := 0
timestamp := 0
dfn, low := make([]int, n+1), make([]int, n+1)
var stk []int
instk := make([]bool, n+1)
var size []int
id := make([]int, n+1)
add := func(a, b int) {
cnt++
}
for i := 1; i <= m; i++ {
sc.Scan()
str = strings.Fields(sc.Text())
a, _ := strconv.Atoi(str[0])
b, _ := strconv.Atoi(str[1])
}
var tarjin func(int)
tarjin = func(h int) {
timestamp++
dfn[h], low[h] = timestamp, timestamp
stk = append(stk, h)
instk[h] = true
for i := head[h]; i != 0; i = next[i] {
tot := to[i]
if dfn[tot] == 0 {
tarjin(tot)
low[h] = min(low[h], low[tot])
} else if instk[tot] {
low[h] = min(low[h], dfn[tot])
}
}
if dfn[h] == low[h] {
size = append(size, 0)
for {
top := stk[len(stk)-1]
stk = stk[:len(stk)-1]
size[len(size)-1]++
id[top] = scc_cnt
instk[top] = false
if top == h {
break
}
}
scc_cnt++
}
}
for i := 1; i <= n; i++ {
if dfn[i] == 0 {
tarjin(i)
}
}
deg := make([]int, scc_cnt)
for i := 1; i <= n; i++ {
for j := head[i]; j != 0; j = next[j] {
tot := to[j]
if id[i] != id[tot] {
deg[id[i]]++
}
}
}
ans_cnt := 0
ans := 0
for i := 0; i < scc_cnt; i++ {
if deg[i] == 0 {
ans_cnt++
ans = size[i]
}
}
if ans_cnt == 1 {
fmt.Println(ans)
} else {
fmt.Println(0)
}
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
func abs(a int) int {
if a > 0 {
return a
}
return -a
}

### 算法1

##### (倍增法) $\mathcal{O}((n+m)*log_2n)$

$\mathcal 1$. 预处理出每个节点的father数组，对于fa[i][k]，其含义为i号节点向上的第$2^k$个祖先节点的编号，从其定义不难看出可以利用递推求出。在具体求解时，还需要记录一个depth数组，保存i号节点的深度，规定根节点深度为1，利用bfs遍历树，对于每个出队的节点，可以利用该节点的深度更新所有其儿子节点的深度，同时还可以更新fa数组，假如i号节点有儿子j，则不难看出fa[j][0] = i，然后可以利用fa[j][0]继续往上更新fa[j][1],fa[j][2]…，规则为fa[j][k] = fa[fa[j][k-1]][k-1]。遍历完所有节点则depth和fa数组均预处理完毕。

$\mathcal 2$. 查询阶段，对于任意给定的两个节点a和b，思路是先看两个节点深度是否一致，不一致则将更深的节点上浮到浅的那一层，然后判断同深度的这两个节点是否是同一个，是则直接结束，否则还需要两个节点齐头并进上浮，直到两个节点到达同一个位置。具体而言，上浮是通过fa数组实现的，并且上浮的尺度是从大到小，逐位逼近，Tips是可以将depth[0]设为0，这样在更深节点上浮时，如果大尺度的上浮导致浮到了0号节点（无效节点），也可以继续缩小尺度循环（因为depth[0]一定不大于depth[b]）；当a和b深度一致后，通过判断fa[a][k]是否等于fa[b][k]，判断是否能结束循环，如果不等，则说明可以继续上浮$2^k$，最终结束时fa[a][0]就是答案了。

$\mathcal 3$. 本题就是在以上的基础上套了个距离，因为还是树，所以可以直接保存一个dist数组，在bfs时保存所有节点到root的距离，最终a和b和最短距离就是dist[a] + dist[b] - 2*dist[lca(a, b)]

#### Golang 代码

package main
import (
"os"
"bufio"
"strings"
"strconv"
"fmt"
)
func main() {
sc := bufio.NewScanner(os.Stdin)
buf := make([]byte, 1024*1024)
sc.Buffer(buf, len(buf))
sc.Scan()
str := strings.Fields(sc.Text())
n, _ := strconv.Atoi(str[0])
m, _ := strconv.Atoi(str[1])
head, next, to, w := make([]int, n+1), make([]int, n<<1), make([]int, n<<1), make([]int, n<<1)
cnt := 0
add := func(a, b, c int) {
cnt++
}
for i := 1; i < n; i++ {
sc.Scan()
str = strings.Fields(sc.Text())
a, _ := strconv.Atoi(str[0])
b, _ := strconv.Atoi(str[1])
c, _ := strconv.Atoi(str[2])
}
dist := make([]int, n+1)
depth := make([]int, n+1)
fa := make([][16]int, n+1)
for i := range dist {
depth[i] = 1<<31 - 1
}
depth[0], depth[1] = 0, 1
bfs := func(root int) {
q := []int{root}
for len(q) > 0 {
cur := q[0]
q = q[1:]
for i := head[cur]; i != 0; i = next[i] {
tot := to[i]
if depth[tot] > depth[cur] + 1 {
depth[tot] = depth[cur] + 1
dist[tot] = dist[cur] + w[i]
fa[tot][0] = cur
q = append(q, tot)
for k := 1; k <= 15; k++ {
fa[tot][k] = fa[fa[tot][k-1]][k-1]
}
}
}
}
}
bfs(1)
lca := func(a, b int) int {
if depth[a] < depth[b] {
a, b = b, a
}
for i := 15; i >= 0; i-- {
if depth[fa[a][i]] >= depth[b] {
a = fa[a][i]
}
}
if a == b {
return a
}
for i := 15; i >= 0; i-- {
if fa[a][i] != fa[b][i] {
a, b = fa[a][i], fa[b][i]
}
}
return fa[a][0]
}
for i := 1; i <= m; i++ {
sc.Scan()
str = strings.Fields(sc.Text())
a, _ := strconv.Atoi(str[0])
b, _ := strconv.Atoi(str[1])
fmt.Println(dist[a]+dist[b]-2*dist[lca(a, b)])
}
}

### 算法1

#### Golang 代码

package main
import (
"os"
"bufio"
"strings"
"strconv"
"fmt"
)
func main() {
sc := bufio.NewScanner(os.Stdin)
buf := make([]byte, 1024*1024)
sc.Buffer(buf, len(buf))
sc.Scan()
cases, _ := strconv.Atoi(sc.Text())
for cases > 0 {
cases--
sc.Scan()
n, _ := strconv.Atoi(sc.Text())
if n == 1 {
fmt.Println(1)
continue
}
head, next, to, w := make([]int, n+1), make([]int, n<<1+1), make([]int, n<<1+1), make([]int, n<<1+1)
cnt := 0
add := func(a, b, c int) {
cnt++
}
sc.Scan()
str := strings.Fields(sc.Text())
for i := 0; i < n; i++ {
l, _ := strconv.Atoi(str[(i-1+n)%n])
mid, _ := strconv.Atoi(str[(i+n)%n])
r, _ := strconv.Atoi(str[(i+1)%n])
if mid <= l && mid <= r {
} else {
if mid > l {
}
if mid > r {
}
}
}
spfa := func() int {
dist := make([]int, n+1)
q := []int{n}
inq := make([]bool, n+1)
for len(q) > 0 {
cur := q[len(q)-1]
q = q[:len(q)-1]
inq[cur] = false
for i := head[cur]; i != 0; i = next[i] {
tot := to[i]
if dist[tot] < dist[cur] + w[i] {
dist[tot] = dist[cur] + w[i]
if !inq[tot] {
q = append(q, tot)
inq[tot] = true
}
}
}
}
ans := 0
for i := 0; i < n; i++ {
ans += dist[i]
}
return ans
}
fmt.Println(spfa())
}
}

#### Go 代码

func printMatrix(matrix [][]int) []int {
if len(matrix) == 0 {
return nil
}
r, c := len(matrix), len(matrix[0])
var res []int
for i, j := 0, 0; i <= (r-1)>>1 && j <= (c-1)>>1; i, j = i+1, j+1 {
res = append(res, matrix[i][j:c-j]...)
for k := i+1; k < r-i-1; k++ {
res = append(res, matrix[k][c-j-1])
}
if r-i-1 != i {
for k := c-j-1; k >= j; k-- {
res = append(res, matrix[r-i-1][k])
}
}
if c-j-1 != j {
for k := r-i-2; k >= i+1; k-- {
res = append(res, matrix[k][j])
}
}
}
return res
}