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

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

简单题 小美的外卖订单编号

• 订单编号从 1 开始，每发起一个订单编号加 1。当订单编号达到上限 m 后，下一个订单编号又从 1 开始。
• 这种规则可以用数学中的取模运算来描述：
  • 如果当前订单编号为 x，则其对应的实际编号可以通过公式 (x-1)%m + 1 计算。
    • (x - 1) → 让编号从 0 开始好做循环。
    • % m → 保证编号在 0 ~ m-1 之间循环。
    • + 1 → 让编号重新回到 1 ~ m。

package main

import "fmt"

func main() {
	var q int
	fmt.Scan(&q)
	for i := 0; i < q; i++ {
		var m, x int
		fmt.Scan(&m, &x)
		fmt.Println((x-1)%m + 1)
	}
}

中等题 买卖股票的最好时机(一)

• 如果在某一天买入股票，那么我们需要在之后价格最高的那一天卖出，才能获得最大利润。
• 因此，问题的核心是记录当前最低买入价格，并计算每一天卖出时的潜在利润。

package main

import (
	"fmt"
	"math"
)

func main() {
	var n int
	fmt.Scan(&n)
	ans, minPrice := 0, math.MaxInt
	for i := 0; i < n; i++ {
		var v int
		fmt.Scan(&v)
		if v < minPrice {
			minPrice = v
		}
		if v-minPrice > ans {
			ans = v - minPrice
		}
	}
	fmt.Println(ans)
}

困难题 数位染色

1. 问题转化：子集和问题

首先，计算所有数字的总和 sum 。

• 如果 sum 是奇数，则无法平分，直接返回 "No"。
• 如果 sum 是偶数，则问题转化为：是否能从这些数字中选出一个子集，使得子集的数字之和等于 sum/2 。

这实际上是一个经典的子集和问题（Subset Sum Problem）。

2. 动态规划解决子集和问题

我们使用动态规划来判断是否存在一个子集，其数字之和等于 sum/2 。

动态规划的状态定义

• 定义 dp[i] 表示是否可以通过选择某些数字，使得它们的和为 i 。
• 初始状态：dp[0] = true（和为 0 的情况总是可行的）。

状态转移方程

• 对于每个数字 d（即 x 的每一位数字），从大到小更新 dp 数组： ，其中 j 从 到 0。
  • 这里的从大到小更新是为了避免重复使用同一个数字。

package main

import (
	"fmt"
)

func main() {
	var s string
	fmt.Scan(&s)
	sum := 0
	for _, c := range s {
		sum += int(c - '0')
	}
	if sum%2 != 0 {
		fmt.Println("No")
		return
	}
	dp := make([]bool, sum/2+1)
	dp[0] = true
	for _, c := range s {
		d := int(c - '0')
		for j := sum/2 - d; j >= 0; j-- {
			dp[j+d] = dp[j+d] || dp[j]
		}
	}
	if dp[sum/2] {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}