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

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

简单题 挑7

1. 遍历1到n的每个数字i
2. 判断条件：
   • i%7 == 0：判断是否为7的倍数
   • strings.Contains(strconv.Itoa(i), "7")：判断数字中是否包含7
   • 只要满足其中一个条件就计数加1

package main

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

func main() {
	var n int
	fmt.Scan(&n)
	ans := 0
	for i := 1; i <= n; i++ {
		if i%7 == 0 || strings.Contains(strconv.Itoa(i), "7") {
			ans++
		}
	}
	fmt.Println(ans)
}

中等题 仰望水面的歪

将击中的坐标根据水面（z=h）进行平面对称，很容易得到经过对称后的坐标是(x,y,2*h-z)。

得到光线的向量后求出三者的最大公约数后进行化简。

package main

import "fmt"

func gcd(a, b int64) int64 {
	if a == 0 {
		return b
	}
	return gcd(b%a, a)
}

func main() {
	var (
		n int
		h int64
	)
	fmt.Scan(&n, &h)
	for i := 1; i <= n; i++ {
		var x, y, z int64
		fmt.Scan(&x, &y, &z)
		zz := 2*h - z
		g := gcd(gcd(x, y), zz)
		fmt.Printf("%d %d %d\n", x/g, y/g, zz/g)
	}
}

困难题 1or0

题目实际上是求区间内存在1子区间的个数 ==> 子区间的总数 - 区间中只包含0的子区间的个数

pre 数组记录每个位置之前最近的0的位置

suf 数组记录每个位置之后最近的0的位置

sum 利用前缀和统计开始到当前位置的只包含0的子区间的个数

对于每次询问，ans1 表示子区间的总数，ans2 区间中只包含0的子区间的个数

因为sum[r] - sum[l-1]可能会包含区间外（ l 左边）的全0区间，得减去这部分数量

package main

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

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var (
		n, q int
		s    string
	)
	fmt.Fscan(in, &n, &s)
	s = " " + s
	pre := make([]int, n+1)
	sum := make([]int, n+1)
	for i := 1; i <= n; i++ {
		if s[i] == '1' {
			sum[i] = sum[i-1]
		} else {
			if pre[i-1] == 0 {
				pre[i] = i
			} else {
				pre[i] = pre[i-1]
			}
			sum[i] = sum[i-1] + (i - pre[i] + 1)
		}
	}
	suf := make([]int, n+2)
	for i := n; i >= 1; i-- {
		if s[i] == '0' {
			if suf[i+1] == 0 {
				suf[i] = i
			} else {
				suf[i] = suf[i+1]
			}
		}
	}

	fmt.Fscan(in, &q)
	for i := 0; i < q; i++ {
		var l, r int
		fmt.Fscan(in, &l, &r)
		ans1 := (r - l + 2) * (r - l + 1) / 2
		ans2 := sum[r] - sum[l-1]
		if s[l] == '0' {
			ll, rr := pre[l], min(r, suf[l])
			ans2 -= (l - ll) * (rr - l + 1)
		}
		fmt.Fprintln(out, ans1-ans2)
	}
}