Python解题 - CSDN周赛第29期 - 争抢糖豆
本期问哥是志在必得,这本算法书我已经觊觎许久,而之前两次因为种种原因未能如愿。因此,问哥这几天花了不少时间,把所有之前在每日一练做过的题目重新梳理了一遍。苦心人,天不负,感谢官方大大!
第一题:订班服
小A班级订班服了! 可是小A是个小糊涂鬼,整错了好多人的衣服的大小。 小A只能自己掏钱包来补钱了。 小A想知道自己至少需要买多少件衣服。
输入描述:第一行输入一个整数n。(1<=n<=100)表示衣服的数量。 以下n行输入n个尺码。表示订单中衣服的尺码。 接下来n行输入n个尺码。小A订的衣服尺码。 尺码表:M,S,L,XL,XLL,XLLL,XLLLL,XLLLLL。
输出描述:输出至少需要买多少件衣服。
示例:
示例 输入 2
XL
X
M
X输出 1
分析
简单题。需要 n 件衣服,买了 n 件衣服,所以只要把需要的 n 件衣服每种尺码的个数,减去已购买的衣服相应尺码的个数,如果大于0就说明该尺码还需要购买。所以最直接的办法就是用哈希表记录每种尺码的个数,然后再逐个检查。
Python已经提供了内置Counter类,可以自动生成字典,而且支持加减法,连逐个检查这一步都省去了:直接相减,剩下的数字加在一起就是答案。
参考代码
n = int(input().strip())
arr1 = [input().strip() for _ in range(n)]
arr2 = [input().strip() for _ in range(n)]
from collections import Counter
clothes = Counter(arr1) - Counter(arr2)
print(sum(clothes.values()))
第二题:争抢糖豆
抓糖豆,小Q与小K都喜欢吃糖豆。 但是糖豆分两种,超甜糖豆和普通糖豆。 现在有w个超甜糖豆和b个普通糖豆。 小Q和小K开始吃糖豆,他们决定谁先吃到超甜糖豆谁就获胜。 小K每次吃的时候会捏碎一颗糖豆。 小Q先吃,小Q想知道自己获胜的概率。 如果两个人都吃不到超甜糖豆小K获胜。
输入描述:输入两个整数w,b。(0<=w,b<=1000)
输出描述:答案保留9位小数。
示例:
示例 输入 1 3 输出 0.500000000
分析
也是以前考过的老题了。可以用递归或动态规划来做,但本题的状态转移不太容易一眼发现,所以可能不少人会觉得难。因为问到概率(胜率),所以本质上还是需要用数学来表达。
以动态规划为例(递归容易超时),我们用 表示当有
颗超甜糖豆,和
颗普通糖豆时自己的胜率。因为先吃到超甜糖豆就获胜了,所以自己要想获胜,只能分成两种情况:
- 先吃到超甜糖豆,概率是
,此情况下直接获胜;
- 先吃到普通糖豆,但是对手也吃到普通糖豆,所以游戏继续,自己还有获胜的可能。(这里有一个特判的情况:如果只有一颗普通糖豆,而自己先吃到普通糖豆的话,无论如何也是输,后面自然就不用算了。)因此,自己和对手都吃到普通糖豆的概率是
。(如果一时看不懂可以多琢磨几遍,乘号左边是自己吃到普通糖豆的概率,右边是自己吃完后对方也吃到普通糖豆的概率,看懂了再继续。)
如果没有“捏碎糖豆”的操作,分析到这就结束了,状态转移就是把这两种情况的胜率加在一起,方程如下:
(因为自己和对手总共吃了两颗普通糖豆,所以上面第二种情况的概率还要乘以 才是胜率。)
如果上面的内容理解了,我们再来分析“捏碎糖豆”的情况。
捏碎糖豆也有两种情况:
- 捏碎了普通糖豆。影响不大,但是上面的第二种状态要接着乘上捏碎普通糖豆的概率,再乘以
。合在一起的胜率就是
。
- 捏碎了超甜糖豆。则二人虽不分胜负,理论上自己还存在胜利的可能(如果还剩下超甜糖豆的话),但是同样地,状态转移方程变了,胜率变成了:
。
这两种捏碎糖豆的情况属于同一决策层级,可以加在一起。于是把捏碎糖豆考虑进来,得到最终的状态转移方程如下:
此外,如之前所述,还要考虑几个特判的情况:
- 没有超甜糖豆,胜率为0,不用计算。
- 没有普通糖豆,胜率100%。
- 只有一颗普通糖豆,胜率为
,因为如果自己先吃到普通糖豆,必输。
很显然,上面第二、三可以合并,而第一条可以在初始化的时候把 的时候设置为0。代码如下:
参考代码
w, b = map(int, input().split())
dp = [[0]*(b+1) for _ in range(w+1)]
for i in range(1, w+1):for j in range(b+1):if j <= 1:dp[i][j]=i/(i+j)else:dp[i][j]=i/(i+j)+j/(i+j)*(j-1)/(i+j-1)*((j-2)/(i+j-2)*dp[i][j-3]+i/(i+j-2)*dp[i-1][j-2])
print(f"{dp[w][b]:.9f}")
输出结果的时候要注意,题目要求必须保留9位小数,空位用0补全,所以要设置占位符。
第三题:走楼梯
现在有一截楼梯,根据你的腿长,你一次能走 1 级或 2 级楼梯,已知你要走 n 级楼梯才能走到你的目的楼层,请实现一个方法,计算你走到目的楼层的方案数。
输入描述:输入整数n。(1<=n<=50)
输出描述:输出方案数。
示例:
示例 输入 5 输出 8
分析
很明显,答案是斐波那契数列。因为一次只能走 1 级或 2 级楼梯,所以第 n 级阶梯可以由 n-1 级阶梯走过来,也可以由 n-2 级阶梯走过来。如果用函数 表示走上第 n 级阶梯的方案数,可得
因为本题 n 范围较小(1<=n<=50),所以使用递归来做应该也没问题。不过更常用的做法是递推,也算是斐波那契的模板题了。
参考代码
n = int(input().strip())
a = b = 1
for _ in range(n):a, b = b, a+b
print(a)
第四题:打家劫舍
一个小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。
输入描述:输入一个正整数n代表房屋的数量(n≤100),接着输入n个非负整数代表每间房屋的现金数量
输出描述:小偷能偷取的最大金额。
示例:
示例 输入 4
1 2 3 1输出 4
分析
力扣原题,经典的打家劫舍系列,但凡刷过点题的相信都做过。而且这里选取的是该系列最简单的一道,动态规划入门题,相关题解太多了,这里问哥只简单说两句吧。
因为相邻的房屋不能同时被盗,所以小偷在当前房屋只有两种选择:不偷当前房屋——继承上个房屋可偷取的的最大金额,偷当前房屋——上上个房屋可偷取的最大金额(因为上个房屋不能偷)加上当前房屋的金额,而当前房屋可偷取的最大金额就等于这两种选择中较大的金额。
如果用 代表当前房屋可偷取的最大金额,
表示当前房屋的金额,可用公式表示如下:
类似斐波那契数列,可以看出 仅由
和
得到(
是给定数组),所以可以使用滚动数组优化空间,换句话说就是只需要额外两个变量循环保存
和
的值即可。
参考代码
n = int(input().strip())
arr = [int(item) for item in input().strip().split()]
a = b = 0
for i in arr:a, b = b, max(b, a+i)
print(b)
相关文章:
Python解题 - CSDN周赛第29期 - 争抢糖豆
本期问哥是志在必得,这本算法书我已经觊觎许久,而之前两次因为种种原因未能如愿。因此,问哥这几天花了不少时间,把所有之前在每日一练做过的题目重新梳理了一遍。苦心人,天不负,感谢官方大大! 第…...

