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

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