牛客周赛Round 99（Go语言）

发布于：2025-07-07 ⋅ 阅读:(21) ⋅ 点赞:(0)
A题 (A.go)

思路总结: 这道题要求判断一个整数中是否包含连续的两个'9'。

核心思路是将输入的整数转换为字符串，然后遍历这个字符串，检查是否存在相邻的两个字符都是'9'。如果找到了，就立即停止遍历并输出"YES"；如果遍历完整个字符串都没有找到，则输出"NO"。

// ==========================================================
//                    POWERED BY GMJ
//                   2025-07-06 18:26
// ==========================================================
// Github:     https://github.com/Joker-0111-G
// CSDN:       https://blog.csdn.net/dl999666?type=blog
// Gmail:      joker0111gmj@gmail.com
// Author:     USER <joker0111gmj@gmail.com>
// FilePath:   ~/homegmj/GoCode/NK/20250706\A.go
// License:    MIT
// Copyright:  (c) 2025 JOKER. All rights reserved.
// ==========================================================
//    __  __    _  _____ _   _  ____ __  __     _
//    \ \/ /   / \|_   _| | | |/ ___|  \/  |   | |
//     \  /   / _ \ | | | | | | |  _| |\/| |_  | |
//     /  \  / ___ \| | | |_| | |_| | |  | | |_| |
//    /_/\_\/_/   \_\_|  \___/ \____|_|  |_|\___/
// ==========================================================
// Project Description (use | for new lines)

package main

import (
	"fmt"
	"strconv"
)

func mainA() {
	var n int
	fmt.Scan(&n) 

	s := strconv.Itoa(n)

	found99 := false 
	for i := 0; i < len(s)-1; i++ {
		if s[i] == '9' && s[i+1] == '9' {
			found99 = true 
			break       
		}
	}

	if found99 {
		fmt.Println("YES") 
	} else {
		fmt.Println("NO")  
	}
}
B题 (B.go)

思路总结: 题目要求找到输入字符串中ASCII码最大的字符，并输出其ASCII码值。

解法非常直接：初始化一个变量ma为0，用来记录当前遇到的最大ASCII码。然后遍历输入字符串中的每一个字符，将其转换为对应的ASCII整数值。在遍历过程中，如果当前字符的ASCII值大于ma，就更新ma。遍历结束后，ma中存储的就是整个字符串中最大的ASCII码值，直接输出即可。

// ==========================================================
//                    POWERED BY GMJ                         
//                   2025-07-06 19:02
// ==========================================================
// Github:     https://github.com/Joker-0111-G
// CSDN:       https://blog.csdn.net/dl999666?type=blog
// Gmail:      joker0111gmj@gmail.com
// Author:     USER <joker0111gmj@gmail.com>
// FilePath:   ~/homegmj/GoCode/NK/20250706\B.go
// License:    MIT
// Copyright:  (c) 2025 JOKER. All rights reserved.
// ==========================================================
//    __  __    _  _____ _   _  ____ __  __     _
//    \ \/ /   / \|_   _| | | |/ ___|  \/  |   | |
//     \  /   / _ \ | | | | | | |  _| |\/| |_  | |
//     /  \  / ___ \| | | |_| | |_| | |  | | |_| |
//    /_/\_\/_/   \_\_|  \___/ \____|_|  |_|\___/
// ==========================================================
// Project Description (use | for new lines)

package main

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

func mainB() {
	reader := bufio.NewReader(os.Stdin)

	var T int
	fmt.Fscan(reader, &T) 

	for t := 0; t < T; t++ {
		var n int
		fmt.Fscan(reader, &n) 
		var s string
		fmt.Fscan(reader, &s)

		ma := 0 
		for _, char := range s {
			as := int(char)
			if as > ma {
				ma = as
			}
		}
		fmt.Println(ma) 
	}
}
C题 (C.go)

思路总结: 这道题的目标是构造一个由'4'和'8'组成的、总价值为k的最小数字。"4"的价值是1，"8"的价值是2。

为了让构造出的数字最小，位数应该尽可能少。因为'8'的价值(2)是'4'的价值(1)的两倍，所以应该优先使用'8'来减少位数。

具体策略是：

  1. 将k对2进行整除，商a表示需要多少个'8'。

  2. k对2取模，如果余数为1 (b=true)，说明还需要一个价值为1的'4'。

  3. 为了使数字最小，较小的数字'4'应该放在较高的位（即最前面）。所以，如果需要'4'，就先在结果中添加一个'4'。

  4. 然后，在后面追加a个'8'。

  5. 特殊情况：如果k=0，价值为0，无法用'4'或'8'表示，但题目可能要求输出一个有效数字，根据代码逻辑，此时输出'1'（可能是题目特定要求或默认值）。

