罗文彬

large picture of the cover

第 33 场 蓝桥·算法入门赛·百校联赛 题解

第 33 场 蓝桥·算法入门赛·百校联赛 题解

比赛链接：https://www.lanqiao.cn/oj-contest/newbie-33/

参考代码使用 Python语言，其他语言可以让发给AI让它转

1. 礼物打包

题目链接

解题思路

输出所有数字相加

参考代码

print(1+2+4+8+16+32+64)

2. 圣诞博弈

题目链接

解题思路(最优策略下的总和等价)

小蓝和对手轮流取卡，共 ​ n 张。

  • 小蓝先手，他拿的每张卡乘以 ​ +k ；
  • 对手后手，他拿的每张卡乘以 ​ -k 。

双方都采取最优策略：

  • 小蓝希望最大化 ​ A - B ，所以他会优先拿最大的数；
  • 对手希望最小化 ​ A - B ，等价于让自己的贡献尽可能“负得少”

不过，​ A - B = k \cdot (\text{小蓝总和}) - (-k \cdot \text{对手总和}) = k \cdot (\text{所有卡片总和}) ，其实无论怎么分配，结果都一样！

更直接地说：

每张卡片最终都会被某人拿走，而它对 ​ A - B 的贡献总是 ​ \pm k \cdot a_i 。
但因为小蓝拿时是 ​ +k \cdot a_i ，对手拿时是 ​ -(-k \cdot a_i) = +k \cdot a_i （因为 ​ A - B = A + |B| ），
所以每张卡片对答案的贡献都是 ​ +k \cdot a_i 。

因此：

A - B = k \cdot (a_1 + a_2 + \cdots + a_n)

直接输出 sum(a) * k 即可。

参考代码

import sys

n, k = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))

# 无论怎么取，A - B = k * 所有卡片之和
print(sum(a) * k)

3. 蓝小骑

解题思路(二进制枚举组合)

本题要求计算在给定四种付费方式下，完成 ​ q 分钟骑行所需的最少花费。

付费方式：

  1. 按时计费：每分钟 ​ x_1 元 → 可无限使用，适合补足时间。
  2. 基础订阅包：花 ​ x_2 元，得 ​ t_2 分钟免费时间（只能买一次）。
  3. 标准订阅包：花 ​ x_3 元，得 ​ t_3 分钟免费时间（只能买一次）。
  4. 高级订阅包：花 ​ x_4 元，得 ​ t_4 分钟免费时间（只能买一次）。

订阅包可以任意组合购买（最多各一个），不足部分用按时计费补上。

二进制枚举所有可能的订阅包组合

由于每个订阅包最多买一次，共有 ​ 2^3 = 8 种组合（不买或买基础、标准、高级中的任意子集）。

对每种组合：

  • 计算总免费时间 ​ T
  • 若 ​ T \geq q ，则无需按时计费，花费为该组合总价
  • 否则，剩余时间 ​ q - T 用按时计费补上，费用为 ​ (q - T) \times x_1

取所有组合中最小花费即可。

参考代码

import sys


def main():
    x1, x2, x3, x4 = map(int, sys.stdin.readline().split())
    t2, t3, t4 = map(int, sys.stdin.readline().split())
    q = int(sys.stdin.readline())

    min_cost = 10 ** 18

    # 二进制枚举三种订阅包的所有组合(000~111)
    for mask in range(8):
        total_time = 0
        cost = 0

        # 基础订阅包(001)
        if mask & 1:
            total_time += t2
            cost += x2

        # 标准订阅包(010)
        if mask & 2:
            total_time += t3
            cost += x3

        # 高级订阅包(100)
        if mask & 4:
            total_time += t4
            cost += x4

        # 如果时间足够，直接用
        if total_time >= q:
            min_cost = min(min_cost, cost)
        else:
            # 不足部分用按时计费补
            extra = q - total_time
            min_cost = min(min_cost, cost + extra * x1)

    print(min_cost)


if __name__ == '__main__':
    main()

复杂度分析

  • 时间复杂度：​ O(1) ，只有 8 种组合；
  • 空间复杂度：​ O(1) 。

