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

简单题小红的整数配对

排序数组：首先将数组 a 按降序排序。这样做的目的是为了尽量选择较大的数进行配对，因为较大的数相乘会得到更高的分数。
遍历数组：从数组的第一个元素开始遍历，每次检查当前元素和下一个元素的差值是否小于等于 k。
- 如果满足条件，则将这两个数的乘积加到总分中，并跳过这两个数（即将索引增加 2）。
- 如果不满足条件，则只跳过当前元素（即将索引增加 1）。
输出结果：遍历结束后，输出累积的总分。

package main

import (
	"fmt"
	"sort"
)

func main() {
	var (
		n int
		k int64
	)
	fmt.Scan(&n, &k)
	a := make([]int64, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
	}
	sort.Slice(a, func(i, j int) bool {
		return a[i] > a[j]
	})
	ans := int64(0)
	for i := 0; i+1 < n; {
		if a[i]-a[i+1] <= k {
			ans += a[i] * a[i+1]
			i += 2
		} else {
			i++
		}
	}
	fmt.Println(ans)
}

中等题小红的取模构造

特殊情况处理：
- 当 a = 0 且 b = 0 时，取 x = 1, y = 1（最简单的解）
- 当 a = b 时，无解（返回 -1, -1），因为不可能同时有 x mod y = y mod x
一个数为0的情况：
- 当 a = 0 时，意味着 x mod y = 0，所以 y 必须能整除 x
- 当 b = 0 时，意味着 y mod x = 0，所以 x 必须能整除 y
一般情况处理：
- 当 a > b 时，取 x = a, y = a+b
- 当 a < b 时，取 x = a+b, y = b

这个实现是正确的，因为：

对于 a = 0, b ≠ 0 的情况：取 x = b+b, y = b 时，b+b mod b = 0 = a 且 b mod (b+b) = b
对于 b = 0, a ≠ 0 的情况：取 x = a, y = a+a 时，a mod (a+a) = a 且 (a+a) mod a = 0 = b
对于一般情况：方案保证了所有答案都是正整数，并且满足取模的要求

package main

import "fmt"

func main() {
	var t int
	fmt.Scan(&t)
	for i := 0; i < t; i++ {
		var a, b, x, y int
		fmt.Scan(&a, &b)
		if a == 0 && b == 0 {
			x, y = 1, 1
		} else if a == b {
			x, y = -1, -1
		} else if a == 0 {
			x, y = b+b, b
		} else if b == 0 {
			x, y = a, a+a
		} else if a > b {
			x, y = a, a+b
		} else {
			x, y = a+b, b
		}
		fmt.Println(x, y)
	}
}

困难题【模板】单源最短路Ⅲ ‖ 非负权图

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

#牛客春招刷题训练营#

牛客春招刷题训练营文章被收录于专栏

爱丽姐真是太好了