当前位置: 首页 > article >正文

蓝桥杯备赛 [day01]|python|迷宫问题|乘积尾零|平方和|切面条|付账问题

目录

0 题目类型 

1 迷宫问题

图解

2 乘积尾零

算法解释

用Python处理大数

用C++编码 

3 平方和

解题技巧 

4 切面条

算法解释

5 贪心问题——付账问题 ​编辑

思路

求解步骤


0 题目类型 

(1)杂题。不需要算法和数据结构,只需要逻辑、推理的题目,难度可难可易。考察思维能力和编码能力,只能通过大量做题来提高。

(2)BFS搜索和DFS搜索。也就是暴力搜索,这是非常基本的算法,是基础中的基础。

(3)动态规划。线性DP,以及一些DP应用,例如状态压缩DP、树形DP等。

(4)简单数学和简单数论

(5)简单的字符串处理、输入输出、简单图论

(6)基本算法,例如排序、排列、二分、倍增、差分、贪心。

(7)基本数据结构。队列、栈、链表、二叉树。

1 迷宫问题

给出一个迷宫,问迷宫内的人有多少能走出来。迷宫如右图所示:每个位置上有一个人,共100人。每个位置有指示牌,L表示向左走,R表示向右走,U表示向上走,D表示向下走。 

图解

2 乘积尾零

给出100个整数,此处省略题目给的100个数,问它们乘积的末尾有多少个零。

算法解释

用Python处理大数

直接连乘:几千位的大数

然后统计末尾的0

用C++编码 

10=2*5,统计5的个数,就是尾零的个数。

3 平方和

sum = 0
for i in range(1,2020):
    s = str(i)
    if '2' in s or '0' in s or '1' in s or '9' in s:
        sum += i*i
print(sum)

2658417853

解题技巧 

不需要什么算法的题目

只需要学过编程语言就能做

考核思维、逻辑、编程能力

“模拟题、构造题、思维题、找规律题”,统称为“杂题”

出现在比赛中,最重要的是得分点

杂题:可能比较简单,也可能比较难

4 切面条

算法解释

#求弯的数量
wan = 1
for i in range(10):
    wan *=2
#拐弯的数量等于2^n-1
#面条的数量等于弯的数量+2
print(wan+1)

1025

5 贪心问题——付账问题 

思路

如果每人带的钱够多,人均完全一样,bi=S/n=avg,标准差X=0。

不过总会出现有人带的钱不够,分两种情况讨论:

(1)第i人带的钱不够平均数avg,他只能出他带的全部钱ai;

(2)第i人带的钱比平均数avg多,他可以多摊一些。

求解步骤

(1)对ai从小到大排序;

(2)前一部分人的钱不够,那么就出他们所有的钱;

(3)从总付钱数中扣除前一部分人出的钱,得剩余钱数为s',以及后一部分人的出钱平均数avg'

(4) 后一部分人的钱多,他们多出一些,怎么出?这部分人也分两类

(i)比较有钱的,但是他的钱不够avg',那么他的钱还是要全出;

(ii)非常有钱的,不管怎么摊他都有富余。

from math import*
n,s = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
avg=s/n
sum=0
for i in range(n):
    if a[i]*(n-i) < s:
        sum += pow(a[i]-avg,2)
        s -= a[i]
    else:
        cur_avg = s/(n-i); #更新平均出钱数
        sum += pow(cur_avg-avg,2)*(n-i)
        break
print("{:.4f}".format(sqrt(sum/(n))))
题名题号

日期问题

103

四平方和

122

奇怪的数列

136

数位递增的数

145

反倍数

152

最大距离

155

积木

163

等腰三角形

171

缩位求和

181

Fibonacci数列

200

分糖果

218

k倍区间

97

图形排版

104

冰雹数

128

机器人繁殖

140

三元组中心问题

146

洁净数

153

螺旋矩阵

156

倍数问题

168

递增三元组

172

特别数的和

191

打印十字图

206

日期问题

103

四平方和

122

奇怪的数列

136

数位递增的数

145

反倍数

152

最大距离

155

积木

163

等腰三角形

171

缩位求和

181

Fibonacci数列

200

分糖果

218

 

(2023年 3月2日 22:47  周一首次发布)


http://www.kler.cn/a/1886.html

相关文章:

  • 如何查看pad的console输出,以便我们更好的进行调试,查看并了解实际可能的问题。
  • SDMTSP:黑翅鸢算法(Black-winged kite algorithm,BKA)求解单仓库多旅行商问题,可以更改数据集和起点(MATLAB代码)
  • 《三角洲行动》游戏运行时提示“缺失kernel32.dll”:问题解析与解决方案
  • Git远程仓库的多人协作
  • 使用idea创建JDK8的SpringBoot项目
  • D102【python 接口自动化学习】- pytest进阶之fixture用法
  • 数据可视化
  • 数据库:mysql的主从复制实战
  • 版本管理工具git 与 svn 的区别具体有哪些?
  • UE实现地面动态交互效果
  • 大数据框架保姆级安装教程——Kafka(3.0.0)
  • 小白学Pytorch系列--Torch API (7)
  • Java单例模式写法
  • 差分运放公式推导-运算放大器
  • 初阶C语言:冒泡排序
  • typescript(元组、枚举、类、泛型)
  • mysql数据库常问面试题
  • 我的 System Verilog 学习记录(10)
  • CF1770E Koxia and Tree
  • 探索css渐变-实现饼图-加载图-灯柱
  • 【Java】UDP网络编程
  • 蓝桥杯算法全集之完全背包问题(动态规划算法)
  • 蓝桥杯真题——自动售水机
  • LeetCode:704. 二分查找
  • 区块链基本原理
  • 【jvm】JVM(三)JVM 垃圾回收算法详解(CMS、三色标记)