// ==========================================================
//                    POWERED BY GMJ                         
//                   2025-07-06 19:04
// ==========================================================
// Github:     https://github.com/Joker-0111-G
// CSDN:       https://blog.csdn.net/dl999666?type=blog
// Gmail:      joker0111gmj@gmail.com
// Author:     USER <joker0111gmj@gmail.com>
// FilePath:   ~/homegmj/GoCode/NK/20250706\C.go
// License:    MIT
// Copyright:  (c) 2025 JOKER. All rights reserved.
// ==========================================================
//    __  __    _  _____ _   _  ____ __  __     _
//    \ \/ /   / \|_   _| | | |/ ___|  \/  |   | |
//     \  /   / _ \ | | | | | | |  _| |\/| |_  | |
//     /  \  / ___ \| | | |_| | |_| | |  | | |_| |
//    /_/\_\/_/   \_\_|  \___/ \____|_|  |_|\___/
// ==========================================================
// Project Description (use | for new lines)


package main

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

func mainC() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush() 

	var T int
	fmt.Fscan(reader, &T) 

	for i := 0; i < T; i++ {
		var k int
		fmt.Fscan(reader, &k) 

		if k == 0 {
			fmt.Fprintln(writer, 1) 
			continue
		}
		a := k / 2
		b := (k % 2 == 1)

		var res strings.Builder 
		if b {
			res.WriteByte('4') 
		}

		for j := 0; j < a; j++ {
			res.WriteByte('8')
		}

		fmt.Fprintln(writer, res.String()) 
	}
}
D题 (D.go)

思路总结: 这是一道数学或逻辑推导题。给定x和p，需要计算一个结果。

通过分析代码逻辑 a := p / x 和 b := p - a，我们可以推断这可能与某种分配或分组有关。 核心判断在于 p % x == 0：

  • 如果 p 能被 x 整除，结果是 2*a - 1。这里的 a 就是 p/x。

  • 如果 p 不能被 x 整除，结果是 2 * b。这里的 b 是 p - p/x。

这暗示了两种不同的计算场景。在能整除的情况下，可能存在某种合并或特殊状态，导致结果减1。在不能整除的情况下，则是基于p和商a的差值进行计算。解题的关键是理解这两种情况对应的具体数学模型。

// ==========================================================
//                    POWERED BY GMJ                         
//                   2025-07-06 19:10
// ==========================================================
// Github:     https://github.com/Joker-0111-G
// CSDN:       https://blog.csdn.net/dl999666?type=blog
// Gmail:      joker0111gmj@gmail.com
// Author:     USER <joker0111gmj@gmail.com>
// FilePath:   ~/homegmj/GoCode/NK/20250706\D.go
// License:    MIT
// Copyright:  (c) 2025 JOKER. All rights reserved.
// ==========================================================
//    __  __    _  _____ _   _  ____ __  __     _
//    \ \/ /   / \|_   _| | | |/ ___|  \/  |   | |
//     \  /   / _ \ | | | | | | |  _| |\/| |_  | |
//     /  \  / ___ \| | | |_| | |_| | |  | | |_| |
//    /_/\_\/_/   \_\_|  \___/ \____|_|  |_|\___/
// ==========================================================
// Project Description (use | for new lines)

package main

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

func mainD() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush() 

	var T int
	fmt.Fscan(reader, &T) 

	for i := 0; i < T; i++ {
		var x, p int
		fmt.Fscan(reader, &x, &p) 
		a := p / x 
		b := p - a

		var res int
		if p%x == 0 {
			res = 2*a - 1
		}else{
			res = 2 * b
		}

		fmt.Fprintln(writer, res) 
	}
}
E题 (E.go)

思路总结: 这道题是一道动态规划（DP）问题。目标是求解对一个数组进行操作后，需要移除多少个只出现一次的元素。

问题可以转化为：最多能保留多少个只出现一次的元素。

我们定义DP状态：

  • dp0: 表示处理到第 i 个元素时，不选择第 i 个元素能保留的最多独特元素数量。

  • dp1: 表示处理到第 i 个元素时，选择第 i 个元素（前提是a[i]是独特元素且满足某种条件）能保留的最多独特元素数量。

