2024蓝桥杯每日一题(回溯)

备战2024年蓝桥杯 -- 每日一题
Python大学A组

        试题一:木棒
        试题二:n皇后问题
        试题三:糖果
        试题四:飞机降落
        试题五:生日蛋糕


试题一:木棒

【问题描述】

        乔治拿来一组等长的木棒,将它们随机地砍断,使得每一节木棍的长度都不超过 5050 个长度单位。然后他又想把这些木棍恢复到为裁截前的状态,但忘记了初始时有多少木棒以及木棒的初始长度。请你设计一个程序,帮助乔治计算木棒的可能最小长度。每一节木棍的长度都用大于零的整数表示。

【输入格式】

        输入包含多组数据,每组数据包括两行。

        第一行是一个不超过 6464 的整数,表示砍断之后共有多少节木棍。

        第二行是截断以后,所得到的各节木棍的长度。

        在最后一组数据之后,是一个零。

【输出格式】

        为每组数据,分别输出原始木棒的可能最小长度,每组数据占一行。

【数据范围】

        数据保证每一节木棍的长度均不大于 5050。

【输入样例】

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

【输出样例】

6
5

【解题思路】

【Python程序代码】

x = int(input())
def dfs(u,now,start):
    if u*l==suma:return True
    if now==l:return dfs(u+1,0,0)
    i = start
    while i<x:
        if st[i]:i+=1; continue
        if a[i]+now>l:i+=1; continue
        st[i]=True
        if dfs(u,now+a[i],i+1):return True
        st[i]=False
        if start==0 or now+a[i]==l:return False
        j = i
        while j<x and a[j]==a[i]:j+=1
        i = j-1
        i += 1
    return False
while x:
    a = list(map(int,input().split()))
    suma = sum(a)
    st = [0]*(70)
    a.sort(reverse=True)
    for i in range(len(a)):
        if a[i]>50:st[i]=1
    l = 1
    while 1:
        if suma%l==0 and dfs(0,0,0):
            print(l); break
        l += 1
    x = int(input())

试题二: n-皇后问题

【问题描述】

        n−皇后问题是指将 n个皇后放在 n×n 的国际象棋棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上。

         现在给定整数 n,请你输出所有的满足条件的棋子摆法。

【输入格式】

        共一行,包含整数 n。

【输出格式】

        每个解决方案占 n 行,每行输出一个长度为 n 的字符串,用来表示完整的棋盘状态。

        其中 . 表示某一个位置的方格状态为空,Q 表示某一个位置的方格上摆着皇后。

        每个方案输出完成后,输出一个空行。

【数据范围】

        1≤n≤9

【输入样例】

4

【输出样例】

.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

 【解题思路】

        经典DFS问题,必做题,直接见代码

【Python程序代码】

n = int(input())
r,l,dg,udg = [0]*(n+5),[0]*(n+5),[0]*(2*n+5),[0]*(2*n+5)
st = [[0]*(n+5) for _ in range(n+5)]
def dfs(u):
    if u==n+1:
        for i in range(1,n+1):
            for j in range(1,n+1):
                if st[i][j]:print('Q',end='')
                else:print('.',end='')
            print()
        print()
    for i in range(1,n+1):
        if r[i] or l[u] or dg[i-u+n] or udg[i+u]:continue
        st[i][u]=1
        r[i]=l[u]=dg[i-u+n]=udg[i+u]=1
        dfs(u+1)
        st[i][u]=0
        r[i] = l[u] = dg[i - u + n] = udg[i + u] = 0
dfs(1)

试题三:糖果

【题目描述】

        糖果店的老板一共有 M 种口味的糖果出售。为了方便描述,我们将 M 种口味编号 1∼M。小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果,而是 K颗一包整包出售。幸好糖果包装上注明了其中 K 颗糖果的口味,所以小明可以在买之前就知道每包内的糖果口味。给定 N 包糖果,请你计算小明最少买几包,就可以品尝到所有口味的糖果。

