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

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

简单题 墙壁划线

这个交点的个数与瓷砖的实际尺寸 x,y 无关，只取决于行数 b 和列数 a。

1. 单条对角线（不含端点）的内部交点数

   把整块墙看成坐标系里的整数格：左上角是 (0,0)，右下角是 (a,b)。主对角线从 (0,0) 到 (a,b)，它与内部的竖线和横线交点一共有 次，但当交点恰好落在格点（也就是同时在一条竖线和一条横线上）时会被重复算两次，这样的内部格点数量是 。

   因此不含两端端点的真正交点数就是

2. 算上四个端点

   两条对角线共有四个不同的端点：

   • 主对角线：(0,0)、(a,b)
   • 副对角线：(a,0)、(0,b)
   • 既然前面 num 是“不含端点”的交点数，总体上把两条对角线都算上，还要加回这四个端点：

3. 去掉公共的那个“多算”交点

   当且仅当 a 或者 b 为偶数时，两个对角线在中点这个位置会落在一条格线上（要么竖线要么横线），因此这个交点既被主对角线算了一次，又被副对角线算了一次，多算了一个，需要减去。

最终就得到了完整的不重不漏的交点总数。

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	pos := make([]int, n+1)
	for i := 1; i <= n; i++ {
		var a int
		fmt.Scan(&a)
		pos[a] = i
	}
	var x, y int
	fmt.Scan(&x, &y)
	if pos[x]-pos[y] == 1 || pos[x]-pos[y] == -1 {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}

中等题 小红的排列构造

多枚举几个 n 我们可以发现规律

1: 无解

2: 无解

3: 3 2 1

4: 3 2 1 4

5: 3 2 1 4 5

6: 3 2 1 4 5 6

7: 3 2 1 4 5 6 7

n: 3 2 1 4 5 6 7 ... n

按照此规律构造即可

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	if n == 1 || n == 2 {
		fmt.Println(-1)
	} else {
		fmt.Print("3 2 1")
		for i := 4; i <= n; i++ {
			fmt.Print(" ", i)
		}
	}
}

困难题 串

1. 动态规划的状态表示

• dp[i][j] 表示长度为 ( i ) 的字符串中处于某种特定状态 ( j ) 的字符串数量。
• 状态 ( j ) 的含义：
  • ( j = 0 )：尚未包含字母 "u"。
  • ( j = 1 )：已经包含字母 "u"，但尚未包含字母 "s"。
  • ( j = 2 )：已经包含子序列 "us"。

初始状态为：

• 长度为 0 的空字符串处于状态 ( j = 0 )，即 dp[0][0] = 1。
• 其他状态的值均为 0。

2. 状态转移方程

对于每个长度 ( i ) 和每个状态 ( j )，我们需要考虑新增字符的影响。新增字符可以是任意小写字母（共 26 种可能），但只有 "u" 和 "s" 会影响状态转移。

• 新增字符不是 "u" 或 "s"：
  • 如果当前字符不是 "u" 或 "s"，则状态保持不变。
    • 处于状态 ( j = 0 ) 的字符串，仍处于状态 ( j = 0 )。
    • 处于状态 ( j = 1 ) 的字符串，仍处于状态 ( j = 1 )。
    • 处于状态 ( j = 2 ) 的字符串，仍处于状态 ( j = 2 )。
  • 转移公式为：（因为有 24 个字母既不是 "u" 也不是 "s"）。
• 新增字符是 "u"：
  • 可以从状态 ( j = 0 ) 转移到状态 ( j = 1 )，转移公式为：
  • 可以从状态 ( j = 1 ) 转移到状态 ( j = 1 )，转移公式为：
  • 可以从状态 ( j = 2 ) 转移到状态 ( j = 2 )，转移公式为：
• 新增字符是 "s"：
  • 可以从状态 ( j = 1 ) 转移到状态 ( j = 2 )，转移公式为：
  • 可以从状态 ( j = 2 ) 转移到状态 ( j = 2 )，转移公式为：
  • 可以从状态 ( j = 0 ) 转移到状态 ( j = 0 )，转移公式为：

package main

import "fmt"

const mod int = 1e9 + 7

func main() {
	var n int
	fmt.Scan(&n)
	// dp[i][j] 表示长度为 i 的字符串处于状态 j 的数量
	// 状态 0: 尚未包含 "u"
	// 状态 1: 已经包含 "u"，但尚未包含 "s"
	// 状态 2: 已经包含 "us"
	dp := make([][3]int, n+1)
	dp[0][0] = 1

	for i := 1; i <= n; i++ {
		for j := 0; j < 3; j++ {
			dp[i][j] = (dp[i][j] + dp[i-1][j]*24%mod) % mod
		}
		// u
		dp[i][1] = (dp[i][1] + dp[i-1][0]) % mod
		dp[i][1] = (dp[i][1] + dp[i-1][1]) % mod
		dp[i][2] = (dp[i][2] + dp[i-1][2]) % mod
		// s
		dp[i][2] = (dp[i][2] + dp[i-1][1]) % mod
		dp[i][2] = (dp[i][2] + dp[i-1][2]) % mod
		dp[i][0] = (dp[i][0] + dp[i-1][0]) % mod
	}

	ans := 0
	for i := 2; i <= n; i++ {
		ans = (ans + dp[i][2]) % mod
	}
	fmt.Println(ans)
}