蓝桥杯第23天(Python)(疯狂刷题第6天)

题型:

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.《技能升级》真题练习(二分)

9.《最长不下降子序列》真题练习(dp,线段树)

10.《最优清零方案》真题练习(暴力枚举,线段树维护)


刷题:

1.《排列字母》真题练习(内置函数)

 初步思想:调用内置函数排序就行了

标程:

s = "WHERETHEREISAWILLTHEREISAWAY"
s = list(s)
s.sort()
print("".join(s))

2.《寻找整数》真题练习(埃氏筛法,或者枚举遍历)

 初步思想:遍历,肯定有规律,然后递增找最小值就行。或者就是埃式筛法。

大致思想代码: 

import os
import sys
mp = {2:1, 3:2, 4:1, 5:4, 6:5,7:4,8:1,9:2,10:9,11:0,12:5,13:10,
      14:11,15:14,16:9,17:0,18:11,19:18,20:9,21:11,22:11,23:15,24:17,25:9,
      26:23,27:20,28:25,29:16,30:29,31:27,32:25,33:11,34:17,35:4,36:29,37:22,
      38:37,39:23,40:9,41:1,42:11,43:11,44:33,45:29,46:15,47:5,48:41,49:46}
# # 先从100-9999里面看看能不能找出一部分
# ls = [i for i in range(100,10**4)]
# result = []

# # 先在[100,9999]中找出除以2-10的余数符合的数字们
# for i in range(2,10):
#       # 使用filter lambda表达式的形式
#       ls = list(filter(lambda  x:x%i==mp[i], ls))
# '''print(ls)
# 此处的结果是[1649, 4169, 6689, 9209],这个结果是有规律的,
# 4169-1649=2520
# 6689-4169=2520
# 9209-6689=2520
# 故而,1649+2520*n的一众结果满足2-10,我们依次接着往下做
# range(起始、末尾、步长)
# '''
#
# #第二次,直接把目光放到(1000,10**9)里面找
# #找10-20之间的
# ls = [i for i in range(1649, 10**9, 2520)]
# for i in range(10,20):
#       ls = list(filter(lambda  x: x%i==mp[i], ls))
'''
print(ls)
结果是[88209209, 321001769, 553794329, 786586889]
[1]-[0]=232792560
[2]-[1]=232792560
故而,88209209+232792560*n
'''

#第三次,直接把目光放在[88209209,10**16]
#找20-30之间的
# ls = [i for i in range(88209209, 10**16, 232792560)]
# for i in range(20,30):
#       ls = list(filter(lambda x:x%i==mp[i], ls))
'''
print(ls)
[391179710009, 2720269272809, 5049358835609,
'''
# a = 2720269272809-391179710009
# ls = [i for i in range(391179710009,10**18,a)]
# for i in range(30,40):
#       ls = list(filter(lambda x:x%i==mp[i],ls))
# print(ls[0])
# 结果是[2022040920220409, 7364972377283609, 12707903834346809,.......
# 只取第一个
print('2022040920220409')

标程:

from math import gcd

#求数字a,b的最小公倍数
def lcm(a, b):
    return a * b // gcd(a, b)

a=[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]
x = 0
step = 1
for i in range(2, 50):
    #暴力求解满足x % i = a[i]
    while x % i != a[i]:
        x += step
    step = lcm(step, i)
print(x)

3.纸张尺寸(循环,判断)

初步想法: 读懂题意,照着逻辑敲出来就行了,没得难度,送分,长除以2的时候可能需要维护长边,因为可能长会比宽大

标程:

x = int(input()[1])
a, b = 1189, 841
for i in range(x):
    a //= 2
    if a < b:
        a, b = b, a
print(a)
print(b)

4.数位排序(自定义排序规则,字符串操作)

初步思路:将数字以字符形式存储,然后转列表,自定义排序规则,首先比较和,如果和相同再按字典序排序,自定义排序规则(functools)

标程:

n = int(input())
m = int(input())
a = [i for i in range(1, n + 1)]
b = [0] * (n + 1)
for i in range(1, n + 1):
    #求i的数位之和
    num = i
    while num != 0:
        b[i] += num % 10
        num //= 10