【输入格式】

        第一行包含三个整数 N,M,K。

        接下来 N 行每行 K 个整数 T1,T2,⋅⋅⋅,TK,代表一包糖果的口味。

【输出格式】

        一个整数表示答案。

        如果小明无法品尝所有口味,输出 −1。

【数据范围】

        1≤N≤100,
        1≤M,K≤20,
        1≤Ti≤M

【输入样例】

6 5 3
1 1 2
1 2 3
1 1 3
2 3 5
5 4 2
5 1 2

【输出样例】

2

 【解题思路】

        可重复覆盖问题,搜索顺序:依次枚举品尝每种糖果(每一列)到底选哪一包糖果(哪一行),看看哪一行有该种类糖果(该列为1表示有该种类糖果)直到把所有的列都覆盖完为止,或者发现有一列无法覆盖也结束,说明无解。
        优化方法:
        1.迭代加深:枚举答案,看看答案是1包能不能覆盖所有类糖,答案是2包能不能覆盖所有类糖…
        2.从少分支的开始枚举
        3.可行性剪枝:添加估价函数h(),至少要选多少行?如果当前剩下的行数<最少的行数,那么肯定无法覆盖。h()的计算:如果某一列没选,就把这一列所有能选的行数都选掉,算作选了1行,这样算出来的行数肯定是<=正确结果的最小行数的。
        4.位运算优化

【Python程序代码】

n,m,k = map(int,input().split())
l2,col = [0]*(1<<m+1),[[] for _ in range(m+5)]
def lowbit(x):
    return x&-x
def h(state):
    res = 0
    i = (1<<m)-1-state
    while i:
        c = l2[ lowbit(i) ]
        for r in col[c]:
            i&=~r
        res += 1
        i -= lowbit(i)
    return res
def dfs(res,state):
    if res==0 or h(state)>res:return state==(1<<m)-1
    t = -1
    i = (1<<m)-1-state
    while i:
        c = l2[ lowbit(i) ]
        if t==-1 or len(col[t])>len(col[c]):
            t = c
        i -= lowbit(i)
    for r in col[t]:
        if dfs(res-1,state|r):return True
    return False
for i in range(m):l2[1<<i]=i
for i in range(n):
    tep = list(map(int,input().split()))
    state = 0
    for j in range(k):
        c = tep[j]
        state |= 1<<(c-1)
    for j in range(m):
        if state&(1<<j):col[j].append(state)
res = 1
tep = [[] for _ in range(m+5)]
for i in range(m):
    tp = set(col[i])
    tep[i]+=list(tp)
col = tep
while res<=m and dfs(res,0)==False:res+=1
if res>m:res=-1
print(res)

 试题四:飞机降落

【题目描述】

        有 N 架飞机准备降落到某个只有一条跑道的机场。其中第 i架飞机在 Ti 时刻到达机场上空,到达时它的剩余油料还可以继续盘旋 Di 个单位时间,即它最早可以于 Ti 时刻开始降落,最晚可以于 Ti+Di 时刻开始降落。降落过程需要 Li 个单位时间。一架飞机降落完毕时,另一架飞机可以立即在同一时刻开始降落,但是不能在前一架飞机完成降落前开始降落。请你判断 N 架飞机是否可以全部安全降落。

【输入格式】

        输入包含多组数据。

        第一行包含一个整数 T,代表测试数据的组数。

        对于每组数据,第一行包含一个整数 N。

        以下 N 行,每行包含三个整数:Ti,Di 和 Li

【输出格式】

        对于每组数据,输出 YES 或者 NO,代表是否可以全部安全降落。

【数据范围】

        对于 30% 的数据,N≤2。
        对于 100%的数据,1≤T≤10,1≤N≤10,0≤Ti,Di,Li≤100000。

【输入样例】

2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20

【输出样例】

YES
NO

【解题思路】

         简单的DFS,考虑所有的排列情况然后判定是否可以全部降落即可。也可以直接进行DFS。

