第十五届蓝桥杯大赛软件赛国赛Python 大学 C 组试做【本期题单: 循环位运算、分割字符串 、 粉刷匠小蓝 】

发布于:2025-06-16 ⋅ 阅读:(35) ⋅ 点赞:(0)

早上好啊大伙,这一期依旧是蓝桥杯备赛刷题的记录。
本期题单:循环位运算、分割字符串 、 粉刷匠小蓝

在这里插入图片描述

前言

前段时间准备省赛,运气好进国赛了。所以就开始准备6月份的国赛。但是近期还有别的比赛要准备,所以刷题的速度比较慢,可能每一期就会有一两道题目。

如果大伙再刷哪道题的时候遇到问题了,也可以留言或者私信,小白兔会去先尝试一下那到题目。

循环位运算

题目

题目链接:循环位运算
在这里插入图片描述

思路分析

本题主要在于两个难点:

  1. 怎么分配次数,才能得到最大值
  2. 循环 2 进制

一、难点一:如何分配操作次数最大化结果

  1. 问题本质分析

    题目要求:给定 n 个数和 m 次操作,将 m 次操作分配给每个数(每个数可分配 0~m 次),使得最终结果最大。
    核心矛盾:每次操作对不同数的增益不同,需找到最优分配策略。

  2. 算法选型推导

    候选算法:动态规划(DP)、贪心、BFS、DFS。
    为什么是背包问题?
    特征匹配:
    「物品」:对每个数的操作次数(每次操作视为一个物品,次数为数量)。
    「容量」:总操作次数 m(分配次数不能超过 m)。
    「价值」:每次操作对该数的增益(需计算每次操作后的数值变化)。
    类型判定:属于「多重背包问题」—— 每个数可分配多次操作,但次数有限(≤m),需最大化总价值。

  3. 背包模型构建

    定义 dp[j] 为使用 j 次操作时能得到的最大值。
    状态转移:对每个数 num[i],计算分配 k 次操作(k=0~m)后的增益,更新 dp[j+k] = max(dp[j+k], dp[j] + gain(num[i], k)),其中 gain(num[i], k) 为对 num[i] 执行 k 次操作后的数值增量。

二、难点二:循环二进制移位的实现

  1. 操作原理解析
    循环二进制移位指将二进制数左移后,溢出的高位从低位补回,形成环形移位。例如:

    32 位二进制数 a,左移 x 位后,高位的 x 位溢出,需将其作为低位补回。

  2. 代码实现与解释

a = a << (x) | a >> (32 - x)

分解步骤:
a << x:左移 x 位,高位溢出的 x 位被暂存到进位标志中(实际代码中左移溢出部分会被丢弃)。
a >> (32 - x):右移 32 - x 位,将原数的低 32 - x 位移至高位,此时高位补 0(逻辑右移)。
| 运算:将左移结果与右移结果按位或,使溢出的 x 位重新补到低位,实现循环移位。

  1. 示例说明
    以 4 位二进制数 a = 1010(十进制 10)、x=1 为例:

    左移 1 位:1010 << 1 = 10100(4 位下溢出为 0100)。
    右移 4-1=3 位:1010 >> 3 = 0001。
    按位或:0100 | 0001 = 0101(十进制 5),即循环左移 1 位后的结果为 0101,等价于原数右移 3 位。

老规矩,大伙按照上面的想法写写看,我也先写写看。下面代码见咯~

代码

n, m = map(int, input().split())  # 读取数组长度n和最大操作次数m
nums = [int(input()) for _ in range(n)]  # 读取n个整数存入列表

dp = [0] * (m + 1)  # 初始化动态规划数组,dp[i]表示使用i次操作后的最大数组和
dp[0] = sum(nums)  # 初始状态:0次操作时,数组和为所有数的总和

