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

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

简单题 小红的好数组

1. 遍历数组，检查是否存在长度为3的非降序子数组。
2. 如果发现这样的子数组，修改这个子数组中间的值（可以设为正无穷）并且计数器增加，并跳过接下来的两个元素，因为当前修改已经破坏了这个子数组(a[i-2],a[i-1],a[i])，下一个可能存在非降序子数组的子数组是(a[i],a[i+1],a[i+2])。
3. 最终输出计数器的值，表示至少需要的操作次数。

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	a := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
	}
	i, count := 2, 0
	for i < n {
		if a[i] >= a[i-1] && a[i-1] >= a[i-2] {
			count++
			i += 2
		} else {
			i++
		}
	}
	fmt.Println(count)
}

中等题 压缩二维码

1. 读取输入数据：
   • 首先读取整数 n，表示二维码的边长为 。
   • 接下来读取 行字符串，每行包含 个字符，字符是 . 或 #。
2. 字符替换：
   • 将 . 替换为 0，将 # 替换为 1，以方便后续处理。
3. 构建比特流：
   • 按照从上到下、从左到右的顺序，将每一行的字符拼接成一个完整的比特流。
4. 分组编码：
   • 将比特流按照每4个比特一组进行分组。
   • 对每一组比特计算其对应的十进制值（即二进制转十进制）。
   • 输出每个十进制值，中间用空格分隔。

package main

import (
	"fmt"
	"strings"
)

func main() {
	var n int
	fmt.Scan(&n)
	var t string
	for i := 0; i < (1 << n); i++ {
		var s string
		fmt.Scan(&s)
		s = strings.ReplaceAll(s, ".", "0")
		s = strings.ReplaceAll(s, "#", "1")
		t += s
	}
	for i := 0; i < len(t); i += 4 {
		s := t[i : i+4]
		num := 0
		for j := 0; j < 4; j++ {
			num = num*2 + int(s[j]-'0')
		}
		fmt.Print(num, " ")
	}
}

困难题 分割等和子集

1. 输入处理：

   • 读取数组大小 n
   • 创建长度为 n 的整数切片 a
   • 计算数组所有元素的和 sum

2. 可行性判断：

   • 如果总和为奇数，直接返回 false（无法平分）
   • 目标是找到和为 sum/2 的子集

3. 动态规划解法：

   • dp[j] 表示是否可以从数组中选择若干个数，使其和为 j
   • 初始化：dp[0] = true（空集的和为0）
   • 状态转移：
     • 对每个数字 a[i]
     • 对于每个可能的和 j
     • dp[j] 可以从不选 a[i] 的状态 dp[j] 或选择 a[i] 的状态 dp[j-a[i]] 转移而来

4. 结果输出：

   • 检查 dp[sum/2]，即是否存在和为 sum/2 的子集
   • 输出相应的 true 或 false

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	a := make([]int, n)
	sum := 0
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
		sum += a[i]
	}
	if sum%2 != 0 {
		fmt.Println("false")
		return
	}
	dp := make([]bool, sum/2+1)
	dp[0] = true
	for i := 0; i < n; i++ {
		for j := sum / 2; j >= a[i]; j-- {
			dp[j] = dp[j] || dp[j-a[i]]
		}
	}
	if dp[sum/2] {
		fmt.Println("true")
	} else {
		fmt.Println("false")
	}
}