【Python程序代码】

t = int(input())
def dfs(start,u):
    global flag
    if u==n:
        flag = 1
        return
    if flag==1:return
    for i in range(n):
        if st[i]:continue
        t,d,l = tdl[i]
        if t+d>=start:
            st[i] = 1
            dfs(max(start,t)+l,u+1)
            st[i] = 0
        else:continue
for _ in range(t):
    n = int(input())
    tdl = []
    st = [0]*(20)
    for i in range(n):
        tdl.append(list(map(int,input().split())))
    flag = 0
    dfs(0,0)
    if flag:print('YES')
    else:print('NO')

 试题五:生日蛋糕

【问题描述】

        7 月 17日是 Mr.W 的生日,ACM-THU 为此要制作一个体积为 Nπ 的 M层生日蛋糕,每层都是一个圆柱体。设从下往上数第 i 层蛋糕是半径为 Ri,高度为 Hi的圆柱。当 i<M时,要求 Ri>Ri+1 且 Hi>Hi+1。由于要在蛋糕上抹奶油,为尽可能节约经费,我们希望蛋糕外表面(最下一层的下底面除外)的面积 Q 最小。令 Q=Sπ,请编程对给出的 N 和 M,找出蛋糕的制作方案(适当的 Ri 和 Hi的值),使 S 最小。除 Q 外,以上所有数据皆为正整数。

【输入格式】

        输入包含两行,第一行为整数 N,表示待制作的蛋糕的体积为 Nπ。

        第二行为整数 M,表示蛋糕的层数为 M。

【输出格式】

        输出仅一行,是一个正整数 S(若无解则 S=0)。

【数据范围】

        1≤N≤10000,
        1≤M≤20

【输入样例】

100
2

【输出样例】

68

【解题思路】

        DFS剪枝的经典问题:
        1.剪枝一:蛋糕由上到下的半径和高度逐渐递减,所以可以初始化一个每层的最小半径和最小高度。
        2.剪枝二:当前摆放的体积若是加上当前能放的最小体积还大于要求体积。说明这个体积不合法(过大),若是已经求出的体积加上我们能够尽可能少的最小侧面积比当前最优解还大,说明该分支一定走不到最优解。
        3.剪枝三:从下往上搜,先枚举大的半径或高度,从小的分枝开始搜索。
        4.剪枝四:s + 2 * (n - v) / R[m + 1] >= ans ,和 s + sqrt(n - v) * 2 >= ans,得分别从计算公式的角度进行放缩剪枝。

【Python程序代码】

n = int(input())
m = int(input())
sumv,sums = [0]*(m+5),[0]*(m+5)
for i in range(1,m+1):
    sumv[i] += sumv[i-1] + i*i*i
    sums[i] += sums[i-1] + i*i
