活動(dòng)地址： ?？痛赫兴㈩}訓(xùn)練營(yíng) - 編程打卡活動(dòng)

簡(jiǎn)單題 自守?cái)?shù)

1. 讀入一個(gè)整數(shù) n
2. 遍歷從 0 到 n 的每個(gè)數(shù)字 x
3. 對(duì)于每個(gè)數(shù)字 x：
   • 將 x 轉(zhuǎn)換為字符串 sx
   • 計(jì)算 x 的平方，并轉(zhuǎn)換為字符串 sy
   • 判斷 sy 的末尾是否等于 sx（通過(guò)切片 sy[len(sy)-len(sx):] 獲?。?/li>
   • 如果相等，答案加 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 平分成兩個(gè)等長(zhǎng)子串 s1 和 s2
2. 對(duì)于每個(gè)子串，找出出現(xiàn)次數(shù)最多的字符的頻次
3. 子串長(zhǎng)度減去最大頻次即為需要修改的最少字符數(shù)
4. 兩個(gè)子串需要修改的字符數(shù)之和即為答案

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. 使用前綴和思想，統(tǒng)計(jì)每個(gè)位置之后（包括當(dāng)前位置）每個(gè)字母出現(xiàn)的次數(shù)：

   • 建立二維數(shù)組 cnt[i][j] 表示從位置 i 開(kāi)始到末尾，字母 j 出現(xiàn)的次數(shù)
   • 從后向前遍歷，方便統(tǒng)計(jì)每個(gè)位置之后的字母出現(xiàn)次數(shù)

2. 遍歷字符串的每個(gè)位置 i，對(duì)于每個(gè)字母 j：

   • 如果等于當(dāng)前位置的字母（aaa 型語(yǔ)句）不計(jì)數(shù)
   • 如果不等于當(dāng)前位置的字母，計(jì)算在位置 i 之后出現(xiàn)的字母 j 能形成的對(duì)數(shù)：

3. 最終答案就是所有可能的字母對(duì)數(shù)之和

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