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

简单题小美的排列询问

排列的特点是每个数字只出现一次，因此可以通过记录每个数字在排列中的位置，快速判断它们是否相邻。
遍历排列，记录每个数字的位置。
检查 x 和 y 的位置差是否为 1 或 -1。如果是，则说明它们相邻。

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")
	}
}

中等题小红的字符串构造

题目要求 t 的字符集与 s 相同，且每个位置的字符都不同。因此，可以通过轮换字符顺序的方式来构造 t。
将 s 中出现的字符去重后按某种顺序排列为一个列表 p 。
对于 s 中的每个字符 c，用 p 中的下一个字符替换它。
如果 s 中只有一个字符（即 p 的长度为 1），则无法构造出满足条件的 t，直接输出 "-1"。

package main

import "fmt"

func main() {
	var s string
	fmt.Scan(&s)
	p := make([]rune, 0)
	mp := make(map[rune][]int)
	for i, c := range s {
		if _, ok := mp[c]; ok {
			mp[c] = append(mp[c], i)
		} else {
			mp[c] = []int{i}
			p = append(p, c)
		}
	}
	if len(p) == 1 {
		fmt.Println("-1")
		return
	}
	t := make([]rune, len(s))
	for i := 0; i < len(p); i++ {
		for _, c := range mp[p[i]] {
			t[c] = p[(i+1)%len(p)]
		}
	}
	fmt.Println(string(t))
}

困难题 [ZJOI2010]COUNT 数字计数

这是一道数位DP题目，主要是统计在区间[a,b]内每个数字0-9分别出现的次数。

使用数位DP来统计从1到x中某个数字d出现的次数：
- 设计状态dfs(pos, preNum, d, sum, flag)函数：
  - pos: 当前处理的位置（从高位到低位）
  - preNum: 前一位填的数字
  - d: 要统计的数字
  - sum: 当前已经出现的目标数字d的个数
  - flag: 是否受到原数字的限制
状态转移过程：
- 如果pos=0，说明已经处理完所有位，返回sum
- 如果不受限制且当前状态已计算过，直接返回记忆化的结果
- 确定当前位可以填的最大数字：
  - 如果受限，最大为原数字当前位的数字
  - 否则最大为9
- 枚举当前位可以填的数字i（0到maxNum）：
  - 特殊处理前导零的情况（preNum=10）
  - 如果填的数字i等于目标数字d，则sum+1
  - 递归处理下一位
主函数处理：
- 对于每个数字d（0-9），计算get(b,d) - get(a-1,d)
- get(x,d)函数用来计算1到x中数字d出现的次数
- 使用数组dim存储待处理数字的每一位

状态记忆化存储在dp[pos][sum]数组中，避免重复计算。使用dp[i][j]=-1初始化表示该状态未被计算过。

package main

import "fmt"

const maxPos = 15

var dp [maxPos][maxPos]int64
var dim [maxPos]int

// pos表示当前位数
// pre_num代表前一位置所填数字
// flag代表是否前面每一位都和上限数字相同
func dfs(pos, preNum, d int, sum int64, flag bool) int64 {
	if pos == 0 {
		return sum
	}
	if !flag && dp[pos][sum] != -1 {
		return dp[pos][sum]
	}
	maxNum := 9
	if flag {
		maxNum = dim[pos]
	}
	var ans int64 = 0
	for i := 0; i <= maxNum; i++ {
		if i == 0 && preNum == 10 {
			ans += dfs(pos-1, 10, d, sum, flag && i == maxNum)
		} else {
			newSum := sum
			if i == d {
				newSum++
			}
			ans += dfs(pos-1, i, d, newSum, flag && i == maxNum)
		}
	}
	if !flag && preNum != 10 {
		dp[pos][sum] = ans
	}
	return ans
}

func get(x int64, d int) int64 {
	for i := 0; i < maxPos; i++ {
		for j := 0; j < maxPos; j++ {
			dp[i][j] = -1
		}
	}
	len := 0
	for x > 0 {
		len++
		dim[len] = int(x % 10)
		x /= 10
	}
	return dfs(len, 10, d, 0, true)
}

func main() {
	var a, b int64
	fmt.Scan(&a, &b)
	for i := 0; i < 10; i++ {
		fmt.Print(get(b, i)-get(a-1, i), " ")
	}
}

#牛客春招刷题训练营#

牛客春招刷题训练营文章被收录于专栏

爱丽姐真是太好了