目录

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))))

（2023年 3月2日 22:47  周一首次发布）