牛客春招刷题训练营-2025.5.26题解

活动地址： 牛客春招刷题训练营 - 编程打卡活动

简单题 小红的矩阵

• 使用两层循环遍历 n × m 的矩阵
• 通过 a%10 == 9 判断一个数字的个位是否为 9
• 使用 cnt 变量记录满足条件的数字个数

package main

import "fmt"

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	cnt := 0
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			var a int
			fmt.Scan(&a)
			if a%10 == 9 {
				cnt++
			}
		}
	}
	fmt.Println(cnt)
}

中等题 游游的最小公倍数

1. 最小公倍数的性质：
   • 最小公倍数 lcm(a, b) 和最大公约数 gcd(a, b) 的关系是：
   • 因此，为了让 lcm(a, b) 尽可能大，我们需要让 gcd(a, b) 尽可能小。理想情况下，gcd(a, b) = 1（即 a 和 b 互质）。
2. 分解 n：
   • 我们需要将 n 分解为 a + b = n，其中 。
   • 初始可以令 和 ，这样可以让 a 和 b) 尽量接近。
3. 调整 a 和 b：
   • 如果 gcd(a, b) > 1，则说明 a 和 b 不互质，此时需要调整 a 和 b 的值。
   • 调整的方式是逐步减小 a 并增大 b，直到 gcd(a, b) = 1。

package main

import "fmt"

func gcd(a, b int64) int64 {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func main() {
	var t int
	fmt.Scan(&t)
	for i := 0; i < t; i++ {
		var n int64
		fmt.Scan(&n)
		a, b := n/2, n-n/2
		for gcd(a, b) != 1 {
			a--
			b++
		}
		fmt.Println(a, b)
	}
}

困难题 【模板】单源最短路Ⅰ ‖ 无权图

1. 输入处理：
   • 读取图的顶点数 n、边数 m 和起点 s。
   • 构建图的邻接表表示。每条边用一个结构体 Edge 表示，包含目标顶点 to 和边的权重 cost。
2. 初始化：
   • 使用数组 dis 存储从起点 s 到每个顶点的最短距离，初始时将起点的距离设为0，其余顶点的距离设为无穷大（即 INF）。
   • 使用布尔数组 vis 标记顶点是否已被访问过，初始时所有顶点都未被访问。
3. Dijkstra算法：
   • 使用优先队列（最小堆）来选择当前距离起点最近的未访问顶点。
   • 每次从优先队列中取出距离最小的顶点 v，如果该顶点已经被访问过，则跳过；否则标记为已访问。
   • 遍历顶点 v 的所有邻接边，更新相邻顶点的最短距离。如果发现更短的路径，则更新距离并将该顶点加入优先队列。
4. 输出结果：
   • 遍历所有顶点，输出从起点 s 到每个顶点的最短路径长度。如果某个顶点不可达（即距离仍为 INF），则输出 -1。

package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
)

type Edge struct {
	to, cost int
}

const N = 2000010
const INF int = 1e9

var (
	g       [N][]Edge
	dis     [N]int
	vis     [N]bool
	n, m, s int
)

func initGraph() {
	for i := 1; i <= n; i++ {
		if i == s {
			dis[i] = 0
		} else {
			dis[i] = INF
		}
	}
}

type PII struct {
	first, second int
}

type PriorityQueue []PII

func (pq PriorityQueue) Len() int           { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].first < pq[j].first }
func (pq PriorityQueue) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }

func (pq *PriorityQueue) Push(x interface{}) {
	*pq = append(*pq, x.(PII))
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

func Dijkstra() {
	initGraph()
	pq := &PriorityQueue{}
	heap.Init(pq)
	heap.Push(pq, PII{0, s})

	for pq.Len() > 0 {
		t := heap.Pop(pq).(PII)
		v := t.second

		if vis[v] {
			continue
		}
		vis[v] = true

		for _, e := range g[v] {
			if dis[e.to] > dis[v]+e.cost {
				dis[e.to] = dis[v] + e.cost
				heap.Push(pq, PII{dis[e.to], e.to})
			}
		}
	}
}

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	fmt.Fscan(in, &n, &m, &s)

	for i := 0; i < m; i++ {
		var u, v int
		fmt.Fscan(in, &u, &v)
		g[u] = append(g[u], Edge{to: v, cost: 1})
	}

	Dijkstra()

	for i := 1; i <= n; i++ {
		if dis[i] == INF {
			fmt.Fprint(out, "-1 ")
		} else {
			fmt.Fprint(out, dis[i], " ")
		}
	}
}