C代码中访问链接脚本中的符号
一、目的在之前的《GNU LD脚本命令语言(一)》、《GNU LD脚本命令语言(二)》我们介绍了GNU链接脚本的知识点,基本上对链接脚本中的SECTION、REGION、以及加载地址与执行地址的关系等内容有了一定的了解。本篇主要讲解链…...

MySQL 8:MySQL索引
索引就是通过一定的算法建立数据模型,用于快速查找某一列中具有特定值的行。如果没有索引,MySQL 必须从第一条记录开始读取整个表,直到找到相关的表。表越大,查询数据所花费的时间就越多。如果表中查询的列有索引,MySQ…...

JVM详解
一,JVM 1,JVM区域划分 类装载器,运行时数据区,字节码执行引擎 2,JVM内存模型(运行时数据区) 由本地方法栈,虚拟机栈,堆,方法区,和程序计数器组成。…...

MySQL数据库调优————索引数据结构
B-TREE B-TREE数据结构 B-TREE特性 根节点的子结点个数2 < X < m,m是树的阶 假设m 3,则根节点可有2-3个孩子 中间节点的子节点个数m/2 < y < m 假设m 3,中间节点至少有2个孩子,最多3个孩子 每个中间节点包含n个关…...

visual studio 改变界面语言
在使用visual studio 2019 时,开始是英文界面,后面变成了中文界面。但是看视频教学时有的是英文界面,我就想回到英文界面,所以有切换界面语言的需要。其实操作很简单:工具-> 选项 打开界面在界面里选择环境…...
2023.2.16每日一题——1250. 检查「好数组」
每日一题题目描述解题核心解法一:数论题目描述 题目链接:1250. 检查「好数组」 给你一个正整数数组 nums,你需要从中任选一些子集,然后将子集中每一个数乘以一个 任意整数,并求出他们的和。 假如该和结果为 1&#x…...

