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

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

简单题 自守数

1. 读入一个整数 n
2. 遍历从 0 到 n 的每个数字 x
3. 对于每个数字 x：
   • 将 x 转换为字符串 sx
   • 计算 x 的平方，并转换为字符串 sy
   • 判断 sy 的末尾是否等于 sx（通过切片 sy[len(sy)-len(sx):] 获取）
   • 如果相等，答案加 1
4. 输出答案

package main

import (
	"fmt"
	"strconv"
)

func main() {
	var n int
	fmt.Scan(&n)
	ans := 0
	for x := 0; x <= n; x++ {
		sx := strconv.Itoa(x)
		sy := strconv.Itoa(x * x)
		if sy[len(sy)-len(sx):] == sx {
			ans++
		}
	}
	fmt.Println(ans)
}

中等题 小红的双生串

1. 将字符串 s 平分成两个等长子串 s1 和 s2
2. 对于每个子串，找出出现次数最多的字符的频次
3. 子串长度减去最大频次即为需要修改的最少字符数
4. 两个子串需要修改的字符数之和即为答案

package main

import "fmt"

func main() {
	var s string
	fmt.Scan(&s)
	s1, s2 := s[:len(s)/2], s[len(s)/2:]
	f := func(str string) (ans int) {
		m := make(map[rune]int)
		for _, v := range str {
			m[v]++
			if m[v] > ans {
				ans = m[v]
			}
		}
		return
	}
	fmt.Println(len(s) - f(s1) - f(s2))
}

困难题 abb

1. 使用前缀和思想，统计每个位置之后（包括当前位置）每个字母出现的次数：

   • 建立二维数组 cnt[i][j] 表示从位置 i 开始到末尾，字母 j 出现的次数
   • 从后向前遍历，方便统计每个位置之后的字母出现次数

2. 遍历字符串的每个位置 i，对于每个字母 j：

   • 如果等于当前位置的字母（aaa 型语句）不计数
   • 如果不等于当前位置的字母，计算在位置 i 之后出现的字母 j 能形成的对数：

3. 最终答案就是所有可能的字母对数之和

package main

import "fmt"

func main() {
	var (
		n int
		s string
	)
	fmt.Scan(&n, &s)
	cnt := make([][26]int64, n+1)
	for i := n - 1; i >= 0; i-- {
		for j := 0; j < 26; j++ {
			cnt[i][j] = cnt[i+1][j]
		}
		cnt[i][s[i]-'a']++
	}
	ans := int64(0)
	for i := 0; i < n; i++ {
		for j := 0; j < 26; j++ {
			if j == int(s[i]-'a') {
				continue
			}
			ans += cnt[i+1][j] * (cnt[i+1][j] - 1) / 2
		}
	}
	fmt.Println(ans)
}