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

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

简单题 小苯的比赛上分

1. 使用优先队列（最小堆）

为了高效地找到当前分数最低的账号，我们可以使用一个最小堆（Priority Queue）。最小堆的特点是堆顶元素始终是最小值，因此每次可以直接取出堆顶元素作为参赛账号。

2. 更新分数并维护最大值

每次取出堆顶元素后，将其分数加上比赛得分 x ，然后将更新后的分数重新放回堆中。同时，我们需要用一个变量 mx 记录当前所有账号中的最大分数，并在每次更新时检查是否需要更新 mx。

package main

import (
	"container/heap"
	"fmt"
)

type PriorityQueue []int

func (pq PriorityQueue) Len() int           { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i] < pq[j] }
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.(int))
}

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

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	a := make(PriorityQueue, n)
	mx := 0
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
		mx = max(mx, a[i])
	}
	heap.Init(&a)
	for i := 0; i < m; i++ {
		var x int
		fmt.Scan(&x)
		v := heap.Pop(&a).(int)
		mx = max(v+x, mx)
		fmt.Println(mx)
		heap.Push(&a, v+x)
	}
}

中等题 小欧安排座位

• 将小朋友分为两类：
  • 希望是不独特的：直接将他们的编号与座位编号对应（即 a[i] = i）。
  • 希望是独特的：需要重新安排座位，使得他们的编号与座位编号不相等。
    • 将这些小朋友的编号存入一个数组，通过循环移位的方式，确保每个小朋友的座位编号不等于其自身编号。

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	var s string
	fmt.Scan(&s)
	s = " " + s
	a := make([]int, n+1)
	var b []int
	for i := 1; i <= n; i++ {
		if s[i] == '0' {
			a[i] = i
		} else {
			b = append(b, i)
		}
	}
	for i := 0; i < len(b); i++ {
		a[b[i]] = b[(i+1)%len(b)]
	}
	for i := 1; i <= n; i++ {
		fmt.Print(a[i], " ")
	}
}

困难题 小苯的数字权值

1. 预处理质数：
   • 使用埃拉托色尼筛法预先生成一定范围内的质数列表。
2. 质因数分解：
   • 对输入的 x 进行质因数分解，记录每个质因数的指数。
3. 计算两种策略的权值：
   • 策略 1：直接保留 x，权值为 。
   • 策略 2：分解为质因数幂次，权值为 。
4. 输出结果：
   • 输出两种策略中权值的最大值。

package main

import "fmt"

var (
	st    []bool
	prime []int
)

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func getPrime(n int) {
	st = make([]bool, n+1)
	for i := 2; i <= n; i++ {
		if !st[i] {
			prime = append(prime, i)
		}
		for _, p := range prime {
			if i*p > n {
				break
			}
			st[i*p] = true
			if i%p == 0 {
				break
			}
		}
	}
}

func solve() {
	var n int
	fmt.Scan(&n)
	ans1, ans2 := 1, 0
	for i, p := range prime {
		if i > n {
			break
		}
		cnt := 0
		for n%p == 0 {
			n /= p
			cnt++
		}
		if cnt > 0 {
			ans1 *= cnt + 1
			ans2 += cnt * 2
		}
	}
	fmt.Println(max(ans1, ans2))
}

func main() {
	getPrime(2e5)
	var t int
	fmt.Scan(&t)
	for i := 0; i < t; i++ {
		solve()
	}
}