蓝桥杯第22天（Python）（疯狂刷题第5天）

题型：

1.思维题/杂题：数学公式，分析题意，找规律

2.BFS/DFS：广搜（递归实现），深搜（deque实现）

3.简单数论：模，素数（只需要判断到 int（sqrt（n））+1），gcd，lcm，快速幂（位运算移位操作），大数分解（分解为质数的乘积）

4.简单图论：最短路（一对多（Dijstra，临接表，矩阵实现），多对多（Floyd，矩阵实现）），最小生成树（并查集实现）

5.简单字符串处理：最好转为列表操作

6.DP：线性DP，最长公共子序列，0/1背包问题，最长连续字符串，最大递增子串

7.基本算法：二分，贪心，组合，排列，前缀和，差分

8.基本数据结构：队列，集合，字典，字符串，列表，栈，树

9.常用模块：math，datetime，sys中的设置最大递归深度（sys.setrecursionlimit(3000000)），collections.deque（队列），itertools.combinations（list,n）（组合），itertools.permutations（list,n）（排列）  heapq（小顶堆）

目录

1.裁纸刀（思维）

2.寻找整数

3.《质因数个数》真题练习（大数分解）

 4.《矩形拼接》真题练习（枚举遍历）

5.《消除游戏》（暴力循环）​编辑

6.重新排序（差分数组，贪心）

7.《全排列的价值》真题练习（数学定理，思维）

 8. 《最长不下降子序列》真题练习（DP）

 9.《最优清零方案》真题练习（暴力，线段树）

 10.《数的拆分》真题练习

---

1.裁纸刀（思维）

 裁的次数是一定的！找规律打印输出即可。

2.寻找整数

import sys  #设置递归深度
import collections  #队列
import itertools  # 排列组合
import heapq  #小顶堆
import math
sys.setrecursionlimit(300000)
import functools   # 自定义比较函数  -1不变，1交换def lcm(x,y):return x//math.gcd(x,y)*yx=3
step=1b=[0,0,1,2,1,4,5,4,1,2,9,0,5,10,11,14,9,0,11,18,9,11,11,15,17,9,23,20,25,16,29,27,25,11,17,4,29,22,37,23,9,1,11,11,33,29,15,5,41,46]'''
3 5 7 8 9 11 13 15 17 19 21 23 25 27      2递增
5 8 11 14 17 20 23 26 29 32     3递增筛选    5 11 17 23  
5 9 13 17 21 25 29 33     4递增    5 17 29'''for i in range(2,50):  # 类似埃式筛法while x %i !=b[i]:   x+=stepstep=lcm(step,i)  # 更新步长
print(x)

 暴力遍历或者找规律，根据前面几个找规律

3.《质因数个数》真题练习（大数分解）

标程：
 

n = int(input())
ans = 0
#从2开始进行质因子分解
i = 2
while i * i <= n:if n % i == 0:ans += 1while n % i == 0:n //= ii += 1
if n != 1:ans += 1
print(ans)