a.sort(key=lambda x: (b[x], x))
print(a[m - 1])

5.《蜂巢》真题练习(思维题,坐标转换)

 初步思路:转换为直角坐标来做!

 正解:也是转为二元组坐标,但是是以3为x的正方向,2为y的正方向
 

标程:

# 方向增量
dir = [[-1, 0], [-1, 1], [0, 1], [1, 0], [1, -1], [0, -1]]

# 将<d,p,q>转换成新坐标系下的<x,y>
def change(d, p, q):
    x, y = 0, 0
    x += dir[d][0] * p
    y += dir[d][1] * p
    d = (d + 2) % 6
    x += dir[d][0] * q
    y += dir[d][1] * q
    return x, y


d1, p1, q1, d2, p2, q2 = map(int, input().split())
Ax, Ay = change(d1, p1, q1)# 转换坐标
Bx, By = change(d2, p2, q2)
first, second = Ax - Bx, Ay - By# 计算差值向量
if first * second >= 0:# 分类讨论
    print(abs(first) + abs(second))
else:
    print(max(abs(first), abs(second)))

6.《消除游戏》真题练习(暴力循环,列表,字符串操作)

初步思路:遍历一次找到所有的边缘字符,记录下标,然后删除。最后如果数组长度不变或者长度为零,就退出。

正解:思路类似,有个优化,就是标记数组长度为当前字符长度,可以节约时间。

s = list(input())
last_length = 0

while True:
    length = len(s)
    #如果长度等于0,终止
    if length == 0:
        print("EMPTY")
        break
    #如果长度未发生变化,终止
    if length == last_length:
        print("".join(s))
        break
    vis = [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] = 1
        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] = 1
    #将边缘字符去除
    tmp_s = []
    for i in range(length):
        if vis[i] == 0:
            tmp_s.append(s[i])
    s = tmp_s
    last_length = length

7.《全排列的价值》真题练习(数学性质,排列组合)

 初步思想:找规律,看是否有规律,没得的话就暴力,能过多少过多少。(无规律)

 正解:数学性质可以得到,顺序对个数加上逆序对个数 的和是一定的,等于n*(n-1)//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.《技能升级》真题练习(二分)

 初步思想:贪心,优先升级升级后增加点数最多的,每次升级后更新升级点数和技能有用值。(过40%数据)

import sys  #设置递归深度
import collections  #队列
import itertools  # 排列组合
import heapq  #小顶堆
import math
sys.setrecursionlimit(300000)
import functools   # 自定义比较函数  -1不变,1交换


save=[]
n,m=map(int,input().split())
for i in range(n):
   a,b=map(int,input().split())
   save.append([a,b,math.ceil(a/b)])

save.sort(key=lambda x:x[0],reverse=True)  # 按当前升级增点树排序
#print(save)
ans=0
for i in range(m):  # 升级m次技能
   for i in save:
      if i[2]>0:   # 升级还有效
         ans+=i[0]
         i[2]-=1
         i[0]=i[0]-i[1]
         break
   save.sort(key=lambda x:x[0],reverse=True)  # 按当前升级增点树排序
   #print(save)
print(ans)

正解:将问题转变成在 N 个递减的等差数列中前 M 大和是多少,第 i 个等差数列的首项为 Ai​,公差为 Bi​。由于是等差数列,存在单调性,可以使用二分答案求出第 M 大的数值

标程:

n, m = map(int, input().split())
a = [0] * (n + 1)
b = [0] * (n + 1)
for i in range(1, n + 1):
  a[i], b[i] = map(int, input().split())

#假设第m大为x,求存在多少个数字>=x
def check(x):
  cnt = 0
  for i in range(1, n + 1):
    if a[i] < x:
      continue
    k = (a[i] - x) // b[i]
    cnt += k + 1
  return cnt >= m

left, right, x = 0, 1000000, 0
while left <= right:
  mid = (left + right) // 2
  if check(mid):
    x, left = mid, mid + 1
  else:
    right = mid - 1

