一 Coding1
题目描述
小红拿到了一个字符串，她想知道这个字符串能否通过重新排列 组成"Baidu"字符串?
注:必须大小写完全相同。
共有t组询问。
输入描述
第一行输入一个正整数t，代表询问次数。
接下来的t行，每行输入一个仅包含英文字母的字符串。
所有字符串的长度之和保证不超过200000。
输出描述
对于每次询问，输出一行答案。如果可以通过重新排列组成"Baidu",则输出"Yes"， 否则输出"No"。
解题思路
在主函数中，我们首先读取询问次数t。然后对于每个询问，我们读取一个字符串并调用Form函数来检查是否可以通过重新排列组成"Baidu"字符串。如果返回true，则输出"Yes"，否则输出"No"。
在Form函数中，我们使用一个Map：freq来统计输入字符串中每个字符出现的次数。然后检查是否有足够的字符可以组成"Baidu"。具体来说，我们将需要的字符存储在一个Map中，并遍历该Map，检查每个字符是否在Map中出现过。如果有任何一个字符没有出现，则说明无法组成"Baidu"，返回false。否则返回true。
详细代码
package main import ( "bufio" "fmt" "os" "strconv" ) func main() { scanner := bufio.NewScanner(os.Stdin) scanner.Scan() t,_:=strconv.Atoi(scanner.Text()) for i:=0;i<t;i++{ scanner.Scan() s := scanner.Text() if Form(s){ fmt.Println("Yes") }else { fmt.Println("No") } } } func Form(s string)bool{ freq :=make(map[rune]int) for _,c := range s{ freq[c]++ } if freq['B']==1 && freq['a']==1 && freq['i']==1 && freq['d']==1 && freq['u']==1{ return true } return false }
二 Coding2
题目描述
给定一个整数x， 请你构造一个仅由了‘r’、‘e’、'd’三种字符组成的 字符串，其中回文子串的数量恰好为x。
字符串的长度不得超过10的5次方。
输入描述
一个正整数x。
1<x<10的9次方
输出描述
输出一个仅由’r’、‘e’、'd’三种字符组成的字符串，长度不得超过10的五次方。有多解时输出任意即可。
解题思路
首先，我们读入整数 x。
如果 x 等于 1，那么可以直接输出 “r”，因为 “r” 是一个回文字符串。
否则，我们需要构造一个由 “r”、“e”、“d” 三种字符组成的字符串，使得该字符串中恰好有 x 个回文子串。
我们可以观察到，由 “r”、“e”、“d” 三种字符组成的回文子串只有 “r”、“e”、“d”、“ee”、“rr”、“dd”、“redd”、“drrd” 和 “erede” 这九种。
假设我们需要构造 k 个回文子串，那么我们可以构造一个由 k/2 个 “redd” 和 (k+1)/2 个 “red” 组成的字符串，其中 “/” 表示整除符号。
例如，如果 x 等于 3，那么我们需要构造一个由三个回文子串组成的字符串，可以先计算出需要两个回文子串，然后构造一个由一个 “redd” 和一个 “red” 组成的字符串，即 “reddred”，然后去掉多余的字符，得到 “red”。
最后，我们可以通过 Go 标准库中的 strings.Repeat 函数来构造由 “redd” 组成的子串，然后通过字符串切片的方式去掉多余的字符，得到长度为 x 的字符串。
详细代码
package main import ( "fmt" "strings" ) func main() { var x int fmt.Scan(&x) if x == 1 { fmt.Println("r") return } palindromeCount := (x + 1) / 2 palindrome := strings.Repeat("red", palindromeCount)[:x] fmt.Println(palindrome) }
三 Coding3
题目描述
小红拿到了棵树，每个节点被染成 了红色或者蓝色。
小红定义每条边的权值为:删除这条边时，形成的两个子树的同色连通块数量之差的绝对值。
小红想知道，所有边的权值之和是多少?
输入描述
第一行输入一个正整数n,代表节点的数量。
第二行输入一个长度为n且仅由’R"和B，两种字符组成的字符串。
第i个字符为’R"代表i号节点被染成红色，为’B’则被染成蓝色。
接下来的n-1行，每行输入两个正整数u和U，代表节点么和节 点U有一条边相连
1≤n≤200000
输出描述
一个正整数，代表所有节点的权值之和。
解题思路
代码思路：
定义一个 node 结构体，每个节点包括颜色和邻接表。
读入节点信息和颜色，构造邻接表。
采用 DFS 的方式遍历整个树，对于每个节点，分别统计其子树中红色节点和蓝色节点的数量，最终求出所有节点的权值之和。
具体地，对于每个节点 u，先将其本身的颜色统计一下，再遍历其邻接表，如果邻接点 v 不是 u 的父节点，则递归遍历以 v 为根的子树，并将其子树中红色节点和蓝色节点的数量累加到 u 节点的计数器 red[u] 和 blue[u] 上，最后将 red[u] 和 blue[u] 的差的绝对值累加到答案中即可。
最终输出所有节点的权值之和。
详细代码
package main import ( "bufio" "fmt" "os" ) type node struct { color byte edges []int } func abs(x int) int { if x < 0 { return -x } return x } func dfs(u int, parent int, nodes []node, red, blue []int, ans *int) { if nodes[u].color == 'R' { red[u]++ } else { blue[u]++ } for _, v := range nodes[u].edges { if v != parent { dfs(v, u, nodes, red, blue, ans) red[u] += red[v] blue[u] += blue[v] } } *ans += abs(red[u] - blue[u]) } func main() { var n int fmt.Scanln(&n) nodes := make([]node, n) colors := make([]byte, n) for i := 0; i < n; i++ { fmt.Scanf("%c", &colors[i]) nodes[i].color = colors[i] } scanner := bufio.NewScanner(os.Stdin) scanner.Split(bufio.ScanWords) for i := 0; i < n-1; i++ { var u, v int scanner.Scan() fmt.Sscan(scanner.Text(), &u) scanner.Scan() fmt.Sscan(scanner.Text(), &v) u-- v-- nodes[u].edges = append(nodes[u].edges, v) nodes[v].edges = append(nodes[v].edges, u) } red := make([]int, n) blue := make([]int, n) ans := 0 dfs(0, -1, nodes, red, blue, &ans) fmt.Println(ans) }
测试：
输入：
4
BBRR
1 2
3 2
4 1
输出
2