r,h = [0]*(m+5),[0]*(m+5)
r[m+1]=h[m+1]=1000000000
ans = 1e9
def dfs(u,nv,ns):
    global ans
    if u==0:
        if nv==n:ans = min(ans,ns)
        return
    if nv+sumv[u]>n:return
    if ns + sums[u]>=ans:return
    if ns + (n-nv)//r[u+1]*2>=ans:return
    if ns + 2*(n-nv)**0.5>=ans:return
    for i in range( min(r[u+1]-1, int(((n-nv)//u)**0.5)),u-1,-1):
        for j in range( min(h[u+1]-1, int((n-nv)/i/i)),u-1,-1):
            t = 0
            if u==m:t=i*i
            r[u]=i; h[u]=j
            dfs(u-1,nv+i*i*j,ns+2*i*j+t)

dfs(m,0,0)
if ans==1e9:print(0)
else:print(ans)

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

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

相关文章

steam_api.dll“是什么?打开游戏出现找不到steam_api.dll无法继续执行代码如何解决

"steam_api.dll"是什么&#xff1f;&#xff0c;steam_api.dll它是由windows系统Visual C Redistributable for Visual Studio提供的。当这个文件损坏或丢失时&#xff0c;会导致一些应用程序无法运行&#xff0c;显示找不到"steam_api.dll"缺失错误。本文…

马斯克开源的grok AI大模型

马斯克践行诺言&#xff0c;坚持开源原则&#xff0c;选择开源自家的 AI 大模型——Grok-1 下载链接如下: https://github.com/xai-org/grok-1 Grok-1 开源仅过去了 10 个小时&#xff0c;该项目便获得了 超过16k 的 Star&#xff0c;成为众人关注的焦点所在。 后续继续更新…

Python二级备考(1)考纲+基础操作

考试大纲如下&#xff1a; 基本要求 考试内容 考试方式 比较希望能直接刷题&#xff0c;因为不懂的比较多可能会看视频。 基础操作刷题&#xff1a; 知乎大头计算机1-13题 import jieba txtinput() lsjieba.lcut(txt) print("{:.1f}".format(len(txt)/len(ls)…

springcloud:4.2 GateWay结合JWT实现网关鉴权

概述 概述 简介 JWT是一种用于双方之间传递安全信息的简洁的、URL安全的声明规范。 定义了一种简洁的,自包含的方法用于通信双方之间以Json对象的形式安全的传递信息。 特别适用于分布式站点的单点登录(SSO)场景 传统的session认证的缺点 安全性:CSRF攻击因为基于cookie来…

掌握AI写作工具:引领内容创作潮流

随着技术发展&#xff0c;AI技术正日益渗透到各行各业&#xff0c;并对内容创作领域产生了深远影响。随着AI写作工具的不断发展和普及&#xff0c;内容创作者们正逐渐看到了AI在提高效率、创造力和质量方面的巨大潜力。本文将探讨AI写作工具如何引领内容创作潮流&#xff0c;以…

vue antd table嵌套表格 左侧展开图标动态控制显示隐藏

antd a-table想要实现如以下效果&#xff0c;有子级就显示展开图标&#xff0c;没有就不显示图标&#xff1a; 话不多说&#xff0c;直接上代码&#xff1a; <template><a-table :columns"columns" :data-source"dataSource"><template #b…

最新若依项目快速上手

最新若依项目快速上手 配套视频&#xff1a;若依项目快速上手视频 1. 下载源码 官网&#xff1a;https://ruoyi.vip/ 前端 git clone https://github.com/yangzongzhuan/RuoYi-Vue3.git后端 git clone https://gitee.com/y_project/RuoYi-Vue.git2. 数据库 创建数据库ry-vue…

JAVA后端调用OpenAI接口 实现打字机效果(SSE)

SSE SSE&#xff08;Server-Sent Events&#xff0c;服务器发送事件&#xff09;是一种基于HTTP协议的通信技术&#xff0c;它允许服务器持续地将数据推送给客户端&#xff0c;而无需客户端发起请求。这种通信方式通常用于实时性要求较高的场景&#xff0c;如实时更新、通知、或…

Linux:搭建ntp服务器

我准备两个centos7服务器 一个为主服务器连接着外网&#xff0c;并且搭建了ntp服务给其他主机同步 另外一个没有连接外网&#xff0c;通过第一台设备去同步时间 首先两个服务器都要安装ntp软件 yum -y install ntp 再把他俩的时间都改成别的 左侧的是主服务器&#xff0c;主…

【Docker篇】自定义Dockerfile的操作

文章目录 &#x1f354;镜像结构&#x1f6f8;什么是Dockerfile⭐基于Ubuntu镜像构建一个新镜像&#xff0c;运行一个java项目&#x1f50e;使用 java:8-alpine &#x1f354;镜像结构 镜像是将应用程序及其需要的系统函数库、环境、配置、依赖打包而成。 我们以MySQL为例&am…

JVM中对象创建过程

在JVM中对象的创建&#xff0c;我们从一个new指令开始&#xff1a; 这个过程大概图示如下&#xff1a; 虚拟机收到new指令触发。 类加载检查&#xff1a;如果类没有被类加载器加载&#xff0c;则执行类加载流程&#xff08;将class信息加载到JVM的运行时数据区的过程&#xff…

KiCad 从原理图创建或者导出原理图符号

KiCad 从原理图创建或者导出原理图符号 原理图中&#xff0c;在下那个要导出的符号上点击右键-》属性-》编辑符号 在符号编辑中选择&#xff1a;文件-》导出符号 加微信&#xff1a;jiyuyun18, 交流电子技术 留言&#xff1a;CSND 电子技术交流群&#xff0c;加入电子微信电…

如何利用生成式AI进行品牌定位调研?

在激烈的市场竞争中&#xff0c;一个明确的品牌定位能够帮助企业突出其独特性&#xff0c;吸引并保留目标消费者。品牌定位调研是企业了解自身、竞争对手以及市场需求的重要手段&#xff0c;是制定有效市场策略的基础。本文将详细介绍如何进行品牌定位调研&#xff0c;包括调研…

PyTorch学习笔记之激活函数篇(四)

4、 Leaky ReLU 函数 4.1 公式 Leaky ReLU函数的公式&#xff1a; f ( x ) { x , x > 0 λ x , x < 0 , λ ∈ ( 0 , 1 ) f(x) \begin{cases} x&,x>0 \\ \lambda x&,x<0,\lambda \in(0,1) \end{cases} f(x){xλx​,x>0,x<0,λ∈(0,1)​ Leakly R…

MySQL连接数不足导致服务异常GetConnectionTimeoutException

文章目录 场景复现解决方案一、调整连接数二、优化程序 场景复现 已经上线正常运行的项目突然很多功能无法使用&#xff0c;查看程序日志发现MySQL报错&#xff0c;异常信息: Could not open JDBC Connection for transaction; nested exception is com.alibaba.druid.pool.Ge…

分布式(计算机算法)

目录 分布式计算 分布式​编辑 分布式和集群 分布式和集群的应用场景 分布式应用场景 集群应用场景 哪种技术更优、更快、更好呢 性能 稳定性 以下概念来源于百度百科 分布式计算 分布式计算是近年提出的一种新的计算方式。所谓分布式计算就是在两个或多个软件互相共享信息…

【ArcGISProSDK】添加异步执行时进度窗口

运行结果 代码 protected override async Task InitializeAsync(){using (ProgressorSource progressorSource new ProgressorSource("初始化...")){await QueuedTask.Run(delegate{MessageBox.Show(licenseExpirationDate.ToString());}, progressorSource.Progres…

介绍一下Spring的AOP

一、问题解析 典型回答 AOP(Aspect-Oriented Programming)&#xff0c;即面向切面编程&#xff0c;用人话说就是把公共的逻辑抽出来&#xff0c;让开发者可以更专注于业务逻辑开发。 和IOC一样&#xff0c;AOP也指的是一种思想。AOP思想是OOP&#xff08;Object-Oriented Prog…

【Java刷题篇】滑动窗口

文章目录 &#x1f4c3;滑动窗口&#x1f4dc;基本概念&#x1f4dc;核心思路 ✍最大连续1的个数 III✍水果成篮 &#x1f4c3;滑动窗口 &#x1f4dc;基本概念 滑动窗口是一种基于双指针的一种思想&#xff0c;两个指针指向的元素之间形成一个窗口。 分类&#xff1a;窗口有…

C++语言现在还有人学吗?

在当今信息爆炸的时代&#xff0c;计算机编程语言繁多&#xff0c;涌现了许多新兴的编程语言&#xff0c;如Python、JavaScript等。针对C编程语言是否还有人学的问题&#xff0c;我个人认为可以从以下几个方面进行讨论。 首先&#xff0c;C诞生于1979年&#xff0c;起初是为了开…