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

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

简单题 求最大连续bit数

1. 输入一个整数 n
2. 通过位运算遍历这个整数的每一位（从低位到高位，总共64位）：
   • 使用 n>>i 将数字右移 i 位
   • 使用 &1 判断最低位是否为1
3. 使用两个变量：
   • l：记录当前连续1的长度
   • ans：记录最大连续1的长度
4. 遍历过程中：
   • 如果当前位是1，则 l 加1
   • 如果当前位是0，则比较 l 和 ans，更新 ans，并将 l 重置为0
5. 最后还需要再检查一次 l 和 ans（处理最后一段连续1的情况）
6. 输出 ans 即为结果

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	ans, l := 0, 0
	for i := 0; i < 64; i++ {
		if n>>i&1 == 1 {
			l++
		} else {
			if l > ans {
				ans = l
			}
			l = 0
		}
	}
	if l > ans {
		ans = l
	}
	fmt.Println(ans)
}

中等题 小红的排列构造

因为题意可知构造出的数组一定是个排列，所以 01 串中最后一位一定是 1，不是 1 的一定无解。

然后遍历 01 串每次遇到1时就对前面的数组位置进行一个填充，一个简单的思路就是末项为当前没有填充的数组最小，其余位置依次递增（即 2,3,4,5 的排列变为 3,4,5,2），这样一定保证前面位置不能构成排列，只有最后一项能够成为排列。

package main

import "fmt"

func main() {
	var (
		n int
		s string
	)
	fmt.Scan(&n, &s)
	s = " " + s
	if s[n] == '0' {
		fmt.Println(-1)
		return
	}
	a := make([]int, n+1)
	l := 1
	for i := 1; i <= n; i++ {
		if s[i] == '1' {
			for j := l; j < i; j++ {
				a[j] = l + j - l + 1
			}
			a[i] = l
			l = i + 1
		}
	}
	for i := 1; i <= n; i++ {
		fmt.Printf("%d ", a[i])
	}
}

困难题 [NOIP2001]装箱问题

这道题是一个经典的0-1 背包问题，目标是将物品放入容量为 V 的背包中，使得背包中物品的总重量尽可能接近 V，但不超过 V。最后输出背包剩余的空间。

1. 定义状态：

   • 使用 dp[j] 表示容量为 j 的背包所能容纳的最大重量。

2. 状态转移方程：

   • 对于每个物品重量 x，从背包容量 V 开始向下遍历：

     dp[j] = max(dp[j], dp[j-x] + x)
     

     这里的含义是：当前容量 j 的最大重量，要么不放入当前物品（保持 dp[j] 不变），要么放入当前物品（更新为 dp[j-x] + x）。

3. 初始化：

   • dp[0] = 0，表示容量为 0 的背包最大重量为 0。
   • 其他 dp[j] 初始为 0，因为还没有放入任何物品。

4. 遍历顺序：

   • 外层循环遍历所有物品。
   • 内层循环从背包容量 V 向下遍历，确保每个物品只能被使用一次（0-1 背包的特性）。

5. 输出结果：

   • 最后，dp[V] 表示容量为 V 的背包所能容纳的最大重量。
   • 剩余空间为 V - dp[V]。

package main

import "fmt"

func main() {
	var V, n int
	fmt.Scan(&V, &n)
	dp := make([]int, V+1)
	for i := 0; i < n; i++ {
		var x int
		fmt.Scan(&x)
		for j := V; j >= x; j-- {
			if dp[j-x]+x > dp[j] {
				dp[j] = dp[j-x] + x
			}
		}
	}
	fmt.Println(V - dp[V])
}