2025B难题练习

1.启动多任务排序

拓扑排序
每次选入度为0的点
对每次选的点进行排序

package mainimport ("bufio""fmt""os""slices""strings"
)func main() {scanner := bufio.NewScanner(os.Stdin)scanner.Scan()text := scanner.Text()relations := strings.Split(text, " ")inNum := make(map[string]int)NodeEdge := make(map[string][]string)for i := 0; i < len(relations); i++ {parts:=strings.Split(relations[i],"->")r := string(parts[0])l := string(parts[1])inNum[r]++if _, ok := inNum[l]; !ok {inNum[l] = 0}NodeEdge[l] = append(NodeEdge[l], r)}//fmt.Println(inNum)queue := []string{}for k, v := range inNum {//fmt.Println("=====", string(k+'A'))if v == 0 {queue = append(queue, k)//fmt.Println(string(r+'A'), "---r")}}ans := []string{}for len(queue) > 0 {slices.Sort(queue)tmp := []string{}for i := 0; i < len(queue); i++ {ans = append(ans, queue[i])for _, r := range NodeEdge[queue[i]] {inNum[r]--if inNum[r] == 0 {//fmt.Println("+++", r)tmp = append(tmp, r)}}}queue = tmp}fmt.Println(strings.Join(ans, " "))}

2.欢乐周末

package mainimport ("bufio""fmt""os""strconv""strings"
)var n, m inttype pair struct{ x, y int }var visit1 [][]bool
var visit2 [][]bool
var grid [][]int
var start []pair
var dst []pairfunc main() {scanner := bufio.NewScanner(os.Stdin)scanner.Scan()input := scanner.Text()relations := strings.Split(input, " ")n, _ = strconv.Atoi(relations[0])m, _ = strconv.Atoi(relations[1])grid = make([][]int, n)visit1 = make([][]bool, n)visit2 = make([][]bool, n)for i := 0; i < n; i++ {scanner.Scan()input = scanner.Text()line := strings.Split(input, " ")grid[i] = make([]int, m)visit1[i] = make([]bool, m)visit2[i] = make([]bool, m)for j := 0; j < m; j++ {grid[i][j], _ = strconv.Atoi(line[j])if grid[i][j] == 2 {start = append(start, pair{i, j})}if grid[i][j] == 3 {dst = append(dst, pair{i, j})}}}bfs(start[0].x, start[0].y, visit1)bfs(start[1].x, start[1].y, visit2)ans := 0for _, v := range dst {//fmt.Println(v)if visit1[v.x][v.y] && visit2[v.x][v.y] {ans++}}fmt.Println(ans)
}
func bfs(i, j int, visit [][]bool) {queue := []pair{}queue = append(queue, pair{i, j})//入队时就标记为truevisit[i][j] = truefor len(queue) > 0 {tmp := []pair{}for i := 0; i < len(queue); i++ {now := queue[i]dx := []int{1, 0, -1, 0}dy := []int{0, 1, 0, -1}for k := 0; k < 4; k++ {nx := dx[k] + now.xny := dy[k] + now.yif nx >= 0 && ny >= 0 && nx < n && ny < m && grid[nx][ny] != 1 && !visit[nx][ny] {tmp = append(tmp, pair{nx, ny})visit[nx][ny] = true}}}queue = tmp}
}

3.返回矩阵中非1的元素个数

package mainimport ("bufio""fmt""os""strconv""strings"
)type pair struct{ x, y int }var n, m int// var visit [][]bool
var grid [][]intfunc main() {scanner := bufio.NewScanner(os.Stdin)scanner.Scan()text := scanner.Text()line := strings.Split(text, " ")n, _ = strconv.Atoi(line[0])m, _ = strconv.Atoi(line[1])grid = make([][]int, n)//visit = make([][]bool, n)for i := 0; i < n; i++ {scanner.Scan()text = scanner.Text()line = strings.Split(text, " ")grid[i] = make([]int, m)//visit[i] = make([]bool, m)for j := 0; j < m; j++ {grid[i][j], _ = strconv.Atoi(line[j])}}bfs(0, 0)ans := 0for i := 0; i < n; i++ {//fmt.Println(grid[i])for j := 0; j < m; j++ {if grid[i][j] != 1 {ans++}}}fmt.Println(ans)}
func bfs(i int, j int) {grid[i][j] = 1queue := []pair{}queue = append(queue, pair{i, j})for len(queue) > 0 {dx := []int{1, 0, -1, 0}dy := []int{0, 1, 0, -1}tmp := []pair{}for i := 0; i < len(queue); i++ {now := queue[i]//fmt.Println("now", now.x, now.y)for k := 0; k < 4; k++ {nx := dx[k] + now.xny := dy[k] + now.y//fmt.Println("nx,ny", nx, ny)if nx >= 0 && ny >= 0 && nx < n && ny < m && grid[nx][ny] == 0 {grid[nx][ny] = 1//fmt.Println("add:", nx, ny)tmp = append(tmp, pair{nx, ny})//fmt.Println(tmp)}}}queue = tmp//fmt.Println("queue", queue, len(queue))}
}

4. 爱吃蟠桃的孙悟空

package mainimport ("bufio""fmt""os""strconv""strings"
)var nums []intfunc main() {scanner := bufio.NewScanner(os.Stdin)scanner.Scan()text := scanner.Text()line := strings.Split(text, " ")for i := 0; i < len(line); i++ {num, _ := strconv.Atoi(line[i])nums = append(nums, num)}//fmt.Println("nums", nums)scanner.Scan()text = scanner.Text()time, _ := strconv.Atoi(text)l, r := 1, 100010for l < r {mid := (l + r) >> 1if check(mid) <= time {r = mid} else {l = mid + 1}//fmt.Println("l,r", l, r)}if check(l) <= time {fmt.Println(l)} else {fmt.Println(0)}//fmt.Println("+++", check(1))
}
func check(k int) int {ans := 0//注意这里tmp := make([]int, len(nums))copy(tmp, nums)for i := 0; i < len(tmp); i++ {for tmp[i] > 0 {//fmt.Println("tmp:", tmp[i])ans++//fmt.Println("ans", ans)tmp[i] -= k}}return ans
}

5.矩阵匹配

匈牙利算法

package mainimport ("bufio""fmt""math""os""strconv""strings"
)var (n, m, k intnums    [][]intmatch   []intvisit   []bool
)func main() {scanner := bufio.NewScanner(os.Stdin)scanner.Scan()text := scanner.Text()line := strings.Split(text, " ")n, _ = strconv.Atoi(line[0])m, _ = strconv.Atoi(line[1])k, _ = strconv.Atoi(line[2])nums = make([][]int, n)minNum := math.MaxInt maxNum := math.MinInt for i := 0; i < n; i++ {scanner.Scan()text = scanner.Text()line = strings.Split(text, " ")nums[i] = make([]int, m)for j := 0; j < m; j++ {nums[i][j], _ = strconv.Atoi(line[j])minNum = min(minNum, nums[i][j])maxNum = max(maxNum, nums[i][j])}}l, r := minNum, maxNumfor l <= r {mid := (l + r) >> 1if valid(mid) >= n-k+1 {r=mid-1} else {l = mid+1}}fmt.Println(r+1)}
func valid(maxValue int) int {match = make([]int, m)for i := 0; i < m; i++ {match[i] = -1}cnt := 0for i := 0; i < n; i++ {visit = make([]bool, m)if dfs(i, maxValue) {cnt++}}return cnt
}
func dfs(i int, maxValue int) bool {for j := 0; j < m; j++ {if !visit[j] && nums[i][j] <= maxValue {visit[j] = trueif match[j] == -1 || dfs(match[j], maxValue) {match[j] = ireturn true}}}return false
}

6.荒岛求生

注意特殊情况，数字个数=0或>30000或者数字=0
从左往右遍历
积累Right的力量，算往左的人走能活几个
从右往左遍历
积累Left的力量，算往右的人走能活几个

ans=左边活的人+右边活的人

package mainimport ("bufio""fmt""os""strconv""strings"
)func main() {var nums []intscanner := bufio.NewScanner(os.Stdin)scanner.Scan()text := scanner.Text()line := strings.Split(text, " ")n := len(line)if n > 30000 || n == 0 {fmt.Println(-1)return}for i := 0; i < n; i++ {x, _ := strconv.Atoi(line[i])if x==0 {fmt.Println(-1)return}nums = append(nums, x)}sumRight := 0cnt := 0for i := 0; i < n; i++ {if nums[i] > 0 {sumRight += nums[i]} else {numValue := -nums[i]if numValue > sumRight {cnt++sumRight = 0} else {sumRight -= numValue}}}sumLeft := 0for i := n - 1; i >= 0; i-- {if nums[i] < 0 {sumLeft += -nums[i]} else {if nums[i] > sumLeft {sumLeft = 0cnt++} else {sumLeft -= nums[i]}}}fmt.Println(cnt)}

7.无向图染色

package mainimport "fmt"type pair struct{ x, y int }func main() {var n, m intfmt.Scan(&n, &m)if m == 0 {fmt.Println(1 << n)return}edge := []pair{}for i := 0; i < m; i++ {var x, y intfmt.Scan(&x, &y)edge = append(edge, pair{x, y})}ans := 0for i := 0; i < 1<<n; i++ {flag := truefor j := 0; j < m; j++ {x, y := edge[j].x, edge[j].yif i>>(x-1)&1 == 1 && i>>(y-1)&1 == 1 {flag = falsebreak}}if flag {ans++}}fmt.Println(ans)}