建邺区住房 建设 网站,网站 f型,网站前台用什么开发,怎么样做外链推广网站#x1f381;2021第十二届蓝桥杯python组国赛真题 #x1f680; 真题练习#xff0c;冲刺国赛 #x1f680; 2021第十二届蓝桥杯python组国赛真题解析代码 博观而约取#xff0c;厚积而薄发 #x1f3c6;国赛真题目录 文章目录 #x1f381;2021第十二届蓝桥杯python组国…2021第十二届蓝桥杯python组国赛真题 真题练习冲刺国赛 2021第十二届蓝桥杯python组国赛真题解析代码 博观而约取厚积而薄发 国赛真题目录 文章目录 2021第十二届蓝桥杯python组国赛真题试题A.带宽⭐️1.题目2.思路分析3.代码实现 试题B.纯质数⭐️1.题目2.思路分析3.代码实现 试题C.完全日期⭐️1.题目2.思路分析3.代码实现 试题D.最小权值⭐️⭐️⭐️1.题目2.思路分析3.代码实现 试题E.大写⭐️1.题目2.思路分析3.代码实现 试题F.123⭐️⭐️⭐️1.题目2.思路分析3.代码实现 试题G.冰山⭐️⭐️⭐️⭐️⭐️⭐️1.题目2.思路分析3.代码实现 试题H.和与乘积⭐️⭐️⭐️⭐️1.题目2.思路分析3.代码实现 试题I.二进制问题⭐️⭐️⭐️⭐️1.题目2.思路分析3.代码实现 试题J.翻转括号序列⭐️⭐️⭐️⭐️⭐️1.题目2.思路分析3.代码实现 试题A.带宽⭐️
1.题目
带宽
2.思路分析
难度⭐️
标签单位换算
思路计算机常识
思路分析 本题考查的是简单的单位换算但需要对计算机知识有基本的了解 1. M B MB MB 与 M b Mb Mb M B MB MB 和 M b Mb Mb 是计算机中的储存单位即为数据大小可以简写为 M M M 和 m m m其中 M B MB MB 表示兆字节 B y t e Byte Byte M b Mb Mb 表示兆比特 b i t bit bit所以有换算公式 1 M B 8 M b 1MB8Mb 1MB8Mb 2. M B p s MBps MBps 与 M b p s Mbps Mbps M B p s MBps MBps 和 M b p s Mbps Mbps 表示的是速率用于反映下载速度或数据读写速度可以简写为 M B / s MB/s MB/s 和 M b / s Mb/s Mb/s其中 M B p s MBps MBps 表示兆字节每秒 M b p s Mbps Mbps 表示兆比特每秒则有换算公式 1 M B p s 8 M b p s 1MBps8Mbps 1MBps8Mbps 英文巧记 M B → M i l l i o n B y t e MB→Million\ Byte MB→Million Byte M b → M i l l i o n b i t Mb→Million\ bit Mb→Million bit M B p s → M i l l i o n B y t e p e r s e c o n d MBps→Million\ Byte\ per\ second MBps→Million Byte per second M b p s → M i l l i o n b i t p e r s e c o n d Mbps→Million\ bit\ per\ second Mbps→Million bit per second 3.代码实现
单位换算实现
print(200//8)
# 25输出结果 试题B.纯质数⭐️
1.题目
纯质数 2.思路分析
难度⭐️
标签素数筛
思路素数筛
思路分析
纯质数在素数条件的基础上还要满足每一个数位上的数都是质数
而个位为质数的数只有 p r i m e [ 2 , 3 , 5 , 7 ] prime[2,3,5,7] prime[2,3,5,7]
因此本质还是判断为素数之后再依次判断每一个数位上是否为素数而判断素数最快的方法就是 素数筛
step 素数筛对于任意一个素数它的正整数倍 ( ≥ 2 ) (≥2) (≥2)一定是合数 构造 v i s vis vis数组先初始化 v i s vis vis为 1 1 1 1 1 1为素数 0 0 0为合数遍历 2 → 20210605 2→20210605 2→20210605若当前的数 x x x为 v i s [ x ] 1 vis[x]1 vis[x]1未被标记且为素数对他进行处理 ①遍历 x x x的倍数 i 2 x , 3 x , . . . i2x,3x,... i2x,3x,... ②如果 i i i未被标记过防止合数重复标记如2的3倍为63的2倍也为6则统计的合数个数会增多则标记vis[i]0 ③进一步对该素数进行判断依次得到其数位上的每一个数如果均在数组 p r i m e [ 2 , 3 , 5 , 7 ] prime[2,3,5,7] prime[2,3,5,7]中则为纯质数cnt1 图解 3.代码实现
素数筛实现
from math import *def is_Prime(x): # 判定为素数for i in range(2,int(sqrt(x))1):if x%i0:return False # 合数return True # 素数def allPrime(x): # 判定为纯素数while x ! 0:a x % 10x x // 10if a not in prime:return False # 是素数但不是纯素数return Trueprime[2,3,5,7] # 个位的纯质数列表
vis[1]*(202106051)
cnt0
for num in range(2,202106051):if vis[num]1 and is_Prime(num): # 如果是素数for i in range(2,20210605//num1): # 素数的整数倍一定不是素数vis[i*num] 0 # 标记为合数if allPrime(num): # 每一位都是素数cnt1 # num为纯素数
print(cnt) #1903输出结果 试题C.完全日期⭐️
1.题目
完全日期 2.思路分析
难度⭐️
标签闰年的判断
思路模拟
思路分析 本题需要将所有的年月日都遍历一遍寻找完全平方数而遍历日期的难点就在于闰年中2月的判断 step 得到年月日之和 我们先设置一般年份中每月的天数 m [ 0 , 31 , 28 , 31 , 30 , 31 , 30 , 31 , 31 , 30 , 31 , 30 , 31 ] m[0,31,28,31,30,31,30,31,31,30,31,30,31] m[0,31,28,31,30,31,30,31,31,30,31,30,31] 闰年的判断 世纪闰年能被 400 400 400整除的 y e a r year year普通闰年能被 4 4 4整除但不能被 100 100 100整除的 y e a r year year 在判断年份之后如果为闰年则修改 m [ 2 ] 29 m[2]29 m[2]29在对该年的遍历结束之后再修改回 28 28 28 判断为完全平方数 对所求的sum可以通过if sumint(sqrt(sum))**2 进行判断因为 i n t ( s q r t ( s u m ) ) int(sqrt(sum)) int(sqrt(sum)) 得到的是对 s u m sum sum开方后得到的浮点数向下取整的结果如果 s u m sum sum不为完全平方数则结果应该为 sumint(sqrt(sum))**2 3.代码实现
模拟实现
from math import *def leapyear(y):# 1.世纪闰年能被400整除# 2.普通闰年能被4整除但不能被100整除if y%4000 or (y%100!0 and y%40):return Truereturn Falsedef get(x):res0while x!0:resx%10xx//10return resm[0,31,28,31,30,31,30,31,31,30,31,30,31] # 每月的天数 0位置不存
cnt0
for year in range(2001,2022):if leapyear(year): # 如果是闰年 修改2月的天数m[2]29for month in range(1,13):for day in range(1,m[month]1):sumget(year)get(month)get(day)if sumpow(int(sqrt(sum)),2):cnt1m[2]28 # 此轮循环结束 还原2月的天数
print(cnt) # 977输出结果 试题D.最小权值⭐️⭐️⭐️
1.题目
最小权值
2.思路分析
难度⭐️⭐️⭐️
标签 d p dp dp 动态规划
思路 d p dp dp 动态规划
思路分析 要求2021个结点时树的最小权值而权值是按照特定方式计算的我们无法直接得到因此可以由小规模问题逐渐递推到大规模问题—— d p dp dp 动态规划 step 确定 d p dp dp数组 首先要知道 d p dp dp 数组的状态由当前状态到下一个状态时状态变化的只有树的结点数由 i → i 1 i→i1 i→i1因此我们定义 d p [ i ] dp[i] dp[i]表示有 i i i 个结点时树的最小权值为 d p [ i ] dp[i] dp[i] 状态转移 由于树的权值与左、右子树的权值以及左、右子树的结点数均有关而又因为确定了一棵树的结点就确定了该结点下的最小权值 d p [ x ] dp[x] dp[x]所以我们该树左子树的结点数为 j j j则右子树的结点数为 i − j − 1 i-j-1 i−j−1 除去根节点则左子树的最小权值为 d p [ j ] dp[j] dp[j]右子树的最小权值为 d p [ i − j − 1 ] dp[i-j-1] dp[i−j−1] 暴力枚举每一种 j j j 的情况最后得到权值最小的解即为 d p [ i ] dp[i] dp[i] 状态转移方程为dp[i]min(dp[i],12*dp[j]3*dp[i-j-1](j**2)*(i-j-1) 最终结果 即为结点数为2021时的 d p [ 2021 ] dp[2021] dp[2021] 3.代码实现
模拟实现
dp[float(inf)]*2022 # dp[i]表示结点数为i的树的最小权值
dp[0]0
dp[1]1 # 只有一个结点时 权值为1
for i in range(2,2022): # i∈[2,2021]for j in range(1,i): # j表示结点数为i的树的左子树的结点个数 j∈[1,i-1]dp[i]min(dp[i],12*dp[j]3*dp[i-j-1](j**2)*(i-j-1)) # 遍历左子树的结点数 找到最小值
print(dp[2021]) # 2653631372输出结果 试题E.大写⭐️
1.题目
大写 2.思路分析
难度⭐️
标签 p y t h o n python python语法
思路① A S C I I ASCII ASCII码转化
思路分析
根据 A S C I I ASCII ASCII码我们知道 ′ A ′ 65 , ′ Z ′ 90 ′ a ′ 97 , ′ z ′ 122 A65,Z90a97,z122 ′A′65,′Z′90′a′97,′z′122因此
大写的 A S C I I ASCII ASCII码 32 32 32 小写字母的 A S C I I ASCII ASCII码
这里再补充两个 p y t h o n python python中的语法 ord(str):返回 s t r str str 对应的 A S C I I ASCII ASCII码chr(num):返回 A S C I I ASCII ASCII 码为 n u m num num的字符 思路②语法
思路分析
这里也有更为简单粗暴的方法
利用 p y t h o n python python中的函数str.upper()
如果为小写字母则将其转化为大写遇到其他字符则不变 补充对应大写转为小写的函数为str.lower() 3.代码实现
1. A S C I I ASCII ASCII实现
sinput()
res
for i in s:if ord(i)97 and ord(i)122: # 如果为小写achr(ord(i)-32)resresaelif ord(i)65 and ord(i)90:resielse:print(输入的不是字母)break
print(res)2.语法实现
print(input().upper())输出结果 试题F.123⭐️⭐️⭐️
1.题目
123
2.思路分析
难度⭐️⭐️⭐️
标签二分 思维
思路二分
思路分析 要求区间 [ L , R ] [L,R] [L,R] 中数的和如果每一轮都先求解前缀和数组那时间复杂度为 O ( T r ) O(Tr) O(Tr)肯定无法通过所有100%所以我们应该抓住题目所给数列的特殊性 我们先简单列举几项 我们对这些数按组进行分类其组内元素个数依次递增
对于该数列有如下性质 第 k k k 组数的和 前 k k k 组数的总个数: k ∗ ( k 1 ) 2 \frac{k*(k1)}{2} 2k∗(k1) 可以看到由于组号为 k k k 的数组是等于它的长度的且其中最大的元素 a k k a_kk akk所以每增加一个长度为 k k k 的数组 k k k 时改组数的变化范围为 1 → k 1→k 1→k则正好等于第一组到第k组元素的总个数即为在数组中的位置 前 k k k 组数的总和为: k ∗ ( k 1 ) ∗ ( k 2 ) 6 \frac{k*(k1)*(k2)}{6} 6k∗(k1)∗(k2) d e f def def由于 S n s u m 1 s u m 2 . . . s u m k S_nsum_1sum_2...sum_k Snsum1sum2...sumk而 s u m k k ∗ ( k 1 ) 2 sum_k\frac{k*(k1)}{2} sumk2k∗(k1) 因此可以将其拆分为 S n S n 1 S n 2 1 2 ∗ [ 1 2 2 2 . . . k 2 ] 1 2 ∗ [ 1 2 . . . k ] S_nS_{n1}S_{n2}\frac{1}{2}*[1^22^2...k^2]\ \frac{1}{2}*[12...k] SnSn1Sn221∗[1222...k2] 21∗[12...k] 根据公式 ∑ i 1 n n 2 n ∗ ( n 1 ) ∗ ( 2 n 1 ) 6 ∑_{i1}^{n}n^2\frac{n*(n1)*(2n1)}{6} ∑i1nn26n∗(n1)∗(2n1) ∑ i 1 n n n ∗ ( n 1 ) 2 ∑_{i1}^{n}n\frac{n*(n1)}{2} ∑i1nn2n∗(n1) 解得 S n k ∗ ( k 1 ) ∗ ( k 2 ) 6 S_n\frac{k*(k1)*(k2)}{6} Sn6k∗(k1)∗(k2) 回到正题根据上面两个性质我们现在最重要的就是确定 L , R L,R L,R 在数组 a a a中的位置也就是在第 x x x 组第 y y y 个因此我们定义 两个映射
①映射 f 1 f1 f1区间序号 k k k → → → 元素个数对应 a a a 数组中下标
若已知区间序号为 k k k则可以确定数组下标 i i i 的范围为 k ∗ ( k − 1 ) 2 i ≤ k ∗ ( k 1 ) 2 \frac{k*(k-1)}{2}i≤\frac{k*(k1)}{2} 2k∗(k−1)i≤2k∗(k1)
def getk(k): # 映射1区间序号k-元素个数return k*(k1)//2 # k表示第k个区间返回结果为前k个区间所含元素的个数②映射 f 2 f2 f2区间序号 k k k → → → 前缀和
若已知区间序号为 k k k则可以确定下标元素 a [ i ] a[i] a[i] 的 s u m [ x ] sum[x] sum[x] 满足 k ∗ ( k − 1 ) ∗ ( k 1 ) 6 s u m [ i ] ≤ k ∗ ( k 1 ) ∗ ( k 2 ) 6 \frac{k*(k-1)*(k1)}{6}sum[i]≤\frac{k*(k1)*(k2)}{6} 6k∗(k−1)∗(k1)sum[i]≤6k∗(k1)∗(k2)
def getsum(k): # 映射2区间序号k-前缀和return k*(k1)*(k2)//6 # 表示前k个区间的元素总和于是我们再结合二分查找先找到 L , R L,R L,R 的具体位置再根据映射 f 2 f2 f2将位置 k k k映射为前缀和就可以得到区间 [ L , R ] [L,R] [L,R] 的和了 step 确定下标 x x x 所在的数组区间 k k k 如要找下标为 5 的元素所在的区间我们对区间 k k k 进行二分查找 如此时 mid3我们将区间为 k 3 k3 k3 时映射到元素个数getk(k)6表示区间为3时对应的数组下标最多为 6返回函数值 6 5 65 65r3继续二分过程结束时 lr3则可以确定下标为 5 的元素在区间为 3 的数列中 最后用下标 5 − g e t k ( k − 1 ) 5-getk(k-1) 5−getk(k−1) 即得到该元素在区间 k 的数列中的位序 求解前缀和 确定了 L , R L,R L,R 的位置后则可以求得 [ L , R ] [L,R] [L,R] 的区间和了 假设 L L L 所在区间为 l k lk lk R R R 所在区间为 r k rk rk 由图可知sum[rk]-sum[lk-1] 为蓝色 红色部分的长度但是实际上蓝色部分并不在区间 [ L , R ] [L,R] [L,R] 内所以还要根据位置关系减去这两部分但为了方便计算这里选择的是用 s u m [ r k − 1 ] − s u m [ l k − 1 ] sum[rk-1]-sum[lk-1] sum[rk−1]−sum[lk−1] − - − 左边蓝色部分 黄色部分 3.代码实现
二分 前缀和实现
def getk(k): # 映射1区间序号k-元素个数return k*(k1)//2 # k表示第k个区间返回结果为前k个区间所含元素的个数def getsum(k): # 映射2区间序号k-前缀和return k*(k1)*(k2)//6 # 表示前k个区间的元素总和def position(x):l,r1,int(2e6) # 二分区间while lr:mid(lr)1if getk(mid)x: # getk相当于k的一个映射映射组数-元素个数lmid1else:rmidreturn l,x-getk(l-1) # x在第l组中的第x-getk(l-1)个def solve(l,r):lk,pos_lposition(l) # 确定l的具体位置rk,pos_rposition(r) # 确定r的具体位置sumgetsum(rk-1)-getsum(lk-1)-getk(pos_l-1)getk(pos_r) # 画图模拟一下return sumTint(input())
for _ in range(T):l,rmap(int,input().split())print(solve(l,r))输出结果 试题G.冰山⭐️⭐️⭐️⭐️⭐️⭐️
1.题目
冰山 2.思路分析
难度⭐️⭐️⭐️⭐️⭐️⭐️
标签 F H Q − t r e a p FHQ-treap FHQ−treap
思路①双字典
思路分析 本题难点就是每一天都要对冰山的体积进行整体修改区间修改可能会想到线段树但是这里要不断修改线段树的值十分繁琐 算法思路由于是整体修改我们则可以对体积相同的冰山归为一类进行操作所以不难想到构造两个字典 a , b a,b a,b只需记录{冰山的体积对应的冰山数量} a a a 用于表示这一天开始时的冰山状态 b b b 用于表示这一天结束时的冰山状态 step 字典操作 g e t ( k e y , 0 ) get(key,0) get(key,0) 对于体积 v v v 的冰山假设有 c n t cnt cnt 个我们可以通过a[v]a.get(v,0)cnt实现键值对的更新操作其等价于先判断是否存在键值对v如果存在则将其值 c n t cnt cnt如果不存在则先构造一个键 v v v再将其值 c n t cnt cnt 对冰山的体积进行分类判断 ①变化后体积 v i x i k vixik vixik则这些冰山之后分解为 a [ v i x i ] a[vixi] a[vixi] 个体积为 k k k 的冰山和 v i x i − k ∗ a [ v i x i ] vixi-k* a[vixi] vixi−k∗a[vixi] 该冰山数量 x 一个这样的冰山分解为体积为1的冰山的个数个体积为 1 1 1 的冰山放入空字典 b b b中 ②变化后体积 1 v i x i ≤ k 1vixi≤k 1vixi≤k 这些冰山既不会分解也不会消失则直接修改键为 vixi而对应的值不变放入空字典 b b b中 ③变化后体积 v i x i ≤ 0 vixi≤0 vixi≤0 冰山消失跳过此轮不放入 b b b 中 如果飘来的冰山体积 y!0则对应的字典中的键b[y]1 把原本的 a a a字典清空将 b b b 赋值给 a a a对 a a a中的键值对遍历求和即可 注意: 这里的 g e t n u m getnum getnum 函数用于求字典 a a a 中该键 k e y key key对应的值如果存在该键则 a[key]否则 0 思路② F H Q − t r e a p FHQ-treap FHQ−treap
思路分析 暂时没有写出来… 3.代码实现
双字典实现通过 70 %
def getnum(x): # 判断a中有没有这个键值对if x in a.keys():return a[x]else:return 0n,m,kmap(int,input().split())
llist(map(int,input().split()))
a{} # 定义字典{体积对应的冰山个数}
for i in l:a[i]a.get(i,0)1for _ in range(m):x,ymap(int,input().split())b{} # 辅助字典for i in a.keys(): # 取出键if ixk:b[1]b.get(1,0)(ix-k)*getnum(i) # 分解后体积为1的冰山b[k]b.get(k,0)getnum(i)elif ix0:b[ix]b.get(ix,0)getnum(i) # 当前体积为ix的冰山数量加上原本体积为i的冰山数量else: # 修改后消失的冰山 略过continueif y!0:b[y]b.get(y,0)1 # 加上体积为y的冰山a.clear()absum0for v,cnt in a.items():sum(v*cnt)%998244353print(sum%998244353)输出结果 试题H.和与乘积⭐️⭐️⭐️⭐️
1.题目
和与乘积 2.思路分析
难度⭐️⭐️⭐️⭐️
标签二分 前缀和 思维
思路二分查找前缀和
思路分析 首先要确定这道题的模型对于求某一个区间的和与乘积我们首先可以想到用前缀和数组但是题目要求的是所有满足条件的区间而非单独查询某一个区间所以就算构造出了前缀和数组还是需要用两层循环暴力地遍历每一个区间双指针进行判断结果肯定是超时那么我们就必须 另辟蹊径——利用本题最为特殊的 1 1 1 step
1. 思维 问题规模分析如果一个合法区间内大于 1 1 1 的数的个数为 t o t a l total total则有 t o t a l 40 total40 total40 d e f def def假设合法区间为 [ l , r ] [l,r] [l,r]在其中含有 t o t a l total total 个大于 1 1 1的数则有 r − l 1 − t o t a l r-l1-total r−l1−total 个数等于 1 1 1由于 1 1 1对于乘积的结果没有贡献所以乘积结果 m u l t i p l y 2 t o t a l multiply2^{total} multiply2total 因为这 t o t a l total total 个数 ≥ 2 ≥2 ≥2又根据区间长度 n ≤ 2 n≤2 n≤2 x 1 0 5 10^5 105元素值 a i ≤ 2 a_i≤2 ai≤2 x 1 0 5 10^5 105则最大区间和 最大区间长度 x 最大元素值 : : : s u m 4 sum4 sum4 x 1 0 10 10^{10} 1010而 4 4 4 x 1 0 10 2 40 10^{10}2^{40} 1010240 所以要使 m u l t i p l y s u m multiplysum multiplysum t o t a l total total 一定小于 40 40 40 推论换句话说当区间乘积 m u l t i p l y ≥ 4 multiply≥4 multiply≥4 x 1 0 10 10^{10} 1010 时一定不可能是合法区间 有了这个推论我们便可以利用它在遍历时进行 剪枝 2. 特殊的 ′ 1 ′ 1 ′1′ 本题中数组内的 ‘1’ 是操作性最强的地方因为 ‘1’ 不会影响某一个区间的乘积而只会影响到某一区间的和 所以对于乘积来说我们只需要着眼于 1 1 1 的数即可因此在暴力搜索区间 [ l , r ] [l,r] [l,r] 时我们可以遍历 r l a n d r 1 rl\ and\ r1 rl and r1 的数作为区间的右边界再进一步对覆盖区间内的 ′ 1 ′ 1 ′1′ 判断即可这样便减小了时间复杂度 算法具体实现
以数组 a [ 1 , 2 , 4 , 1 , 1 , 3 , 1 ] a[1,2,4,1,1,3,1] a[1,2,4,1,1,3,1] 为例 求解前缀和数组 s u m sum sum 我们选择舍弃下标为 0 0 0 的位置不存 找到所有 1 1 1 的数的位置 用 i n d e x index index 数组储存大于 1 1 1 的数的位置利于快速确定区间右边界 在找到大于 1 1 1的数后我们定义映射 f f f a → i n d e x a→index a→index之后若要访问 a a a 中大于 1 1 1 的数只需对 i n d e x index index数组中的下标 j j j进行映射a[index[j]] 即可 找到每一个 1 1 1 的数后连续的 ′ 1 ′ 1 ′1′的个数: 对于 a a a中下标为 i i i 的数 n u m num num_ 1 [ i ] 1[i] 1[i] 表示 a [ i ] a[i] a[i] 后面连续的 ‘1’ 的个数 二分搜索 →得到位序大于当前左区间 i i i 且 值大于1的最小位置 R: 我们在固定了左区间 i i i 后就需要找到一个 R R R使得 Ri and a[R]1也就是说我们要在所求得的 i n d e x index index数组中寻找这样的 R R R使区间为 [ i , R ] [i,R] [i,R] 为了降低时间复杂度我们选择对 i n d e x index index数组进行二分查找搜索 这里二分要注意一个问题我们要找的不是 i i i而是比 i i i大的数所以应该是返回比 i i i 大的位置 假设此时 i 3 i3 i3也就是左区间为 a [ 3 ] 4 a[3]4 a[3]4 ①定义l0,rtotal因为如果让rtotal-1则得到的不是 i i i的后继 此时mid1index[mid]i也就是将 m i d mid mid 映射到数组 a a a 中其下标为 i i i但是因为我们要找的不是 i i i而是大于 i i i 的数所以移动左指针lmid1 ②移动后index[mid]i则移动右指针rmid ③最后lr则结束二分查找所求的 R R R 即为 i n d e x [ r ] index[r] index[r] (映射) 遍历区间 在二分搜索后我们得到了区间 [ l , R ] [l,R] [l,R]其中 l ∈ [ 1 , n ] l∈[1,n] l∈[1,n] R R R 为大于 1 1 1的数 a [ R ] a[R] a[R]我们对其合法性进行判断 ①剪枝如果在遍历过程中发现multiplyINF4x10^{10}则直接结束遍历遍历下一个左区间值由推论 这里剪枝很重要加上可以通过60%的案例但这也是基于推论得来的 ②若此时区间内的 s u m m u l t i p l y summultiply summultiply则因为 R R R 到下一个大于1的数中间均为1导致在这个区间上乘积将无法等于和所以继续对下一个满足条件的右区间的搜索 图解 此时 s u m sum sum 的值已经大于 m u l t i p l y multiply multiply 了就算加上右区间之后连续的 ′ 1 ′ 1 ′1′也无法改变乘积值所以此时只有遍历下一个满足条件的右区间才有可能使其相等 ③若此时区间内的 s u m m u l t i p l y s u m n u m summultiplysumnum summultiplysumnum_ 1 [ R ] 1[R] 1[R]则表明可以通过一定范围内右边界的延伸实现和与乘积相等则数量 1 1 1 图解 3.代码实现
二分 前缀和 思维 剪枝实现
def getsum(l,r): # 求l,r区间的前缀和return sum[r]-sum[l-1]INF 40000000000
nint(input())
a[0]list(map(int,input().split())) # 第一个不存
sum[0]*(n1) # 前缀和
index[] # 数组中1的数的索引
total0 # 记录1的数的个数
num_1[0]*(n1) # 数组中1的数之后连续1的个数# 1.前缀和得到1的数的索引
for i in range(1,n1):sum[i]sum[i-1]a[i]if a[i]1:index.append(i)total1# 2.得到数组中1的数之后连续1的个数
cnt0
for i in range(n,0,-1): # 从后向前遍历if a[i]1:cnt1else:num_1[i]cnt # 记录a[i]之后连续1的个数cnt0 # cnt清零# 3.找到合法区间
res0
for i in range(1,n1): # 固定左区间为 ires1 # 每一个数都是一个合法区间multiplya[i] # 表示乘积l,r0,total # 查找i之后第一个大于1的数的位置即对1的数组进行二分while lr:mid(lr)1if index[mid]i: # 这里一定是 因为要找在它之后的rmidelse:lmid1jr # j表示后一个位置while jtotal: # 以index数组中之后的值index[j]依次作为右区间Rindex[j] # 映射index-amultiply*a[R] # 由于[i,R]区间内的其他数均为1所以不影响乘积if multiplyINF:breakif getsum(i,R)multiplygetsum(i,R)num_1[R]:res1j1
print(res)输出结果 试题I.二进制问题⭐️⭐️⭐️⭐️
1.题目
二进制问题 2.思路分析
难度⭐️⭐️⭐️⭐️
标签数位 d p dp dp
思路数位 d p dp dp d f s dfs dfs
思路分析 这里很容易想到将 N N N拆分为二进制数要满足二进制位上有 k k k个 1 1 1即区间内满足某一条件的数是多少用数位 d p dp dp求解 数位 d p dp dp 即是对每一位上的数进行操作其常与 递归 ( d f s ) (dfs) (dfs) 结合因为在递归中每次进行的操作都是一样的刚好满足数位 d p dp dp的要求
接下来我们详细讲一下数位 d p dp dp下 d f s dfs dfs的模板 step 首先对于每一个数位而言我们要 确定其数的取值范围 假设我们要求比 N 12345 小且满足某一条件的数的个数那么对于最高位而言我们可以选择 [ 0 , 1 ] [0,1] [0,1]因为如果选择的数字大于该位置上的数如有2xxxx12345则后面不论取多少这个数一定比 N N N大已经不满足条件对于第 2 2 2位上的数而言我们就需要进行讨论了 ①最高位上为1则第2位置上只能选择 [ 0 , 2 ] [0,2] [0,2]因为最高位已经抵满若第二位置上取 3 3 3则有 13xxx12345一定不满足小于 N N N ②最高位上为0则第2位置上可以选择 [ 0 , 9 ] [0,9] [0,9]为什么呢因为比第二位置级别更高的位置上比 N N N 在该位置上的数小所以之后的位数上任意怎么取都一定比 N N N小123450xxxx 其实这就是高位置数上的数对数的大小更能起决定性作用我们受此启发便可以得到如下结论 (1) 如果x前面某一位已经小于对应位置上的上限数字即 N N N在该位置上的数字则这一位以及之后的每一位上都可以填入 [0,进位数-1] 如十进制进位数为10二进制进位数为2 (2) 如果x前面的每一位都等于对应位置上的上限数字则这一位上的数的取值范围为 [0,该位置上的上限数] 数位 d p dp dp 与 d f s dfs dfs 因此我们可以通过 d f s dfs dfs得到所有满足条件的情况数: 定义一个函数: dfs(pos,pre,flag) p o s pos pos表示当前访问的数的位数 p r e pre pre表示 p o s pos pos之前数位上数的状态如在本题中可以记录 p o s pos pos前有多少个 1 1 1 f l a g flag flag代表是否前面每一位上的数都和对应位置的上限数相同 于是我们对 N N N由高位向低位进行 d f s dfs dfs深搜 以本题为例假设数字 N 7 111 ( 2 ) N7111(2) N7111(2) k 2 k2 k2 每次如果选择 1 1 1则pre1选择 0 0 0则pre不加又因为 111 111 111的上限数字均为 1 1 1所以某一位上选了0后之后的每一位都可以任选 1 / 0 1/0 1/0 f l a g flag flag 标记为 0 0 0 p o s pos pos的值则逐层递减由此我们可以得到如下的递归二叉树 其中满足条件时pos0 and prek 记忆化搜索 而 d f s dfs dfs必然少不了 剪枝 操作因为在递归时会存在一些重复操作导致效率降低如图所示我们不难发现这两棵子树完全一样但我们进行了多次计算所以这也就是数位 d p dp dp与 d f s dfs dfs结合的关键——记忆化搜索 我们还原它的状态为 01x 和 10x (x为待定系数)而这两个状态都有一个共同特点那就是 flag0由于前面两个位置上的数并不全是上限数字所以导致第三位置上的数可以任选之后的位置也可以也就是 x x x 的情况数是已知的如已经记录了状态 01x 要满足条件有 011 1 1 1 种情况则 10x 要满足条件直接可以判断也只有 1 1 1 种情况 101 所以如果对该状态 ( p o s , p r e , f l a g ) (pos,pre,flag) (pos,pre,flag)进行过记录之后再遇到该状态时我们就可以直接在当前递归层返回结果而不需要递归到叶子结点上 那么为什么一定要是 f l a g 0 flag0 flag0 的时候才要更新 d p dp dp 数组呢 其实很简单如果 flag1则该状态一定是唯一的比如 111xxx难道还能找出flag1又有前三位数与它状态相同的数吗flag1就已经说明它之前位置上的数都是上限数状态是确定的但如果是flag0就意味着之后位置上的数可以任选了而不用在意之前位置上的数具体是多少反正肯定不全是上限数字如 1110xxx 和 0011xxx1110也好0011也罢反正都不全是 1 1 1于是后三位 xxx 就可以任选那么这三位选择的方案个数就是确定的啦所以用 d p dp dp数组记录 如何实现上述记忆化搜索过程呢 d p dp dp 数组 我们定义 d p dp dp数组 d p [ p o s ] [ p r e ] x dp[pos][pre]x dp[pos][pre]x表示在当前数位为 p o s pos pos且前面已经有 p r e pre pre个 1 1 1时之后 p o s pos pos位能实现满足条件的选择为 x x x 种 举个例子就懂了 ①dp[1][1]1表示当前数位为1前面已经有1个1了那么要满足条件之后1位有1种选择可以使该数满足条件如 10x当前在pos1也就是对应 x x x那么你这时候只要一种选择就是x1才能使 prek2记忆化为1 ②dp[1][0]0表示当前数位为1前面已经有0个1了若要满足条件之后1位有0种选择可以使pre2如 00x则不可能满足条件记忆化为0 所以如果当前 flag0我们就更新此状态下的 d p dp dp 数组实现记忆化 3.代码实现
数位 d p dp dp d f s dfs dfs实现
import sys
sys.setrecursionlimit(1000000) # 设置递归深度 10^6def dfs(pos,pre,flag):global dpif prek:return 0if pos0: # 递归结束return 1 if prek else 0 # 如果1的个数等于k 则1种情况否则返回0if flag0 and dp[pos][pre]!-1: # 如果该状态被记录过 (剪枝)return dp[pos][pre]max_numnum[pos] if flag else 1 # 得到pos位可选的最大数res0for i in range(0,max_num1):resdfs(pos-1,prei,flag and inum[pos]) # 如果当前flag1 并且下一位选择上限数 flag才继续# 1if flag0:dp[pos][pre]res # 记录状态return resn,kmap(int,input().split())
num[-1] # 1.用于存放二进制数 2.从低位到高位存 3.首位置不存 以保持位数与下标对齐
while n:num.append(n1)nn1
poslen(num)-1 # n的二进制位数
# 1.bin(n)[2:]可以知道n最多有60位 2.K最大为50
dp[[-1]*51 for _ in range(62)]
print(dfs(pos,0,1))输出结果 试题J.翻转括号序列⭐️⭐️⭐️⭐️⭐️
1.题目
翻转括号序列 2.思路分析
难度⭐️⭐️⭐️⭐️⭐️
标签线段树
思路线段树
思路分析 这道题用暴力解的…线段树没想出来 step 首先构造前缀和数组 s u m sum sum 将 ′ ( ′ ( ′(′ 视为 1 1 1 ′ ) ′ ) ′)′ 视为 − 1 -1 −1 对于区间的查询 由于满足条件的区间 [ L , R ] [L,R] [L,R]的要求为 ① s u m [ R ] s u m [ L − 1 ] sum[R]sum[L-1] sum[R]sum[L−1] ② ∀ i ∈ [ L , R ] ∀i∈[L,R] ∀i∈[L,R]有 s u m [ i ] − s u m [ L − 1 ] ≥ 0 sum[i]-sum[L-1]≥0 sum[i]−sum[L−1]≥0 所以我们找到最长的且满足区间 [ L , R ] [L,R] [L,R]内的前缀和不小于 s u m [ L − 1 ] sum[L-1] sum[L−1]的 R R R使sum[R]sum[L-1]即可 对于区间的翻转 翻转对于数字来说就是取相反数这里采取的是暴力的方法修改区间上的数 实际上如果用线段树操作我们可以用以下方法更快捷地对区间 [ L , R ] [L,R] [L,R]进行翻转 翻转区间 [ L , R ] [L,R] [L,R] 先翻转 [ 1 , L − 1 ] [1,L-1] [1,L−1]再翻转 [ 1 , R ] [1,R] [1,R]
为什么要让翻转区间覆盖到 1 1 1呢
由于前缀和数组是从 1 1 1 开始不断求和的所以如果左区间为 1 1 1那么修改区间 [ 1 , x ] [1,x] [1,x]相当于让 [ 1 , x ] [1,x] [1,x] 的 s u m [ i ] sum[i] sum[i] 数组全部变为相反数sum[i]-sum[i]而对于 [ x 1 , n ] [x1,n] [x1,n]的部分假设翻转前sum[x]a翻转之后sum[x]-a由于对后面的前缀和造成影响的就是 s u m [ x ] sum[x] sum[x]而 s u m [ x ] sum[x] sum[x] 变化了 2 s u m [ x ] − 2 a 2sum[x]-2a 2sum[x]−2a所以对 [ x 1 , n ] [x1,n] [x1,n] 的 s u m [ i ] sum[i] sum[i] 数组全部变为sum[i]2sum[x] 即可 以 ( ( ( ) ) ( ) (\ (\ (\ )\ )\ (\ ) ( ( ( ) ) ( )为例若要翻转区间 [ 3 , 5 ] [3,5] [3,5] 则可以等效为修改区间 [ 1 , 2 ] [1,2] [1,2] 和区间 [ 1 , 5 ] [1,5] [1,5] 3.代码实现
暴力法实现50%
def query(L):res0for i in range(L,n1): # 暴力遍历if sum[i]-sum[L-1]0: # 条件1任意的sum[i]都要满足大于sum[L-1]if sum[i]sum[L-1]: # 条件2sum[i]sum[L-1]且i最大resmax(i,res)else: # 若小于0了说明右括号多直接退出breakreturn resdef update(L,R):for i in range(L,n1):if iR:a[i]-a[i]sum[i]sum[i-1]a[i]n,mmap(int,input().split())
sinput()
a[0]
for i in s:if i(:a.append(1)elif i):a.append(-1)sum[0]*(n1)
for i in range(1,n1):sum[i]sum[i-1]a[i]ans[]
for _ in range(m):wlist(map(int,input().split()))if len(w)2: # 查询最长序列Lw[1]Rquery(L)ans.append(R)elif len(w)3: # 翻转括号L,Rw[1],w[2]update(L,R)for k in ans:print(k)输出结果 希望备战蓝桥杯的小伙伴们都能有所收获觉得有帮助的话就赏个三连吧~ 如有错误欢迎指正~