#已经求出第M大为x,求解前M大和
#大于x的数字个数num,数字之和ans
num, ans = 0, 0
for i in range(1, n + 1):
  if a[i] < x:
    continue
  #找一个最大的满足k:a[i] - k * b[i] > x
  k = (a[i] - x) // b[i]
  if k * b[i] != (a[i] - x):
    k += 1
  #a[i] + a[i]-b[i] + ... +a[i]-(k-1)*b[i]
  ans += (a[i] + a[i] - (k - 1) * b[i]) * k // 2
  num += k
ans += (m - num) * x
print(ans)

9.《最长不下降子序列》真题练习(dp,线段树)

 初步思想:首先通过dp算出最长递增子序列,然后从最长结尾倒推回去看是否有区间满足<=k,有的话+k就行了。(不要这道题分,不会

正解:dp最长不下降子序列,线段树

标程:

import sys

input = lambda: sys.stdin.buffer.readline().rstrip()

maxn = 100010
b = [0] * maxn
dp = [0] * maxn
tree = [0] * (maxn * 4)

#权值线段树,维护dp数组,不需要初始化
#更新下标为x,与val取max
def update(o, l, r, x, val):
    if l == r:
        tree[o] = max(tree[o], val)
        return
    mid = (l + r) >> 1
    if x <= mid:
        update(o << 1, l, mid, x, val)
    else:
        update(o << 1 | 1, mid + 1, r, x, val)
    tree[o] = max(tree[o << 1], tree[o << 1 | 1])

#查询区间[L,R]最大值
def query(o, l, r, L, R):
    if L <= l and r <= R:
        return tree[o]
    mid = (l + r) >> 1
    ans = 0
    if L <= mid:
        ans = max(ans, query(o << 1, l, mid, L, R))
    if R > mid:
        ans = max(ans, query(o << 1 | 1, mid + 1, r, L, R))
    return ans

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
if n == k:
    print(n)
else:
    #离散化
    S = set(a)    #去重
    b = list(S)   #排序
    tot = len(b)
    b.sort()
    for i in range(len(a)):
        left, right, ans = 0, tot - 1, -1
        while left <= right:
            mid = (left + right) >> 1
            if b[mid] >= a[i]:
                ans = mid
                right = mid - 1
            else:
                left = mid + 1
        a[i] = ans + 1
    a = [0, *a]
    
    ans = 0
    #从前往后遍历a,放入权值线段树中
    for i in range(1, n + 1):
        dp[i] = query(1, 1, tot, 1, a[i]) + 1
        update(1, 1, tot, a[i], dp[i])
    #重新清空权值线段树
    tree = [0] * (maxn * 4)
    for i in range(n, k, -1):
        #a[i-k+1] ... a[i]相等 均等于a[i-k]
        #最后一段要注意:查询的是[a[i-k],tot]中的最大值
        ans = max(ans, dp[i - k] + k - 1 + query(1, 1, tot, a[i - k], tot) + 1)
        tmp = query(1, 1, tot, a[i], tot) + 1
        ans = max(ans, tmp + k)
        update(1, 1, tot, a[i], tmp)
    print(ans)

10.《最优清零方案》真题练习(暴力枚举,线段树维护)

 初步思路:循环遍历就行,优先操作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] = 0
    if l == r:
        tree_mi[o] = a[l]
        return
    mid = (l + r) >> 1
    build(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) >> 1
    ans = 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] += val
        tree_add[o] += val
        return
    push_down(o);
    mid = (l + r) >> 1
    if 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]置为0
        update(1, 1, n, i, i, -res)
        ans += res
    else:
        ans += mi
        #区间消除
        update(1, 1, n, i, i + k - 1, -mi)
        #res表示当前的a[i]
        res = query(1, 1, n, i, i)
        #把当前的a[i]置为0
        update(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)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/6688.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

下一个系统不是Win12,微软要复活Win10X