适用于 ​ q \leq 10^9 的大数情况。

4. 清理横幅

题目链接

解题思路(直接找最右目标字符)

题目说每次操作会删除第 cnt 个字符（cnt 是当前字符串中 'L'、'Q'、'B' 的总数），重复直到没有这些字符。

但其实不用模拟！
只要字符串里还有 'L'、'Q' 或 'B'，操作就不会停。而最后一个这样的字符出现在位置 i（从0开始数），那么前 i+1 个字符肯定都会被删掉——因为每次删一个，删到它为止至少要删 i+1 次。

反过来，删了 i+1 次后，这个字符就没了，它前面的也都删光了，自然就没有 'L'/'Q'/'B' 了。

所以答案就是：最右边的 'L'、'Q' 或 'B' 的位置 + 1。
如果一个都没有，答案是 0。

做法：从右往左扫一遍，找到第一个 'L'、'Q' 或 'B' 就行。

参考代码

import sys

def main():
    s = sys.stdin.readline().strip()
  
    # 从右往左查找最后一个 'L'、'Q' 或 'B'
    for i in reversed(range(len(s))):
        if s[i] in 'LQB':
            # 找到了，位置是 i（0-indexed），答案是 i+1（1-indexed）
            print(i + 1)
            return
  
    # 如果没找到任何 L/Q/B，说明不需要操作
    print(0)

if __name__ == '__main__':
    main()

5. 花灯调整

题目链接

解题思路(贪心模拟 + 操作顺序优化)

本题要求判断：是否存在一种操作顺序，使得 ​ k 位游客分别对前缀 ​ [1, p_i] 的花灯进行翻转操作后，最终状态与目标字符串 ​ S 完全一致。

关键在于理解：操作顺序可以任意安排，因此我们可以通过合理排序操作来最大化控制能力。由于每次操作是“翻转前缀”，我们可以利用贪心策略从左到右逐位验证是否可能达到目标状态。

核心观察：操作顺序可任意排列

  • 每个游客选择一个前缀长度 ​ p_i ，将 ​ [1, p_i] 内的所有灯状态翻转（0→1，1→0）。
  • 所有操作的执行顺序可以自由调整，因此我们可以按 ​ p_i 从小到大排序，依次处理。
  • 这样做可以保证：当处理到第 ​ i 个位置时，所有影响该位置的操作（即所有 ​ p_j \geq i ）已经按顺序处理过。

状态推导逻辑

  • 初始状态为全关（'0'），共 ​ n 盏灯。
  • 每次操作会翻转某个前缀，因此某盏灯被翻转的次数等于 有多少个 ​ p_i \geq 当前灯的位置。
  • 由于翻转两次等于没翻，所以只需关心每盏灯被翻转了奇数次还是偶数次。
  • 若翻转奇数次 → 最终状态与初始不同；若偶数次 → 保持原状。

贪心模拟流程

  1. 将所有 ​ p_i 排序，得到从小到大的操作序列。
  2. 从左到右遍历每个灯的位置 ​ i ：
    • 统计当前有多少个已处理的操作满足 ​ p_j \geq i ，即这些操作会影响第 ​ i 盏灯。
    • 记录当前灯的状态（初始为 '0'），每遇到一个 ​ p_j \geq i ，就翻转一次。
  3. 比较当前状态与目标 ​ s[i] 是否一致。
  4. 若全部匹配，则输出 "Yes"，否则 "No"。

关键点：由于操作顺序可任意安排，我们可以按 ​ p_i 升序处理，这样能确保在处理第 ​ i 个位置时，所有影响它的操作都已经被考虑。

参考代码

import sys

