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

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

简单题 进制转换

方案一：正常做法

定义一个十六进制转十进制的函数 hex2dec 函数（注意传入的 hex 要去除 0x）

1. 初始化变量：dec 变量初始化为 0，用于存储最终的十进制结果。
2. 遍历字符串：使用 for 循环遍历 hex 字符串的每一个字符。
3. 字符转换：
   • 如果字符在 '0' 和 '9' 之间，说明是数字字符，将其转换为相应的十进制值并累加到 dec 中。
   • 如果字符在 'A' 和 'F' 之间，说明是字母字符，将其转换为相应的十进制值（'A' 对应 10，'B' 对应 11，以此类推）并累加到 dec 中。
4. 返回结果：循环结束后，返回计算得到的十进制值 dec。

该函数通过逐个字符处理十六进制字符串，将每个字符转换为相应的十进制值，并累加到结果中，最终实现了十六进制到十进制的转换。

package main

import (
	"fmt"
)

func hex2dec(hex string) int {
	dec := 0
	for i := 0; i < len(hex); i++ {
		if hex[i] >= '0' && hex[i] <= '9' {
			dec = dec*16 + int(hex[i]-'0')
		} else if hex[i] >= 'A' && hex[i] <= 'F' {
			dec = dec*16 + int(hex[i]-'A'+10)
		}
	}
	return dec
}

func main() {
	var s string
	fmt.Scan(&s)
	fmt.Println(hex2dec(s[2:]))
}

方案二：利用格式化符号

1. 声明一个字符串变量 s 用于存储输入。
2. 使用 fmt.Scan 函数读取用户输入的字符串。
3. 声明一个整数变量 n 用于存储转换后的十进制数。
4. 使用 fmt.Sscanf 函数从字符串的==第三个字符==开始读取，并将其按==十六进制格式==转换为整数存储在 n 中。
   • 输入的字符串前两个字符是无关的（例如 0x），从第三个字符开始才是有效的十六进制数。
5. 使用 fmt.Printf 函数以==十进制格式==输出整数 n。

package main

import "fmt"

func main() {
	var s string
	fmt.Scan(&s)
	var n int
	fmt.Sscanf(s[2:], "%X", &n)
	fmt.Printf("%d\n", n)
}

方案三：利用 strconv.ParseInt 函数

strconv.ParseInt 函数的签名如下：

func ParseInt(s string, base int, bitSize int) (i int64, err error)

• s：要解析的字符串。
• base：字符串的进制数，可以是 0、2 到 36 之间的任意值。如果 base 为 0，函数会根据字符串前缀自动确定进制数。
• bitSize：目标整数的位大小，可以是 0、8、16、32 或 64。

返回值：

• i：解析后的整数值。
• err：如果解析过程中出现错误，会返回一个错误对象。

package main

import (
	"fmt"
	"strconv"
)

func main() {
	var s string
	fmt.Scan(&s)
	n, _ := strconv.ParseInt(s, 0, 64)
  // n, _ := strconv.ParseInt(s[2:], 16, 64)
	fmt.Println(n)
}

中等题 合并表记录

利用 map 来储存索引的数值，其中 key 是索引，value 是数值累加和。

如果直接输出 map 的键值对，键的顺序是随机的。因为 map 在 Go 中实现是哈希表，是无序的。如果你需要按特定顺序（例如按键的升序）输出 map 中的键值对，就需要先将键存储到一个切片中并进行排序，然后按排序后的顺序输出键值对。

package main

import (
	"fmt"
	"sort"
)

func main() {
	var n int
	fmt.Scan(&n)
	m := make(map[int]int)
	for i := 0; i < n; i++ {
		var x, y int
		fmt.Scan(&x, &y)
		m[x] += y
	}

	var keys []int
	for k := range m {
		keys = append(keys, k)
	}
	sort.Ints(keys)
	for _, k := range keys {
		fmt.Println(k, m[k])
	}
}

困难题 称砝码

把砝码看作物品，天平看作背包，这题就可以看成是背包容量无限大（不考虑容量）的多重背包问题的变形问题。

其中，砝码的重量就是物品价值，天平所称得的最大重量即为背包容量。

我们可以根据数据范围计算背包容量的理论极限最大值是 10*2000*10=200000

dp[i] 的含义：是否存在背包容量为 i 的情况

动态规划状态转移

• 遍历每个物品。
• 对于每个物品，遍历其数量。
• 对于每个数量，更新 dp 数组，检查当前重量减去物品重量的位置是否可以达到，如果可以，则当前重量也可以达到。

注意点：一维情况下枚举背包容量需要逆序 for k := 200000; k >= weights[i].m; k--

在一维情况下枚举背包容量需要逆序是为了避免重复计算和覆盖问题。具体来说，当你在处理背包问题时，如果你正序枚举容量，那么在更新 dp 数组时，可能会使用到已经更新过的值，从而导致错误的结果。

例如，假设你有一个物品的重量为 m，并且你正序枚举容量 k：

1. 当你处理容量 k 时，你会更新 dp[k] 为 dp[k - m] 的值。
2. 如果你正序枚举，那么在处理容量 k + 1 时，dp[k + 1] 可能会使用到已经更新过的 dp[k] 的值，这会导致错误的结果。

通过逆序枚举容量，你可以确保在更新 dp[k] 时，dp[k - m] 仍然是未更新的值，从而避免重复计算和覆盖问题。

package main

import (
	"fmt"
)

type weight struct {
	m int
	x int
}

func main() {
	var n int
	fmt.Scan(&n)
	weights := make([]weight, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&weights[i].m)
	}
	for i := 0; i < n; i++ {
		fmt.Scan(&weights[i].x)
	}
	dp := make([]bool, 200001)
	dp[0] = true
	for i := 0; i < n; i++ {
		for j := 0; j < weights[i].x; j++ {
			for k := 200000; k >= weights[i].m; k-- {
				if dp[k-weights[i].m] {
					dp[k] = true
				}
			}
		}
	}
	count := 0
	for i := 0; i <= 200000; i++ {
		if dp[i] {
			count++
		}
	}
	fmt.Println(count)
}