状态转移方程: 遍历数组 a 从 1到 n：

  1. 计算 next_dp0 (不选当前元素 a[i-1]):

    • 可以从 dp0 (前一个也不选) 转移而来。

    • 也可以从 dp1 (前一个选了) 转移而来，只要满足不冲突的条件 (如 a[i-2] < i)。

    • next_dp0 = max(dp0, dp1_if_valid)

  2. 计算 next_dp1 (选择当前元素 a[i-1]):

    • 首先，a[i-1] 必须是只出现一次的元素。

    • 可以从 dp0 转移：dp0 + 1，需满足条件 (如 i-1 < a[i-1])。

    • 可以从 dp1 转移：dp1 + 1，需满足条件 (如 a[i-2] < a[i-1])。

    • next_dp1 = max(dp0_to_dp1, dp1_to_dp1)

遍历结束后，max(dp0, dp1) 就是最多能保留的独特元素数量 maxLen。

最终答案是 总的独特元素数量 - maxLen。

// ==========================================================
//
//	POWERED BY GMJ
//	2025-07-06 19:18
//
// ==========================================================
// Github:      https://github.com/Joker-0111-G
// CSDN:        https://blog.csdn.net/dl999666?type=blog
// Gmail:       joker0111gmj@gmail.com
// Author:      USER <joker0111gmj@gmail.com>
// FilePath:    ~/homegmj/GoCode/NK/20250706/E_fixed.go
// License:     MIT
// Copyright:   (c) 2025 JOKER. All rights reserved.
// ==========================================================
//
//	__  __    _  _____ _  _  ____ __  __     _
//	\ \/ /   / \|_   _| | | |/ ___|  \/  |   | |
//	 \  /   / _ \ | | | | | | |  _| |\/| |_  | |
//	 /  \  / ___ \| | | |_| | |_| | |  | | |_| |
//	/_/\_\/_/   \_\_|  \___/ \____|_|  |_|\___/
//
// ==========================================================
package main

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

var (
	in     = bufio.NewScanner(os.Stdin)
	out    = bufio.NewWriter(os.Stdout)
	negInf = -1 << 30
)

func init() {
	in.Split(bufio.ScanWords)
}