for num in nums:  # 遍历数组中的每个数字
    ndp = dp.copy()  # 复制当前dp数组,用于存储更新后的状态,避免覆盖原状态
    
    adds = []  # 存储当前数字所有有效操作的(操作次数, 增加值)
    # 计算1到min(32, m)次循环左移的有效操作(只保留增加值≥0的操作)
    for i in range(1, min(32, m) + 1):
        # 计算循环左移i位后的数值变化:
        # 1. (num << i) | (num >> (32 - i)) 实现32位循环左移
        # 2. & 0xFFFFFFFF 确保结果为32位无符号整数
        # 3. 减去原数得到增加值add
        add = (((num << i) | (num >> (32 - i))) & 0xFFFFFFFF) - num
        if add >= 0:  # 只保留能让数值变大的操作
            adds.append((i, add))
    
    # 遍历所有可能的已使用操作次数i
    for i in range(m + 1):
        if dp[i] == 0:  # 若i次操作的状态未被更新过(无效状态),跳过
            continue
        # 对每个有效操作(j次操作,增加add值)进行状态转移
        for j, add in adds:
            if i + j <= m:  # 确保总操作次数不超过m次
                # 若通过i+j次操作能得到更大的数组和,则更新状态
                if ndp[i + j] < dp[i] + add:
                    ndp[i + j] = dp[i] + add
    dp = ndp  # 更新dp数组为当前数字处理后的最优状态

print(max(dp))  # 输出所有操作次数下的最大数组和

分割字符串

题目

题目链接: 分割字符串

在这里插入图片描述

思路分析

这道题的思路其实是蛮清晰的,就是dfs,找出所有的情况,然后排查就行了。

因为题目中字符串本质不同,所以可以用 set 来存储,然后最后的答案也可以直接取差集就可以了。

再用 dp 记忆化数据优化 dfs,就行解决。

代码

import sys
sys.setrecursionlimit(1<<20)  # 设置递归深度限制,防止栈溢出

def dfs(i, j):
    """
    深度优先搜索函数,判断从位置i开始,能否找到有效的子串划分
    i: 当前处理的位置
    j: 上一个子串的长度
    """
    # 记忆化搜索:如果状态已计算过,直接返回结果
    if (i, j) in dp:
        return dp[(i, j)]
    
    # 递归终止条件:已处理完所有字符,找到有效划分
    if i >= n:
        return True
    
    # 收集前一个子串中出现过的字符
    prev_char = set() 
    for c in range(max(0, i-j), i):
        prev_char.add(S[c])
    
    res = False  # 初始化结果为False
    
    # 尝试当前子串的长度(1到5)
    for le in range(1, 6):
        if i + le > n:  # 越界检查
            break 
        
        cur = False  # 标记当前子串是否包含前一个子串中的字符
        for c in S[i:i+le]:
            if c in prev_char:
                cur = True
                break
        
        # 如果当前子串不包含前一个子串中的字符,且后续可以找到有效划分
        if not cur and dfs(i+le, le):
            can_sub.add(S[i:i+le])  # 将当前子串加入可行子串集合
            res = True  # 更新结果为True
    
    dp[(i, j)] = res  # 记忆化存储结果
    return res

# 主程序
S = input().strip()  # 读取输入字符串
n = len(S)  # 获取字符串长度

can_sub = set()  # 存储所有可行的子串
all_sub = set()  # 存储所有可能的子串

# 预处理:生成所有可能的子串(长度1到5)
for i in range(n):
    for j in range(1, 6):
        if i + j <= n:  # 确保不越界
            all_sub.add(S[i:i+j])

dp = {}  # 记忆化存储字典
    
dfs(0, 0)  # 从位置0开始搜索,初始前一个子串长度为0

# 计算所有不可能出现的子串(差集),并按字典序排序
ans = sorted(all_sub - can_sub)

# 输出结果
print(len(ans))
for t in ans:
    print(t)

粉刷匠小蓝

题目

题目链接:粉刷匠小蓝

在这里插入图片描述
在这里插入图片描述

思路分析

这题做得太顺利了,很棒,我很喜欢……

一、问题要求拆解

  1. 核心任务:将指定墙面刷成蓝色,且右侧蓝色墙面的总数为偶数。
  2. 关键条件:仅处理标记为 “1” 的墙面(标记为 “0” 的墙面无需处理)。

二、解题思路分析

  1. 初步处理:统计有效墙面数量
    首先需统计需要刷的墙面(即 “1”)的总数,记为 n。后续计算均基于 n 的值展开。

  2. 方案选择:动态规划(DP) vs 深度优先搜索(DFS)

    DFS 的局限性:若直接枚举所有刷墙顺序,时间复杂度为 O(n!),当 n 较大时必然超时。
    DP 的优势:通过寻找规律,将问题转化为状态转移,时间复杂度可优化至 O(n)。