def main():
    # 读取输入
    n, k = map(int, sys.stdin.readline().split())
    s = sys.stdin.readline().strip()  # 目标图案
    p = list(map(int, sys.stdin.readline().split()))  # 每位游客选择的前缀长度
  
    # 将操作按前缀长度升序排列，便于从左到右处理
    p.sort()
  
    # 当前灯的状态，初始为关闭（'0'）
    cur = '0'
    index = 0  # 当前正在处理的操作索引
    flag = True  # 是否能匹配成功
  
    # 从左到右遍历每一盏灯
    for i in range(n):
        # 处理所有 p[index] <= i 的操作（即影响当前位置的操作）
        while index < k and p[index] <= i:
            # 每次操作都会翻转当前灯的状态
            cur = '0' if cur == '1' else '1'
            index += 1
    
        # 如果已经处理完所有操作，后续灯的状态不再变化
        if index == k:
            break
        
        # 检查当前灯的状态是否与目标一致
        if s[i] != cur:
            flag = False
            break
  
    # 输出结果
    if flag:
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    main()

方法说明

  • 时间复杂度：​ O(n + k \log k) ，主要开销在排序 ​ p 数组。
  • 空间复杂度：​ O(k) ，用于存储排序后的操作数组。
  • 正确性保证：通过按 ​ p_i 升序处理操作，确保每个位置的影响被完整统计，且不会遗漏或重复。

本题的核心思想是“操作顺序可调”，因此可以将问题转化为贪心模拟，无需枚举所有排列组合。

6. 圣诞礼物

题目链接

解题思路

本题要求找到最小的非负整数 ​ X ，使得 ​ A + X 能整除 ​ B + 2X 。直接枚举 ​ X 在 ​ 10^9 范围内显然不可行，因此需要通过代数变换将问题转化为因数枚举问题。

变量替换与整除转化

我们令

d = A + X \quad \Rightarrow \quad X = d - A

将其代入被除数：

B + 2X = B + 2(d - A) = (B - 2A) + 2d

由于 ​ d \mid 2d 恒成立，因此

d \mid (B + 2X) \iff d \mid (B - 2A)

也就是说，只要 ​ d 是 ​ B - 2A 的一个正因数，并且 ​ d \geq A （保证 ​ X \geq 0 ），那么 ​ X = d - A 就是一个合法解。

所以只需要枚举 ​ B - 2A 的正因数并找到最小的大于等于A的就可以了

特殊情况处理

  • 若 ​ B - 2A = 0 ，即 ​ B = 2A ，则对任意 ​ d > 0 都有 ​ d \mid 0 ，因此最小的 ​ X = 0 。
  • 若 ​ B - 2A < 0 ，由于整除性与符号无关，我们只需考虑其绝对值 ​ |B - 2A| 的正因数。

算法步骤

  1. 计算 ​ D = B - 2A 。
  2. 若 ​ D = 0 ，直接输出 0。
  3. 否则取 ​ D = |D| ，枚举其所有正因数。
  4. 在所有因数中，找出满足 ​ d \geq A 的最小值。
  5. 若存在，答案为 ​ d - A ；否则无解，输出 -1。

该方法的时间复杂度为 ​ O(\sqrt{|B - 2A|}) ，在 ​ B \leq 10^9 时完全可行。

参考代码

import sys

def main():
    # 找到x使得(B+2X)%(A+X)==0
    # 令d = A+X => X = d - A
    # B+2X = B + 2d - 2A 是d的倍数
    # => B-2A是d的倍数
    # 只需要枚举B-2A的所有正因数，找到最小的d>=A，X = d - A
    A, B = map(int, sys.stdin.readline().split())
  
    # 计算 D = B - 2A
    D = B - 2 * A
  
    # 特殊情况：D == 0，此时任意 d = A+X 都能整除 0，取 X=0 最小
    if D == 0:
        print(0)
        return
  
    # 取绝对值，因为因数只关心大小，不关心符号
    D = abs(D)
  
    # 枚举 D 的所有正因数
    factors = []
    i = 1
    while i * i <= D:
        if D % i == 0:
            factors.append(i)           # i 是一个因数
            if i != D // i:             # 避免平方数重复添加
                factors.append(D // i)
        i += 1
  
    # 对因数排序，以便从小到大找第一个 >= A 的
    factors.sort()
  
    # 遍历因数，找最小的 d >= A
    for d in factors:
        if d >= A:
            print(d - A)                # X = d - A
            return
  
    # 如果没有因数 >= A，则无解
    print(-1)

if __name__ == '__main__':
    main()

一个敲代码的

site logo

罗文彬的个人站

© 2025 罗文彬