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

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

简单题 不要三句号的歪

• 通过 strings.Split(s, ",") 将输入字符串按逗号分割成切片
• 获取第二个数（索引为 1）和第四个数（索引为 3）
• 使用 strconv.Atoi() 将字符串转换为整数
• 省略部分就是第四个数减去第二个数再减 1

package main

import (
	"fmt"
	"strconv"
	"strings"
)

func main() {
	var s string
	fmt.Scan(&s)
	ss := strings.Split(s, ",")
	b, _ := strconv.Atoi(ss[1])
	c, _ := strconv.Atoi(ss[3])
	fmt.Println(c - b - 1)
}

中等题 尼科彻斯定理

具体来说，对于任意正整数 n，有

这里数列中的每一项都是连续的奇数，总共有 n 项，这个表示方式是“最短”的。

证明思路

• 首项与末项

序列的首项为 ，末项为 。

• 求和验证

由于该序列为等差数列，公差为 2，项数为 n，根据等差数列求和公式：

化简后得到：

• 最短性说明

若用少于 n 个连续奇数表示 ，那么总和必定不足或超过 ，因此 n 个连续奇数正是达到 所需的最少项数。

结论：最短的序列就是由 n 个连续奇数组成的，从 到 的数列。

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	for i := n*n - n + 1; i <= n*n+n-1; i += 2 {
		if i == n*n-n+1 {
			fmt.Print(i)
		} else {
			fmt.Print("+", i)
		}
	}
}

困难题 隐匿社交网络

• 使用并查集来维护同一个社交网络的集合

• 对每个数的二进制位进行分析（0-63位）

• 用数组a[64]记录每一位上第一次出现1的数的下标

  • 如果某一位是1，就将这个数和之前在这一位上为1的数合并到同一个集合中

• 最后遍历所有数所在的集合，找出最大的集合大小

package main

import (
	"bufio"
	"fmt"
	"os"
)

var (
	in      *bufio.Reader
	out     *bufio.Writer
	fa, siz []int
)

func find(x int) int {
	if x != fa[x] {
		fa[x] = find(fa[x])
	}
	return fa[x]
}

func unite(x, y int) {
	x, y = find(x), find(y)
	if x == y {
		return
	}
	siz[x] += siz[y]
	fa[y] = x
}

func size(x int) int {
	return siz[find(x)]
}

func solve() {
	var n int
	fmt.Fscan(in, &n)
	fa, siz = make([]int, n+1), make([]int, n+1)
	for i := 1; i <= n; i++ {
		fa[i], siz[i] = i, 1
	}
	a := [64]int{}
	for i := 1; i <= n; i++ {
		var w int64
		fmt.Fscan(in, &w)
		for j := 0; j < 64; j++ {
			if (w>>j)&1 == 1 {
				if a[j] == 0 {
					a[j] = i
				} else {
					unite(a[j], i)
				}
			}
		}
	}

	ans := 0
	for i := 1; i <= n; i++ {
		if ans < size(i) {
			ans = size(i)
		}
	}
	fmt.Fprintln(out, ans)
}

func main() {
	in = bufio.NewReader(os.Stdin)
	out = bufio.NewWriter(os.Stdout)
	defer out.Flush()
	var t int
	fmt.Scan(&t)
	for i := 0; i < t; i++ {
		solve()
	}
}