三、手动推导规律(前几项案例)

通过枚举小数据量的情况,寻找可行方案数的规律:

1 的数量 可行的方案 总数
1 1 1
2 1 2 1
3 1 2 3、3 1 2 2
4 1 2 3 4、3 1 2 4、1 4 2 3、3 4 1 2 4
…… …… ……

四、核心规律总结

最大数的位置特性:
设当前有 n 个需要刷的墙面,编号为 1~n(按顺序排列)。最终刷墙顺序中,最大的数 n 必须出现在奇数位置(如第 1、3、5 位等)。

原因:
若 n 出现在偶数位置,其右侧剩余墙面数为奇数,无法满足 “右侧蓝色墙面总和为偶数” 的条件。只有当 n 出现在奇数位置时,右侧墙面数为偶数,才能通过后续排列满足条件。

动态规划状态转移:
定义 dp[i] 为 i 个墙面时的可行方案数。
当确定最大数 i 的位置后,剩余 i-1 个墙面的排列需满足同样规则。观察前几项数据:
dp[1] = 1
dp[2] = 1 = dp[1]
dp[3] = 2 = dp[2] × 2?不,实际规律为 dp[i] = dp[i-1] × (i的奇偶性相关因素)?

更正:通过前几项发现 dp[1]=1, dp[2]=1, dp[3]=2=dp[2]×2, dp[4]=4=dp[3]×2,即 dp[i] = dp[i-1] × 2(当 i ≥ 2 时)。

五、结论与动态规划实现

方案总数公式:
当 n=0 时,方案数为 1(无墙面需刷)。
当 n≥1 时,dp[n] = dp[n-1] × 2,即 dp[n] = 2^(n-1)。
(如 n=1 时,2^0=1;n=2 时,2^1=1?此处需注意前几项中 n=2 时方案数为 1,与公式 2^(2-1)=2 矛盾,说明规律推导需更严谨。实际正确规律应为:dp[n] = dp[n-1] × (n为奇数时乘2,n为偶数时乘1)?需重新核对前几项:
n=1:1 种
n=2:1 种(dp[2]=dp[1]×1)
n=3:2 种(dp[3]=dp[2]×2)
n=4:4 种(dp[4]=dp[3]×2)

故正确转移方程为:dp[i] = dp[i-1] × 2(当 i 为奇数时),dp[i] = dp[i-1](当 i 为偶数时)。)

最终解法:
统计需要刷的墙面数 n。
若 n=0,返回 1。
否则,从 n=1 开始递推,根据 i 的奇偶性计算 dp[i],最终 dp[n] 即为可行方案数。

看懂了吗?没看懂再列一遍。

看懂了吗?看懂了就试试吧~

代码

mod = int(1e9 + 7)  # 定义取模常量,防止整数溢出

n = int(input())  # 读取输入的整数个数
lst = list(map(int, input().split()))  # 读取整数列表
cnt = lst.count(1)  # 统计列表中数字1的出现次数

# 初始化动态规划数组,大小为(cnt+10),预留足够空间
dp = [0] * (cnt + 10)

# 设置初始条件:
dp[0] = dp[1] = dp[2] = 1

# 处理特殊情况:如果列表中没有数字1,直接输出1
if cnt == 0:
    print(1)
else:
    # 动态规划状态转移:计算有i个数字1时的方案数
    for i in range(3, cnt + 1):
        # 计算当前步骤的关键系数t:(i-1)//2 + 1
        # 这个系数决定了状态转移的方式
        t = (i - 1) // 2 + 1
        # 状态转移方程:当前方案数 = 系数t * 前一个状态的方案数
        # 取模操作确保结果在int范围内
        dp[i] = (t * dp[i-1]) % mod
    
    # 输出最终结果:有cnt个数字1时的方案数
    print(dp[cnt])

尾声

OK,写完这些题,我们就完成了 C 组的国赛题。还是有收获的,是吧大伙~

继续努力吧,希望能拿个不错的名次,与大伙共勉!

感谢大伙观看,别忘了三连支持一下

大家也可以关注一下我的其它专栏,同样精彩喔~

下期见咯~

请添加图片描述


网站公告

今日签到

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