先是 Windows 三年发布周期回归又是官方 UI 泄露&#xff0c;再到前不久新增的测试频道… 微软将在2024年推出或许名为 Windows 12 的下一代系统基本已经板上钉钉了。 相比过去&#xff0c;小蝾总觉得即便是换代更新能带来的震撼都越来越少了。 当年每一个版本都是划时代的更…

.net C#反编译及脱壳常用工具--小结

1、Reflector --微软自家工具--推荐 Reflector是最为流行的.Net反编译工具。Reflector是由微软员工Lutz Roeder编写的免费程序。Reflector的出现使NET程序员眼前豁然开朗&#xff0c;因为这个免费工具可以将NET程序集中的中间语言反编译成C#或者Visual Basic代码。除了能将IL转…

【学习笔记、面试准备】机器学习西瓜书要点归纳和课后习题参考答案——第3章

机器学习西瓜书要点归纳第3章 线性模型3.1 基本形式3.2 线性回归3.3 对数几率回归3.4 线性判别分析3.5 多分类学习3.6 类别不平衡问题3.7 阅读材料习题目录地址 第3章 线性模型 3.1 基本形式 线性模型定义&#xff1a; 其中x是输入向量 优点&#xff1a;形式简单&#xff…

C#中的转换

一、什么是转换 将一个类型转换为另外一个类型&#xff1b;可以是两个值类型之间的转换&#xff1b;可以是两个引用类型之间的转换&#xff1b;可以是值类型和引用类型之间的转换&#xff08;拆箱与装箱&#xff09;&#xff1b;可以用户自定义转换。转换的时候有隐式转换/自动…

lombok快速入门

Lombok是一个实用的Java类库&#xff0c;可以通过简单的注解来简化和消除一些必须有但显得很臃肿的Java代码。 通过注解的形式自动生成构造器、getter/setter、equals、hashcode、toString等方法&#xff0c;并可以自动化生成日志变量&#xff0c;简化java开发、提高效率。 <…

好用到爆的windows文件检索工具--Everything

如果你的电脑是windows系统&#xff0c;那么这款软件强烈推荐大家安装>Everything&#xff0c;他可以帮助你快速的检索的磁盘里的文件&#xff0c;话不多说&#xff0c;开始安装 1.下载 访问https://www.voidtools.com/zh-cn/会跳转官方下载地址 双击安装包运行 效果如下…

Tensor张量基础与常用方法【Pytorch】

Tensor中文译名为张量&#xff0c;标量是零维张量&#xff0c;向量是一维张量&#xff0c;矩阵是二维张量&#xff0c;矩阵的堆叠是三维张量…… 张量的维数可以无穷大&#xff0c;不过由于现实世界是三维的&#xff0c;因此更高维度的图形我们无法想象&#xff0c;但是这并不…

即时通讯-6-已读回执的方案设计

背景-为什么展示已读未读 部分即时通讯软件会选择展示给用户已读未读&#xff0c; 主要是快速感知对方的阅读状态&#xff0c; 感觉到自己受重视&#xff0c; 方便做下一步操作。 如果要带点高度的讲&#xff0c;满足软件所代表的关键用户的诉求 什么场景下要展示已读回执 t…

462. 最小操作次数使数组元素相等 II——【Leetcode每日一题】

462. 最小操作次数使数组元素相等 II 给你一个长度为 n 的整数数组 nums &#xff0c;返回使所有数组元素相等需要的最小操作数。 在一次操作中&#xff0c;你可以使数组中的一个元素加 1 或者减 1 。 示例 1&#xff1a; 输入&#xff1a;nums [1,2,3] 输出&#xff1a;2 …

微信小程序获取手机号47001 data format error hint的完美解答(restTemplate发送post请求)

发现问题 这几天正在搞微信小程序获取手机号功能开发&#xff0c;发现发送post请求接口时候&#xff0c;接口返回如下错误&#xff1a; {"errcode": 47001,"errmsg": "data format error hint: [******] rid: ******" } post请求的url为&…

动态代理原理

