蓝桥杯倒计时 | 倒计时10天
作者🕵️♂️：让机器理解语言か
专栏🎇：蓝桥杯倒计时冲刺
描述🎨：蓝桥杯冲刺阶段，一定要沉住气，一步一个脚印，胜利就在前方！
寄语💓：🐾没有白走的路，每一步都算数！🐾
目录
题目一：X进制减法
思路：
代码：
题目二：扫雷
思路：
代码：
题目三：李白打酒加强版
题目大意：
法一：暴力法：（排列）
法二：递归
代码1：（递归：40%）
法三： DP
状态转移方程：
代码2：（DP：AC）
题目一：X进制减法
问题描述
进制规定了数字在数位上逢几进一。
X 进制是一种很神奇的进制, 因为其每一数位的进制并不固定！例如说某 种 X 进制数, 最低数位为二进制, 第二数位为十进制, 第三数位为八进制, 则 X 进制数 321 转换为十进制数为 65 。
现在有两个 X 进制表示的整数 A 和 B, 但是其具体每一数位的进制还不确 定, 只知道 A 和 B 是同一进制规则, 且每一数位最高为 N 进制, 最低为二进 制。请你算出 A−B 的结果最小可能是多少。
请注意, 你需要保证 A 和 B 在 X 进制下都是合法的, 即每一数位上的数 字要小于其进制。
输入格式
第一行一个正整数 N, 含义如题面所述。
第二行一个正整数 Ma, 表示 X 进制数 A 的位数。
第三行 Ma 个用空格分开的整数, 表示 X 进制数 A 按从高位到低位顺序各 个数位上的数字在十进制下的表示。
第四行一个正整数 Mb, 表示 X 进制数 B 的位数。
第五行 Mb 个用空格分开的整数, 表示 X 进制数 B 按从高位到低位顺序各 个数位上的数字在十进制下的表示。
请注意, 输入中的所有数字都是十进制的。
输出格式
输出一行一个整数, 表示 X 进制数 A−B 的结果的最小可能值转换为十进 制后再模 1000000007 的结果。
样例输入
11 3 10 4 0 3 1 2 0样例输出
94样例说明
当进制为: 最低位 2 进制, 第二数位 5 进制, 第三数位 11 进制时, 减法 得到的差最小。此时 A 在十进制下是 108,B 在十进制下是 14 , 差值是 94。
思路：
X进制的理解
3 2 1 8 10 2 个位 1
十位 2 * 2
百位 3 * 10 * 2
规律：该位数字乘上前面所有进制数。
求X 进制数 A−B 的结果的最小可能值，就是令每一位的进制数最小，每一数位上的数字要小于其进制，所以第i位的进制k为：k = max(2, max(list_A[i], list_B[i])+1)
代码：
n = int(input())
Ma = int(input())
list_A = list(map(int, input().split()))
Mb = int(input())
list_B = list(map(int, input().split()))
r = 0 # A-B最小差res
p = 1
m = 1000000007
for i in range(len(list_A)-1, -1, -1):
k = max(2, max(list_A[i], list_B[i])+1) # 确定进制数k
# X进制转十进制
# X(321) -> (3*10*2 + 2*2 + 1 = 65)
r = (r + p * (list_A[i] - list_B[i])) % m # A - B
p = p * k % m # 这里取余%对结果没有影响，但可以尽快运行速度
print(r)题目二：扫雷
2021年省赛模拟题
题目描述
在一个 n 行 m 列的方格图上有一些位置有地雷，另外一些位置为空。
请为每个空位置标一个整数，表示周围八个相邻的方格中有多少个地雷。
输入描述
输入的第一行包含两个整数 n,m。
第 2 行到第 n+1 行每行包含 m 个整数，相邻整数之间用一个空格分隔。如果对应的整数为 0，表示这一格没有地雷。如果对应的整数为 1，表示这一格有地雷。
其中，1≤n,m≤100 分钟后还是在当天。
输出描述
输出 n 行，每行 m 个整数，相邻整数之间用空格分隔。
对于没有地雷的方格，输出这格周围的地雷数量。对于有地雷的方格，输出 9。
输入输出样例
示例 1
输入
3 4 0 1 0 0 1 0 1 0 0 0 1 0输出
2 9 2 1 9 4 9 2 1 3 9 2
思路：
创建一个统计地雷的列表vis。遍历整个图，如果碰到雷，就在标记数组把这个位置标为9，然后把这个位置相邻的八个位置+1 。题目规定有地雷标为“9”，由于不是雷的位置周围最多有八个雷，所以那些位置标记不会超过8 不会和9冲突。
代码：
n,m = map(int,input().split())
tu = [list(map(int,input().split())) for i in range(n)]#用来存地图
vis = [[0 for j in range(m)]for i in range(n)]# 标记数组：统计周围地雷
dir = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]#写一个方向数组
for i in range(n):#遍历整个tu
for j in range(m):
if tu[i][j]==1:#如果这个位置是有雷
vis[i][j]=9#就将标记数组标记为9
for x in dir:#然后对周围八个位置进行检查遍历
xi = i +x[0]
xj = j +x[1]
if 0<=xi<=n-1 and 0<=xj<=m-1:#筛选八个位置中不出界的位置
if vis[xi][xj]!=9:#如果这个位置不是9
vis[xi][xj]+=1#就将这个位置+1 表示周围有一个雷了
for i in range(n):#循环遍历输出
for j in range(m):
print(vis[i][j],end=' ')
print()题目三：李白打酒加强版
2022年C/C++省赛压轴题
问题描述
话说大诗人李白, 一生好饮。幸好他从不开车。
一天, 他提着酒显, 从家里出来, 酒显中有酒 2 斗。他边走边唱:
无事街上走，提显去打酒。 逢店加一倍, 遇花喝一斗。
这一路上, 他一共遇到店 N 次, 遇到花 M 次。已知最后一次遇到的是花, 他正好把酒喝光了。
请你计算李白这一路遇到店和花的顺序, 有多少种不同的可能?
注意: 显里没酒 ( 0 斗) 时遇店是合法的, 加倍后还是没酒; 但是没酒时遇 花是不合法的。
输入格式
第一行包含两个整数 N 和 M.
输出格式
输出一个整数表示答案。由于答案可能很大，输出模 1000000007 的结果.
样例输入
5 10样例输出
14样例说明
如果我们用 0 代表遇到花，1 代表遇到店，14 种顺序如下：
010101101000000
010110010010000
011000110010000
100010110010000
011001000110000
100011000110000
100100010110000
010110100000100
011001001000100
100011001000100
100100011000100
011010000010100
100100100010100
101000001010100
题目大意：
李白一开始有 2斗酒，他会经过 N次店，遇到M次花，每遇到一次花，他就会喝 1斗酒；每遇到 一次店 ，酒量会变成原来的2倍。最后一次他遇到花，喝完一斗洒后，酒正好是0斗。求满足条件的不同顺序的花和店的母其方案数
法一：暴力法：（排列）
N次店，M次花，总共N+M次，有（N+M)! 个排列，但N，M≤100，超时。。。
法二：递归
遇到店，store-1，wine*2
遇到花，flower-1，wine-1
结束条件：当店为0，花为1，酒为1时，方案数+1
代码1：（递归：40%）
N,M = map(int,input().split())
list=[]
def fun(store,flower,wine):
if store>0:
fun(store-1,flower,wine*2)
if flower>0:
fun(store,flower-1,wine-1)
if store==0 and flower==1 and wine==1:
list.append(1)
return list
fun(N,M,2)
print(len(list))法三： DP
dp[i][j][k]：经过 i个位置 ，中间遇到j次店，洒数为k斗的方案教
i的范围1~N+M，j的范围0~N，k的范围0~M （酒量k肯定不能超过M斗，因为只能遇到M次花，每次减一斗，且到最后要减为0）
遇到店的情况：j不为0（已经遇到过店） 且 k % 2 == 0（酒在遇到店后k必为偶数，因为酒在遇到店后翻倍了，才能保证遇到店之前k//2为整数）
状态转移方程：
① 到位置i遇到花/店：dp[i][j][k] = dp[i - 1][j][k + 1] + dp[i - 1][j - 1][k //2] 两种方案数相加
② 到位置i遇到花：dp[i][j][k] = dp[i - 1][j][k + 1]
最终的结果：dp[n+m-1][n][1] 前面走过了 n+m-1个位置，中间遇到了n个店，且此时有1斗洒，那么最后1个位置就肯定是花，且走完后酒恰好变为0斗 。
代码2：（DP：AC）
n, m = map(int, input().split())
MOD = int(1e9) + 7
dp = [[[0] * 110 for _ in range(110)] for i in range(210)]
dp[0][0][2] = 1 # 初始化DP
for i in range(1, n + m + 1):
for j in range(0, min(i + 1, n + 1)): # 遍历店，店不超过n个
for k in range(0, m + 1): # 酒量
if j and k % 2 == 0: # 已经遇到过店且酒是偶数：遇到店/花
dp[i][j][k] = (dp[i - 1][j][k + 1] + dp[i - 1][j - 1][k //2]) % MOD
else: # 其他情况下：遇到花
dp[i][j][k] = dp[i - 1][j][k + 1]
print(dp[n + m - 1][n][1])