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

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

简单题 小红浏览论坛

  1. 读入贴子数量 n 和最小差值 x
  2. 对每个贴子读入点赞数 a 和反对数 b
  3. 检查点赞数和反对数的差的绝对值是否大于等于 x
  4. 统计满足条件的贴子数量并输出
package main

import "fmt"

func main() {
	var n, x int
	fmt.Scan(&n, &x)
	ans := 0
	for i := 0; i < n; i++ {
		var a, b int
		fmt.Scan(&a, &b)
		if a-b >= x || b-a >= x {
			ans++
		}
	}
	fmt.Println(ans)
}

中等题 游游的排列构造

步骤1:放置大数(先放 n-k+1 到 n 的数)

  • 从索引 0 开始,每隔一个位置放置一个数
  • 这样确保大数之间至少有一个数的间隔
  • 使用偶数位置:0, 2, 4...

步骤2:填充剩余空位

  • 用 1 到 n-k 的数字
  • 填充到之前跳过的位置(奇数索引)
package main

import "fmt"

func main() {
	var n, k int
	fmt.Scan(&n, &k)
	a := make([]int, n)
	v := n - k + 1
	for i := 0; i < n; i += 2 {
		a[i] = v
		if v == n {
			break
		}
		v++
	}
	v = 1
	for i := range a {
		if a[i] == 0 {
			a[i] = v
			v++
		}
		fmt.Print(a[i], " ")
	}
}

困难题 【模板】最小生成树

  1. 输入图的结构
    • 图由顶点和边组成,边包含两个顶点和一个权重。
    • 使用结构体表示边,并将所有边存储在一个数组中。
  2. 对边进行排序
    • 按照边的权重从小到大排序。
  3. 使用并查集管理连通性
    • 并查集用于判断两个顶点是否已经连通。如果一条边的两个顶点已经连通,则跳过该边以避免形成环。
  4. 构建最小生成树
    • 遍历排序后的边,依次加入生成树中,直到生成树包含所有顶点。
package main

import (
	"fmt"
	"sort"
)

var (
	n, m  int
	fa    []int
	depth []int
)

type edge struct {
	id, u, v, w int
}

func initUnionFind(n int) {
	fa = make([]int, n+1)
	depth = make([]int, n+1)
	for i := 1; i <= n; i++ {
		fa[i] = i
		depth[i] = 1
	}
}

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

func unite(a, b int) {
	a, b = find(a), find(b)
	if depth[a] == depth[b] {
		depth[a]++
		fa[b] = a
	} else {
		if depth[a] < depth[b] {
			fa[a] = b
		} else {
			fa[b] = a
		}
	}
}

func same(a, b int) bool {
	return find(a) == find(b)
}

func main() {
	fmt.Scan(&n, &m)
	var edges []edge
	for i := 0; i < m; i++ {
		var u, v, w int
		fmt.Scan(&u, &v, &w)
		edges = append(edges, edge{i + 1, u, v, w})
	}

	sort.Slice(edges, func(i, j int) bool {
		return edges[i].w < edges[j].w
	})

	initUnionFind(n)

	kruskal := func() (res int, ids []int) {
		for _, e := range edges {
			if !same(e.u, e.v) {
				unite(e.u, e.v)
				res += e.w
				ids = append(ids, e.id)
			}
			if len(ids) == n-1 {
				break
			}
		}
		return
	}

	k, ids := kruskal()
	fmt.Println(k)
	for _, id := range ids {
		fmt.Print(id, " ")
	}
}

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

爱丽姐真是太好了

全部评论
mark
点赞 回复 分享
发布于 05-30 11:39 辽宁
mark
点赞 回复 分享
发布于 05-30 11:39 湖南
mark
点赞 回复 分享
发布于 05-30 11:39 浙江
mark
点赞 回复 分享
发布于 05-30 11:39 浙江
mark
点赞 回复 分享
发布于 05-30 11:39 上海
mark
点赞 回复 分享
发布于 05-29 15:39 北京
mark模板
点赞 回复 分享
发布于 05-29 15:08 北京
排序很关键
点赞 回复 分享
发布于 05-29 14:36 北京
mark模板
点赞 回复 分享
发布于 05-29 14:21 北京

相关推荐

JWT&nbsp;的工作原理用户通过用户名和密码等凭据进行身份验证。服务器验证用户的凭据,生成&nbsp;JWT,并将其返回给用户。JWT&nbsp;通过&nbsp;Base64Url&nbsp;编码而成。用户存储&nbsp;JWT,通常存储在浏览器的&nbsp;localStorage&nbsp;或&nbsp;sessionStorage&nbsp;中。用户在每次请求时将&nbsp;JWT&nbsp;发送到服务器,通常通过&nbsp;HTTP&nbsp;请求的&nbsp;Authorization&nbsp;头部。服务器接收到&nbsp;JWT&nbsp;后验证其签名与内容。如果有效,服务器执行该请求;如果无效,返回相应的错误信息。JWT&nbsp;的优势无状态:JWT&nbsp;以自包含的方式存储用户信息,服务器不需要存储用户会话信息,适合分布式系统。跨域支持:由于&nbsp;JWT&nbsp;是基于标准的字符串格式,可以轻松支持跨域请求。灵活性:可以在&nbsp;Token&nbsp;中存储自定义数据,不仅限于身份验证相关的信息。安全性:通过签名算法保证数据的完整性,避免被篡改。JWT&nbsp;的缺点不可撤销性:JWT&nbsp;一旦生成,无法简单地撤销,除非设计了&nbsp;Token&nbsp;刷新机制。过期管理:需要合理设置过期时间,过长会带来安全隐患,过短则可能影响用户体验。隐私问题:JWT&nbsp;中的信息是Base64Url编码的,并未加密,因此敏感信息不应直接放在&nbsp;Token&nbsp;中。常见用例用户身份验证:用户登录成功后,会话管理通过发放&nbsp;JWT&nbsp;实现。API&nbsp;访问控制:保护&nbsp;API&nbsp;端点,确保只有持有有效&nbsp;Token&nbsp;的用户才能访问。单点登录(SSO):多个系统之间共享&nbsp;JWT,实现单点登录。
社畜职场交流圈
点赞 评论 收藏
分享
05-20 21:53
门头沟学院 Java
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务