亿级高并发电商项目-- 实战篇 --万达商城项目 八(安装FastDFS、安装Nginx、文件服务模块、文件上传功能、商品功能与秒杀商品等功能)
专栏:高并发---分布式项目 👏作者简介:大家好,我是小童,Java开发工程师,CSDN博客博主,Java领域新星创作者 📕系列专栏:前端、Java、Java中间件大全、微信小程序、微信支…...

Viper捐款7000万韩元,合计人民币是多少钱?
Viper捐款7000万韩元,合计人民币是多少钱? #2023LCK春季赛##英雄联盟# #Viper捐款7000万韩元# Viper向大田东区捐款 7000 万,成为大田荣誉协会 105 号会员。Viper选手从 2019 年开始一直向大田东区捐款,但是他不希望这件事被公开…...

前端vue实现系统拦截跳转外链并进入跳转询问界面
跳转询问界面如下图所示: 给自己挖坑的实现方式,最终解决方案请看最底下 思路:正常情况下我们有2种方式跳转外链 第一种非a标签,我们手动添加事件进行跳转 <div class"dingdan public-padding p-item" click&quo…...
【Linux】Shell(Bash)单引号、双引号、不加引号和反引号用法和区别详解
简要总结 不加引号:不会将含有空格的字符串视为一个整体输出, 如果内容中有变量等,会先把变量解析出结果,然后在输出最终内容来,如果字符串中带有空格等特殊字符,则不能完整的输出,需要改加双引号ÿ…...

本人使用的idea插件
文章目录🚏 本人使用的idea插件🚬 pojo to Json🚬 GsonFormatPlus🚬 EasyYapi🚬 Chinese (Simplified) Language Pack / 中文语言包🚬 MyBatis Log Free🚬 MyBatisPlusX🚬 Statistic…...

站在行业C位,谷医堂打开健康管理服务新思路
对于农村及贫困地区老百姓来说,由于交通因素和家庭经济条件制约,看病难致身体调理情况一直不太乐观,这也导致心理压力很大。然而,随着近年中医药产业崛起与快速发展,这种局面很快就会得到改观,以湖南谷医堂…...

ABO溶血症概率
[简介]ABO溶血是由于母亲和胎儿ABO血型不合引起的新生儿溶血,概率不是很大,一般出现在准妈妈是O血,准爸爸是非O血,这次容易发生血型不合,但新生儿ABO溶血概率不高,大多数症状相对较轻。ABO溶血的概率是什么…...
【算法数据结构体系篇class03】:数组、链表、栈、队列、递归时间复杂度、哈希表、有序表问题
一、反转链表package class03;import java.util.ArrayList; import java.util.List;/*** 链表反转*/ public class ReverseLinkedList {public static class Node {public int value;public Node next;public Node(int data) {value data;}}public static class DoubleNode {p…...
【新2023】华为OD机试 - 最多提取子串数目(Python)
最多提取子串数目 题目 给定由 [a-z] 26 个英文小写字母组成的字符串 A 和 B,其中 A 中可能存在重复字母,B 中不会存在重复字母 现从字符串 A 中按规则挑选一些字母,可以组成字符串 B。 挑选规则如下: 1) 同一个位置的字母只能被挑选一次 2) 被挑选字母的相对先后顺序不…...
嵌入式C语言设计模式 --- 代理模式
1 - 什么是代理模式? 代理模式(Proxy Pattern),是指当客户端无法访问某个对象或者访问某个对象存在困难的时候,可以通过一个代理对象来进行间接访问。 举一个生活中的例子,比如,我们在买火车票或者飞机票的时候,有时候不会直接在12306或者航空公司官网上面购买,而是…...

前端性能优化的整理笔记
🚴 前言大厂面试题分享 面试题库后端面试题库 (面试必备) 推荐:★★★★★地址:前端面试题库🏄利用碎片化的时间,系统的整理,性能优化的知识点。🎯 前端性能优化…...

springboot+mybatis连接数据库实现增删改查功能
springbootmybatis连接数据库实现增删改查功能创建表创建项目实体类DAO接口写sql的XML文件Service层Controller启动类结果目录结构参考博客创建表 create table user(id int ,name varchar(30),pwd varchar(40) )insert into user values(2,hxf,789101),(3,hlm,789102),(4,hzh…...

疑似45亿地址信息泄露事件跟进后续
开放隐私计算 收录于合集#数据安全13个开放隐私计算开放隐私计算OpenMPC是国内第一个且影响力最大的隐私计算开放社区。社区秉承开放共享的精神,专注于隐私计算行业的研究与布道。社区致力于隐私计算技术的传播,愿成为中国 “隐私计算最后一公里的服务区…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

技术栈RabbitMq的介绍和使用
目录 1. 什么是消息队列?2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践
作者:吴岐诗,杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言:融合数据湖与数仓的创新之路 在数字金融时代,数据已成为金融机构的核心竞争力。杭银消费金…...