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

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

简单题 杨辉三角的变形

• 前两行因为元素个数太少，不存在偶数
• 因为每行第二个位置是 n-1，所以奇数行第一个偶数出现的位置为 2
• 多推几项可以发现第一个偶数出现的位置循环节为 2324

package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)
	if n <= 2 {
		fmt.Println(-1)
	} else if n%2 == 1 {
		fmt.Println(2)
	} else if n%4 == 0 {
		fmt.Println(3)
	} else {
		fmt.Println(4)
	}
}

中等题 计算日期到天数转换

1. 程序接收输入的年、月、日（y, m, d）
2. 判断是否为闰年：
   • 如果年份能被4整除但不能被100整除，或者能被400整除，则为闰年
   • 闰年2月有29天，平年2月有28天
3. 计算当前日期是一年中的第几天：
   • 将该月份之前所有月份的天数累加
   • 再加上当月的天数

package main

import "fmt"

var days = []int{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30}

func isLeapYear(year int) bool {
	if year%4 == 0 && year%100 != 0 || year%400 == 0 {
		return true
	}
	return false
}

func main() {
	var y, m, d int
	fmt.Scan(&y, &m, &d)
	if isLeapYear(y) {
		days[2] = 29
	}
	s := 0
	for i := 1; i < m; i++ {
		s += days[i]
	}
	s += d
	fmt.Println(s)
}

困难题 而后单调

要想让操作后是严格递增或严格递减数组，所以挑选出的长度为 m 的连续子数组一定要是原数组排序后元素之间是相邻且有序的。

所以问题转换成了判断一个数组中是否存在长度为m的连续子数组，该子数组中的元素在排序后是连续递增或连续递减的。

1. 解题步骤：

   • 首先读入数组长度n和目标长度m，以及数组a
   • 使用map检查数组中是否有重复元素，如果有重复则直接输出"NO"
   • 创建数组b作为a的副本并排序，用于取每个元素的排序后位置
   • 使用map记录每个元素在排序后数组中的位置索引

2. 动态规划部分：

   • 创建两个dp数组：
     • dp1[]：记录以当前位置结尾的连续递增子序列长度
     • dp2[]：记录以当前位置结尾的连续递减子序列长度

3. 状态转移：

   • 对于每个位置i：
     • 如果当前元素在排序后位置比前一个元素大1，则dp1[i] = dp1[i-1] + 1
     • 如果当前元素在排序后位置比前一个元素小1，则dp2[i] = dp2[i-1] + 1
     • 否则重置为1

4. 最后判断：

   • 遍历所有位置，如果存在任意位置的dp1[i]或dp2[i]等于m，则输出"YES"
   • 否则输出"NO"

时间复杂度：，主要来自排序

空间复杂度：，用于存储dp数组和map

package main

import (
	"fmt"
	"sort"
)

func solve() {
	var n, m int
	fmt.Scan(&n, &m)
	a := make([]int, n)
	b := make([]int, n)
	mp := make(map[int]int)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
		b[i] = a[i]
		mp[a[i]] = -1
	}
	if len(mp) != n {
		fmt.Println("NO")
		return
	}
	sort.Ints(b)
	for i := 0; i < n; i++ {
		mp[b[i]] = i
	}
	dp1, dp2 := make([]int, n), make([]int, n)
	dp1[0], dp2[0] = 1, 1
	for i := 1; i < n; i++ {
		if mp[a[i]]-mp[a[i-1]] == 1 {
			dp1[i] = dp1[i-1] + 1
		} else {
			dp1[i] = 1
		}
		if mp[a[i]]-mp[a[i-1]] == -1 {
			dp2[i] = dp2[i-1] + 1
		} else {
			dp2[i] = 1
		}
	}
	for i := 0; i < n; i++ {
		if dp1[i] == m || dp2[i] == m {
			fmt.Println("YES")
			return
		}
	}
	fmt.Println("NO")
}

func main() {
	var t int
	fmt.Scan(&t)
	for i := 0; i < t; i++ {
		solve()
	}
}