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

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

简单题 小红的魔法药剂

对于每种药剂 i ，我们有以下两种选择：

1. 选择红色版本：直接支付 a[i] 的成本。
2. 选择蓝色版本：支付 a[x] + a[y] 的成本。

对每种药剂取 min(a[i], b[i]) 的和作为答案

package main

import "fmt"

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	var n int
	fmt.Scan(&n)
	a := make([]int, n+1)
	for i := 1; i <= n; i++ {
		fmt.Scan(&a[i])
	}
	b := make([]int, n+1)
	for i := 1; i <= n; i++ {
		var x, y int
		fmt.Scan(&x, &y)
		b[i] = a[x] + a[y]
	}
	ans := 0
	for i := 1; i <= n; i++ {
		ans += min(a[i], b[i])
	}
	fmt.Println(ans)
}

中等题 游游的字母翻倍

1. 模拟操作：
   • 每次操作直接对字符串进行修改，将指定区间内的每个字符重复一次并插入到其后面。
   • 由于字符串是可变的，每次操作都会改变其长度和内容。
2. 区间操作细节：
   • 对于给定区间 ([l, r])，我们需要：
     • 提取区间外的部分（即 ([0, l-1]) 和 ([r+1, n-1])）。
     • 遍历区间内的每个字符，将其重复一次并拼接到结果中。
     • 将三部分拼接起来形成新的字符串。
3. 多次操作的处理：
   • 按照输入顺序依次执行每一步操作。
   • 每次操作后更新字符串，作为下一步操作的基础。

package main

import "fmt"

func main() {
	var n, q int
	fmt.Scan(&n, &q)
	var s string
	fmt.Scan(&s)
	for i := 0; i < q; i++ {
		var l, r int
		fmt.Scan(&l, &r)
		l--
		r--
		t := s[:l]
		for j := l; j <= r; j++ {
			t += string(s[j]) + string(s[j])
		}
		t += s[r+1:]
		s = t
	}
	fmt.Println(s)
}

困难题 游游的数值距离

1. 预先计算并存储所有可能需要的阶乘值。
2. 使用公式计算每个 x 对应的 y 值的上下界。
3. 在计算出的 y 值范围内遍历，寻找使表达式 最小的 x 和 y。
4. 打印找到的最优 x 和 y。

package main

import "fmt"

func abs(n int) int {
	if n < 0 {
		return -n
	}
	return n
}

func ceil(a, b int) int {
	if a%b == 0 {
		return a / b
	}
	return a/b + 1
}

func main() {
	var n int
	fmt.Scan(&n)
	factorials := make([]int, 14)
	factorials[0] = 1
	for i := 1; i <= 13; i++ {
		factorials[i] = factorials[i-1] * i
	}
	bestX, bestY, bestV := 1, 1, abs(n)
	for x := 3; x <= 13; x++ {
		y1, y2 := n/(factorials[x]-1), ceil(n, factorials[x]-1)
		for y := y1 - 1; y <= y2+1; y++ {
			if y == 2 || y <= 0 {
				continue
			}
			v := abs(n - (factorials[x]-1)*y)
			if v < bestV {
				bestX, bestY, bestV = x, y, v
			}
		}
	}
	fmt.Printf("%d %d\n", bestX, bestY)
}