func readInt() int {
	in.Scan()
	n, _ := strconv.Atoi(in.Text())
	return n
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func solve() {
	n := readInt()
	a := make([]int, n)
	freq := make(map[int]int)
	for i := 0; i < n; i++ {
		val := readInt()
		a[i] = val
		freq[val]++
	}

	numTotalUnique := len(freq)
	isUnique := make(map[int]bool)
	for val, count := range freq {
		if count == 1 {
			isUnique[val] = true
		}
	}

	dp0 := 0
	dp1 := negInf

	for i := 1; i <= n; i++ {
		a_i := a[i-1]
		ndp0_from_dp0 := dp0
		ndp0_from_dp1 := negInf
		if i > 1 {
			if a[i-2] < i {
				ndp0_from_dp1 = dp1
			}
		}
		next_dp0 := max(ndp0_from_dp0, ndp0_from_dp1)

		next_dp1 := negInf
		if isUnique[a_i] {
			ndp1_from_dp0 := negInf
			if i-1 < a_i {
				ndp1_from_dp0 = dp0 + 1
			}

			ndp1_from_dp1 := negInf
			if i > 1 {
				if a[i-2] < a_i {
					ndp1_from_dp1 = dp1 + 1
				}
			}
			next_dp1 = max(ndp1_from_dp0, ndp1_from_dp1)
		}

		dp0 = next_dp0
		dp1 = next_dp1
	}

	maxLen := max(dp0, dp1)
	fmt.Fprintln(out, numTotalUnique-maxLen)
}

func mainE() {
	defer out.Flush()
	t := readInt()
	for t > 0 {
		solve()
		t--
	}
}
F题 (F.go)

思路总结: 这道题要求在满足特定条件下找到一个最大的整数 h。条件是：n 可以表示为 m 个数 x_i 的和（n = x_1 + ... + x_m），其中每个 x_i 都大于等于 h，并且 x_i 和 h 的按位与（bitwise AND）都为0。

核心思路是贪心 + 位运算检验。

  1. 贪心策略: 从高位到低位（例如从第30位开始）尝试构建 h。我们希望 h 尽可能大，所以优先尝试将高位置为1。

  2. 构建过程:

    • 初始化答案 ans = 0。

    • 从 b = 30 到 0 循环。

    • 在每一位 b，我们尝试将 ans 的第 b 位置为1，形成一个临时的 h，即 h = ans | (1 << b)。

  3. 检验可行性:

    • 将每个 x_i 分解为 h + y_i。因为 x_i & h == 0，所以 x_i >= h 等价于 y_i >= 0 且 y_i & h == 0。

    • 原方程 n = sum(x_i) 变为 n = sum(h + y_i) = m*h + sum(y_i)。

    • 我们需要检验 rem = n - m*h (剩余部分) 是否能被分配到 m 个 y_i 中，同时满足 y_i >= 0 和 y_i & h == 0。

    • 这个检验过程由 check(rem, m, h) 函数完成。

  4. check函数逻辑:

    • 该函数通过从高位到低位逐位处理 rem 来判断分配是否可能。

    • 它维护一个 debt（债务）变量。对于 rem 的每一位，如果 h 的对应位是1，那么 y_i 的这一位必须是0，所以 rem 在这一位的1不能被分配，会累积成“债务”传递给更低的位。

    • 如果 h 的对应位是0，那么 y_i 的这一位可以是1，我们可以用这m个数来“偿还”债务。最多可以偿还 m。

    • 如果在任何时候债务过大（溢出风险），或者到最后债务没有清零，则说明分配失败。

  5. 更新答案:

    • 如果 check 函数返回 true，说明将第 b 位置为1是可行的，我们更新 ans = h。

    • 否则，保持 ans 不变，继续尝试下一位。

最终得到的 ans 就是满足条件的最大 h。

// ==========================================================
//                    POWERED BY GMJ
//                   2025-07-06 19:25
// ==========================================================
// Github:     https://github.com/Joker-0111-G
// CSDN:       https://blog.csdn.net/dl999666?type=blog
// Gmail:      joker0111gmj@gmail.com
// Author:     USER <joker0111gmj@gmail.com>
// FilePath:   ~/homegmj/GoCode/NK/20250706\F.go
// License:    MIT
// Copyright:  (c) 2025 JOKER. All rights reserved.
// ==========================================================
//    __  __    _  _____ _   _  ____ __  __     _
//    \ \/ /   / \|_   _| | | |/ ___|  \/  |   | |
//     \  /   / _ \ | | | | | | |  _| |\/| |_  | |
//     /  \  / ___ \| | | |_| | |_| | |  | | |_| |
//    /_/\_\/_/   \_\_|  \___/ \____|_|  |_|\___/
// ==========================================================
// Project Description (use | for new lines)

package main

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

// max devuelve el mayor de dos enteros int64.
func max(a, b int64) int64 {
	if a > b {
		return a
	}
	return b
}

// check determina si 'rem' (el resto) se puede escribir como la suma
// de 'm' enteros no negativos, donde cada uno es bitwise ortogonal a 'h'.
func check(rem int64, m int64, h int64) bool {
	var debt int64 = 0 // 'debt' acumula la deuda desde los bits más significativos.

	// Iteramos desde un bit alto para manejar cualquier acarreo de forma segura.
	for j := 62; j >= 0; j-- {
		// Si ya no quedan bits en 'rem' y la deuda es cero, podemos parar.
		if debt == 0 && (rem>>j) == 0 {
			continue
		}

		// Si la deuda es demasiado grande, es imposible que se pague.
		// Esto previene el desbordamiento (overflow) de 'debt'.
		// 1<<62 es una cota segura que está por debajo del límite de int64.
		if debt >= (1 << 62) {
			return false
		}

		// Acumulamos la deuda, desplazándola e incluyendo el bit actual de 'rem'.
		debt = debt*2 + (rem>>j)&1

		// Si el bit j está "permitido" (h_j == 0), podemos usar nuestros 'm'
		// créditos para pagar la deuda.
		if (h>>j)&1 == 0 {
			debt = max(0, debt-m)
		}
	}

	// Si al final del proceso la deuda es cero, la distribución es posible.
	return debt == 0
}

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

	var T int
	fmt.Fscan(in, &T)

	for t := 0; t < T; t++ {
		var n, m int64
		fmt.Fscan(in, &n, &m)

		var ans int64 = 0
		// Estrategia greedy: construir la respuesta desde el bit más significativo (30).
		for b := 30; b >= 0; b-- {
			h := ans | (1 << b)

			// Si m*h > n, es imposible. Usamos n/m para evitar desbordamientos.
			if h > n/m {
				continue
			}

			rem := n - m*h

			// Verificamos si este resto se puede distribuir correctamente.
			if check(rem, m, h) {
				// Si es posible, aceptamos este bit.
				ans = h
			}
		}
		fmt.Fprintln(out, ans)
	}
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布