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

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

前言

前段时间准备省赛，运气好进国赛了。所以就开始准备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 位重新补到低位，实现循环移位。

3. 示例说明
   以 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)。

三、手动推导规律（前几项案例）

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

四、核心规律总结

最大数的位置特性：
设当前有 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 组的国赛题。还是有收获的，是吧大伙~

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

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

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

下期见咯~