一、案例分析 1、引出问题 回到Spring之初控制事务繁琐的问题。 回到Spring之初控制事务繁琐的问题. 考虑一个应用场景∶需要对系统中的某些业务方法做事务管理&#xff0c;拿简单的save和update操作举例。没有加上事务控制的代码如下。 加上事务代码&#xff0c;如下&#x…

大数据平台开发——使用Java和Python调用Shell脚本

大数据平台开发——使用Java和Python调用Shell脚本 背景 在大数据平台开发中&#xff0c;经常会遇到需要调用Shell脚本的场景&#xff0c;倒不是说只能用Shell&#xff0c;毕竟大数据开发到头来一定是个语言无关的事情&#xff1a; 从Hive源码解读大数据开发为什么可以脱离S…

Java进阶

注解 什么是注解 Java注解&#xff08;Annotation&#xff09;又称Java标注&#xff0c;是JDK5.0引入的一种注释机制。 Java语言中类、方法、变量、参数和包等都可以被标注。Java标注可以通过反射获取标注内容。在编译器生成类文件时&#xff0c;标注可以被嵌入到字节码中。Ja…

【Python实操】一行代码就可以自动画出这种艺术画?(详细教程)

文章目录前言一.准备阶段二、开始使用 Discoart1.引入库2.显示/保存/加载配置总结前言 DiscoArt 是一个很牛逼的开源模块&#xff0c;它能根据你给定的关键词自动绘画。 绘制过程是完全可见的&#xff0c;你可以在 jupyter 页面上看见这个绘制的过程&#xff1a; 一.准备阶段…

零拷贝内存 固定内存

一、总览 虚拟内存是一种计算机内存管理的技术&#xff0c;它让程序认为程序自身有一段完整的连续可用的内存&#xff08;一个地址空间&#xff09;。当程序运行时所占的内存空间大于物理空间容量&#xff0c;操作系统可以将暂时不用的数据放入到磁盘&#xff0c;用的时候再拿出…

Linux--高级IO--select--0326

目录 IO为什么低效&#xff1f; 1.快速理解五种IO模式 2.五种IO模型 3.非阻塞IO fcntl() 4.IO多路转接 select select fd_set类型 struct timeval*类型 5.Select的代码测试 5.1 问题一&#xff1a;一开始&#xff0c;我们只有一个listen套接字 5.2 问题二&#xff1…

《项目管理知识体系指南(PMBOK)》第7版之8大绩效域

项目绩效域被定义为一组对有效交付项目成果至关重要的相关活动。 《项目管理知识体系指南&#xff08;PMBOK&#xff09;》第7版将项目管理划分为干系人、团队、开发方法和生命周期、规划、项目工作、交付、测量、不确定性共8大绩效域。 一、干系人绩效域 解决与干系人相关的…

【对YOLOv8(ultralytics)打印测试结果的调整】(1)使得map值打印显示从0.551变为55.08 (2)打印出FPS

目录1. 最终打印效果2. 做两处更改2.1 修改map显示&#xff0c;在ultralytics-main/ultralytics/yolo/v8/detect/val.py中操作2.2 打印FPS&#xff0c;在ultralytics-main/ultralytics/yolo/engine/validator.py中操作❗❗❗ 兄弟姐妹们&#xff0c;如果看习惯了运行train.py时…

PMP应该如何备考?

PMP现在是新考纲&#xff0c;PMP新版大纲加入了 ACP 敏捷管理的内容&#xff0c;而且还不少&#xff0c;敏捷混合题型占到了 50%&#xff0c;前不久官方也发了通知 8月启用第七版《PMBOK》&#xff0c;大家都觉得考试难度提升了&#xff0c;我从新考纲考完下来&#xff0c;最开…

Moonbeam隆重推出您的个人开发小助手 — — Kapa.ai

Moonbeam为开发者提供内容详细的开发者文档和全天候的Discord支持。但假如&#xff1a;有人可以24/7查看Discord并在15秒之内就回复您的问题 — — 新推出的Kapa.ai机器人使这个假如成为现实。Kapa.ai是一款由ChatGPT支持的AI机器人&#xff0c;可以回答关于在Moonbeam上构建的…
最新文章