from random import randint
from math import gcddef witness(a, n):u = n - 1t = 0while u % 2 == 0:u = u // 2t += 1x1 = pow(a, u, n)for i in range(1, t + 1):x2 = x1 * x1 % nif x2 == 1 and x1 != 1 and x1 != n - 1:return Truex1 = x2if x1 != 1:return Truereturn False#miller_rabin素性测试 对数字n进行s次测试
def miller_rabin(n, s = 5):if n < 2:return Falseif n == 2:return Trueif n % 2 == 0:return Falsefor i in range(s):a = randint(1, n - 1)if witness(a, n):return Falsereturn True#返回一个因子，不一定是素因子
def pollard_rho(n):i, k = 1, 2c = randint(1, n - 1)x = randint(0, n - 1)y = xwhile True:i += 1x = (x * x + c) % nd = gcd(abs(x - y), n)if d != 1 and d != n:return dif y == x:return nif i == k:y = xk = k * 2factor = []
#找所有的素因子
def findfac(n):if miller_rabin(n):factor.append(n)returnp = nwhile p >= n:p = pollard_rho(p)findfac(p)findfac(n // p)n = int(input())
findfac(n)
print(len(set(factor)))

 4.《矩形拼接》真题练习（枚举遍历）

 

 依次考虑4条边，6条边，8条边对应的情况，枚举遍历

标程：

T = int(input())
while T != 0:T -= 1a = list(map(int, input().split()))a = [[a[0],a[1]], [a[2],a[3]], [a[4],a[5]]]ans = 8#枚举第一个矩形下标为i，第二个矩形下标为j，第三个矩形下标为kfor i in range(3):for j in range(3):for k in range(3):if i == j or i == k or j == k:continue#枚举三个矩形的两条边for ii in range(2):for jj in range(2):for kk in range(2):if a[i][ii] == a[j][jj]:ans = min(ans, 6)if a[i][ii] == a[k][kk]:ans = min(ans, 4)if a[i][ii] == a[j][jj] + a[k][kk]:ans = min(ans, 6)if a[j][1 - jj] == a[k][1 - kk]:ans = min(ans, 4)print(ans)

5.《消除游戏》（暴力循环）

暴力循环 ，扫一轮，看哪些是边缘字符，记录下标，完成扫描后删除，完成后继续循环遍历，退出条件：当前字符为空或者循环一次后长度不变。

标程：

s = list(input())
last_length = 0while True:length = len(s)#如果长度等于0，终止if length == 0:print("EMPTY")break#如果长度未发生变化，终止if length == last_length:print("".join(s))breakvis = [0] * length#根据题意找出边缘字符for i in range(length):if (i - 1) >= 0 and (i + 1) < length and s[i] == s[i - 1] and s[i] != s[i + 1]:vis[i] = vis[i + 1] = 1if (i - 1) >= 0 and (i + 1) < length and s[i] != s[i - 1] and s[i] == s[i + 1]:vis[i] = vis[i - 1] = 1#将边缘字符去除tmp_s = []for i in range(length):if vis[i] == 0:tmp_s.append(s[i])s = tmp_slast_length = length

6.重新排序（差分数组，贪心）

 初步想法：将重新查询的区间进行记录，看是否有交集，将交集区间替换为最大值

差分数组

 正解：读取区间，标记区间访问次数（通过差分数组实现），然后根据贪心思想，将大的值放到访问次数最多的位置。

标程：

import sys  #设置递归深度
import collections  #队列
import itertools  # 排列组合
import heapq  #小顶堆
import math
sys.setrecursionlimit(300000)
import functools   # 自定义比较函数  -1不变，1交换# 总体思路：查询最多的那一个放最大值，不需要序号，只需要记录最大次数
n = int(input())
a = list(map(int,input().split()))
a=[0]+a
b=[0]*(n+10)
s=[0]*(n+1)m=int(input())
for i in range(m):# 差分数组实现区间加法更新l,r = map(int,input().split())b[l]+=1b[r+1]-=1#对差分数组前缀和，得到每个数字的查询次数
for i in range(1,n+1):s[i]=s[i-1]+b[i]# sum1为原始和，sum2为贪心后的最大值
sum1,sum2=0,0
for i in range(1,n+1):sum1+=a[i]*s[i]# 贪心思想，大对大，小对小
a.sort()
s.sort()# 计算重新排序后的
for i in range(1,n+1):sum2+=a[i]*s[i]
print(sum2-sum1)

7.《全排列的价值》真题练习（数学定理，思维）

初步想法：找规律？没得规律就把全排列列出来，循环暴力，能拿多少分那多少分。

 找规律，蒙对20%数据

import sys  #设置递归深度
import collections  #队列
import itertools  # 排列组合
import heapq  #小顶堆
import math
sys.setrecursionlimit(300000)
import functools   # 自定义比较函数  -1不变，1交换#4 0+1*3+2*3+3*3+4*3+5*3+6
#3 0+1+1+2+2+3
#2 0+1ans=0
n = int(input())
for i in range(1,n*(n-1)//2):ans+=(n-1)*i%998244353
print((ans+n*(n-1)//2)%998244353)

 正解：顺序数和逆序数总和为 n*(n-1)//2   ，顺序数和逆序数想等，n个数公有n！个全排列，即顺序和逆序之和为n!*n*(n-1)//2，所以价值之和为上式除以2。

标程：

mod = 998244353
n = int(input())
ans = n * (n - 1) // 2 % mod
for i in range(3, n + 1):ans = ans * i % mod
print(ans)

 8. 《最长不下降子序列》真题练习（DP）

初步想法：通过DP算法，即最长递增子序列模板来做，记录最长子序列的下标，通过DP数组来找遍历，从后往前，看是否有元素小于最长子序列同时区间大于K的，有的话直接+k？

应该有问题，这种思路有问题！！不能过全部数据，考虑不全。

正解：思路类似，通过DP最长递增模板，但是需要用线段树模板维护，这题不要全分，跳了。

 9.《最优清零方案》真题练习（暴力，线段树）

 初步想法：先选择操作2，在操作1，暴力循环就可以了

 正解：思路相同，但是我的想法不能过全部数据，需要用线段树来处理，线段树没学。

maxn = 1000000 + 10
tree_mi = [0] * (maxn * 4)
tree_add = [0] * (maxn * 4)n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
a = [0, *a]#线段树模板
#利用左右儿子信息更新节点o
def push_up(o):tree_mi[o] = min(tree_mi[o << 1], tree_mi[o << 1 | 1])#利用节点o的lazy标记add更新左右儿子
def push_down(o):if tree_add[o] != 0:tree_add[o << 1] += tree_add[o]tree_mi[o << 1] += tree_add[o]tree_add[o << 1 | 1] += tree_add[o]tree_mi[o << 1 | 1] += tree_add[o]tree_add[o] = 0#建树
def build(o, l, r):tree_add[o] = 0if l == r:tree_mi[o] = a[l]returnmid = (l + r) >> 1build(o << 1, l, mid)build(o << 1 | 1, mid + 1, r)push_up(o)#查询区间[L,R]的最小值
def query(o, l, r, L, R):if L <= l and r <= R:return tree_mi[o]push_down(o);mid = (l + r) >> 1ans = 1000000000;if L <= mid:ans = min(ans, query(o << 1, l, mid, L, R))if R > mid:ans = min(ans, query(o << 1 | 1, mid + 1, r, L, R))return ans#区间更新[L,R]统一加上val
def update(o, l, r, L, R, val):if L <= l and r <= R:tree_mi[o] += valtree_add[o] += valreturnpush_down(o);mid = (l + r) >> 1if L <= mid:update(o << 1, l, mid, L, R, val)if R > mid:update(o << 1 | 1, mid + 1, r, L, R, val)push_up(o);build(1, 1, n)
ans = 0
for i in range(1, n - k + 2):#查询区间[i, i+k-1]的最小值mi = query(1, 1, n, i, i + k - 1)if mi == 0:                     #无法进行区间消除#res表示当前的a[i]res = query(1, 1, n, i, i)#把当前的a[i]置为0update(1, 1, n, i, i, -res)ans += reselse:ans += mi#区间消除update(1, 1, n, i, i + k - 1, -mi)#res表示当前的a[i]res = query(1, 1, n, i, i)#把当前的a[i]置为0update(1, 1, n, i, i, -res)ans += res
for i in range(n - k + 2, n + 1):ans += query(1, 1, n, i, i)
print(ans)

 10.《数的拆分》真题练习

 

 初步想法：大数分解应该能做，看是否能分解为两个质数或者一个质数，能就输出yes，不能就输出no

import os
import sys
import math# 请在此输入您的代码
t= int(input())
def check(n):count=[]  # 记录有多少个素数cur=0  # 指向列表，方便记录幂次for i in range(2,int(math.sqrt(n))+1):if n%i==0:count.append(0)if len(count)>2:print("no")returnwhile n%i==0:n=n//icount[cur]+=1cur+=1  #记录下一个质数幂次if n>1:count.append(1)if len(count)>2:print("no")return#print(count)if len(count)==1 and count[0]>=2:print('yes')returnif  len(count)==2 and count[0]>=2 and count[1]>=2:print('yes')returnprint('no')for i in range(t):a=int(input())check(a)

正解：题目意思好像弄错了，本题求的是只要分解的质数的幂次大于2就行。（标准做法要用到埃氏筛得到4000内的所有素数，对每一个数遍历，首先判断平方和立方，然后再枚举4000以内的素数因子，如果有幂次等于1的，直接跳出循环打印no）

import os
import sys
import math# 请在此输入您的代码
t= int(input())
def check(n):count=0  # 记录幂次for i in range(2,int(math.sqrt(n))+1):if n%i==0:while n%i==0:n=n//icount+=1if(count<2):print('no')returncount=0   # 复位，记数下一个质数if n>1:  # 剩下一个质数，幂次肯定为1，不满足print("no")returnprint('yes')for i in range(t):a=int(input())check(a)

标程：

import os
import sys
import mathnot_prime = [0]*4010
prime = []
# 预处理400以内的素数
for i in range(2,4001):if not_prime[i]==0:prime.append(i)for j in range(2*i,4001,i):  #埃式筛not_prime[j]=1# 判断平方数
def square_number(x):y=int(x**0.5)return y*y==x or (y+1)*(y+1)==x   #防止精度出问题# 判断立方数
def cubic_number(x):y=int(x**(1/3))return y**3==x or (y+1)**3 ==x
t = int(input())
for i in range(t):a=int(input())# 判断平方和立方if square_number(a) or cubic_number(a):print('yes')continue# 枚举4000以内因子falg=Truefor i in prime:if a%i==0:mi=0while a%i==0:a=a//imi+=1if mi==1:falg=Falsebreakif falg:print('yes')else:print('no')