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

简单题小红的对称串

判断逻辑：

对于每个字符串，遍历到其长度的一半
对于每个位置 j，判断 s[j] 与 s[len(s)-1-j] 是否构成合法的对称
- 自对称字母必须和自己相同
- 对称对字母必须与其对应字母配对
如果出现其他字母，或对称规则不满足，输出 "No"
如果所有位置都满足对称规则，输出 "Yes"

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)

	solve := func() {
		var s string
		fmt.Scan(&s)
		for j := 0; j <= len(s)/2; j++ {
			switch s[j] {
			case 'i', 'l', 'm', 'n', 'o', 'u', 'v', 'w', 'x':
				if s[len(s)-1-j] != s[j] {
					fmt.Println("No")
					return
				}
			case 'b':
				if s[len(s)-1-j] != 'd' {
					fmt.Println("No")
					return
				}
			case 'd':
				if s[len(s)-1-j] != 'b' {
					fmt.Println("No")
					return
				}
			case 'p':
				if s[len(s)-1-j] != 'q' {
					fmt.Println("No")
					return
				}
			case 'q':
				if s[len(s)-1-j] != 'p' {
					fmt.Println("No")
					return
				}
			default:
				fmt.Println("No")
				return
			}
		}
		fmt.Println("Yes")
	}

	for i := 0; i < n; i++ {
		solve()
	}
}

中等题 Y型树

将问题转化为有多少种方法把正整数 $n = N - 1$ 拆成 3 个正整数的无序组合？

对 n ，将其拆成 3 个正整数 $a \le b \le c$ 的无序组合数为： $\left\lfloor \frac{n^2 + 3}{12} \right\rfloor$

这是一个经典的组合恒等式（无序三正整数拆分公式）详见：https://oeis.org/A001399

package main

import (
	"fmt"
	"math/big"
)

const MOD = 1000000007

func main() {
	var n int64
	fmt.Scan(&n)

	bigN := big.NewInt(n - 1)              // n - 1
	bigNum := new(big.Int).Mul(bigN, bigN) // n^2
	bigNum.Add(bigNum, big.NewInt(3))      // n^2 + 3
	bigNum.Div(bigNum, big.NewInt(12))     // (n^2 + 3) / 12

	mod := big.NewInt(MOD)
	result := new(big.Int).Mod(bigNum, mod)

	fmt.Println(result)
}

困难题【模板】二分

二分查找函数实现:
- lowerBound: 查找第一个大于等于目标值的位置
- upperBound: 查找第一个大于目标值的位置
程序主体逻辑:

输入：
- n：数组长度
- q：查询次数
- a：长度为 n 的数组
- 每次查询包含 4 个参数：op, l, r, x
  - op：操作类型(1-4)
  - l, r：查询区间[l,r)
  - x：目标值

查询类型:

op = 1: 返回区间内第一个大于等于 x 的数
op = 2: 返回区间内第一个大于 x 的数
op = 3: 返回区间内最后一个小于 x 的数
op = 4: 返回区间内最后一个小于等于 x 的数

查询处理:
- 对子数组 a[l:r] 进行二分查找
- 根据查找结果和区间边界判断答案是否有效
- 输出结果：如果找到合法位置则输出对应值，否则输出 -1

package main

import "fmt"

func lowerBound(a []int, x int) int {
	l, r, ans := 0, len(a)-1, len(a)
	for l <= r {
		mid := (l + r) / 2
		if a[mid] >= x {
			ans = mid
			r = mid - 1
		} else {
			l = mid + 1
		}
	}
	return ans
}

func upperBound(a []int, x int) int {
	l, r, ans := 0, len(a)-1, len(a)
	for l <= r {
		mid := (l + r) / 2
		if a[mid] > x {
			ans = mid
			r = mid - 1
		} else {
			l = mid + 1
		}
	}
	return ans
}

func main() {
	var n, q int
	fmt.Scan(&n, &q)
	a := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
	}
	for i := 0; i < q; i++ {
		var op, l, r, x int
		fmt.Scan(&op, &l, &r, &x)
		var id int
		switch op {
		case 1:
			id = lowerBound(a[l:r], x)
		case 2:
			id = upperBound(a[l:r], x)
		case 3:
			id = lowerBound(a[l:r], x) - 1
		case 4:
			id = upperBound(a[l:r], x) - 1
		}
		if id+l >= l && id+l < r {
			fmt.Println(a[id+l])
		} else {
			fmt.Println(-1)
		}
	}
}

#牛客春招刷题训练营#

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

爱丽姐真是太好了