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

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

简单题小红吃药

输入处理：

n：表示症状的总数
s：一个字节切片，用'1'和'0'表示每种症状是否存在（1表示有症状，0表示无症状）
m：表示药品的总数

药品信息存储：

med数组存储每种药品的信息
med[i][0]：表示第i种药能治疗哪些症状（1表示能治疗，0表示不能治疗）
med[i][1]：表示第i种药会产生哪些副作用（1表示会产生，0表示不会产生）

服药过程模拟：

for i := 0; i < n; i++ {
    // 如果当前有症状(s[i]=='1')且药能治疗这个症状(med[u][0][i]=='1')
    if s[i] == '1' && med[u][0][i] == '1' {
        s[i] = '0'  // 治愈该症状
    }
    // 如果药会产生这个副作用(med[u][1][i]=='1')
    if med[u][1][i] == '1' {
        s[i] = '1'  // 产生新症状
    }
}

结果输出：

每次服用药品后，使用bytes.Count统计当前还存在多少个症状（计算字节切片中'1'的个数）

package main

import (
	"bytes"
	"fmt"
)

func main() {
	var (
		n int
		s []byte
		m int
	)
	fmt.Scan(&n, &s, &m)
	med := make([][2]string, m+1)
	for i := 1; i <= m; i++ {
		fmt.Scan(&med[i][0], &med[i][1])
	}
	var q int
	fmt.Scan(&q)
	for ; q > 0; q-- {
		var u int
		fmt.Scan(&u)
		for i := 0; i < n; i++ {
			if s[i] == '1' && med[u][0][i] == '1' {
				s[i] = '0'
			}
			if med[u][1][i] == '1' {
				s[i] = '1'
			}
		}
		fmt.Println(bytes.Count(s, []byte("1")))
	}
}

中等题小红和小紫的取素因子游戏

每次操作必须选择一个质因子进行除法，当无法找到质因子时（即数字变为1）游戏结束。

总操作次数等于质因子的总个数，因此质因子个数的奇偶性决定了最后谁会操作。

如果质因子总数是偶数，则小紫（yukari）获胜，如果质因子总数是奇数，则小红（kou）获胜。

package main

import "fmt"

func main() {
	var t int
	fmt.Scan(&t)
	for i := 0; i < t; i++ {
		var x int
		fmt.Scan(&x)
		cnt := 0
		for j := 2; j <= x/j; j++ {
			for x%j == 0 {
				x /= j
				cnt++
			}
		}
		if x > 1 {
			cnt++
		}
		if cnt%2 == 0 {
			fmt.Println("yukari")
		} else {
			fmt.Println("kou")
		}
	}
}

困难题小红送外卖

问题分析：

从1号点（美食街）出发到达目标学校，再返回1号点
需要计算多个查询点到1号点的最短距离之和
由于是往返路径，最终结果需要乘以2

代码实现要点：

使用Dijkstra算法求解单源最短路
图的存储采用邻接表方式
使用优先队列优化Dijkstra算法的性能

Dijkstra()函数实现：

初始化距离数组，除起点外都设为INF
使用优先队列维护节点
每次取出距离最小的未访问节点
更新当前节点的所有邻接节点的距离

处理查询：

读入q个查询点
对每个查询点x，累加dis[x]（即1到x的最短距离）
最后将总距离乘以2（因为是往返路径）

package main

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

type Edge struct {
	to, cost int
}

const N = 100010
const INF int = 1e9

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

func initGraph() {
	for i := 2; i <= n; i++ {
		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, 1})

	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 addEdge(x, y int, z int) {
	g[x] = append(g[x], Edge{to: y, cost: z})
	g[y] = append(g[y], Edge{to: x, cost: z})
}

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

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

	for i := 0; i < m; i++ {
		var u, v, w int
		fmt.Fscan(in, &u, &v, &w)
		addEdge(u, v, w)
	}

	Dijkstra()

	ans := 0
	for i := 1; i <= q; i++ {
		var x int
		fmt.Fscan(in, &x)
		ans += dis[x]
	}
	fmt.Fprintln(out, ans*2)
}

#牛客春招刷题训练营#

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

爱丽姐真是太好了