文章目录
🤡前言🤡
| 时隔多天又回到了百练成钢系列，博客更新可以间断但是学习可不能间断。最近临近期末比较忙更新博客的频率与质量都有所下降,不知道大家最近在忙啥呢可以评论区告诉一下博主嗷。本期给大家分享几个感觉不错的算法题！学习计算机无论什么方向、什么编程语言都离不开算法这一说，精妙的算法往往是伟人的智慧结晶。站在巨人的肩膀上将会看到别致的风景。下面开始正题吧。 |
预览：
| DNA | 格式化输入输出，找输出规律 |
| 蛇形矩阵 | 找数字与数组下标规律 |
| Huffuman树 | 哈夫曼树权值的计算方法 |
| K-进制数 | 组合数的一种变换，强烈推荐学习 |
| K倍区间 | 前缀和与取模同余知识点，吐血推荐 |
| 交换瓶子 | 将一个实际问题抽象为一个图论问题，将复杂问题简单化 |
| 第几个幸运数 | 枚举组合数 |
| 四平方和 | 使用判断条件消除一部分循环。思想不错 |
| The 3n + 1 problem | 前缀和的思想解决一个实际的问题。 |
| 大数乘法 | 数值乘法计算的模拟，锻炼思维，理解乘法计算过程。 |
💟DNA💞
🧡问题描述🧡
题目描述
小强从小就喜欢生命科学，他总是好奇花草鸟兽从哪里来的。
终于， 小强上中学了，接触到了神圣的名词–DNA.它有一个双螺旋的结构。
这让一根筋的小强抓破头皮，“要是能画出来就好了” 小强喊道。现在就请你帮助他吧
输入
输入包含多组测试数据。第一个整数N（N<=15）,N表示组数，每组数据包含两个整数a,b。
a表示一个单位的DNA串的行数，a为奇数且 3<=a<=39。b表示重复度(1<=b<=20)。
输出
输出DNA的形状，每组输出间有一空行。
样例输入
2
3 1
5 4
样例输出
🧡问题分析🧡
格式化打印输出即可，可以在演算纸上先画一画。我在这里的处理方式是进行分段处理
想要提出共有的特征进行循环需要先分析每一段的特征以下图为例
每一个小格中的样式都相同所以可以将其作为共有特征进行提取
最上面一行先打印出来。然后对剩下的循环迭代即可（其他方法可以自己试一下）
🧡代码实现🧡
def PrintDNA(n):
if n>1:
# 先打印上一半
for i in range((n-1)//2-1):
print(" "*(i+1)+"X"+" "*(n-2*(i+1)-2)+"X"+" "*(i+1))
# 打印最中间的一点
print(" "*((n-1)//2)+"X"+" "*((n-1)//2))
# 打印下半段
for i in range((n+1)//2-1):
print(" "*((n-1)//2-i-1)+"X"+" "*(2*i+1)+"X"+" "*((n-1)//2-i-1))
else:
print("X")
x=int(input())
for i in range(x):
n,m=map(int,input().split())
print("X"+" "*(n-2)+"X")
for i in range(m):
PrintDNA(n)
print()
💟蛇行矩阵💞
🖤问题描述🖤
题目描述
蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形。
输入
本题有多组数据，每组数据由一个正整数N组成。（N不大于100）
输出
对于每一组数据，输出一个N行的蛇形矩阵。两组输出之间不要额外的空行。矩阵三角中同一行的数字用一个空格分开。行尾不要多余的空格。
样例输入
5
样例输出
1 3 6 10 15
2 5 9 14
4 8 13
7 12
11
🖤问题分析🖤
这个蛇形矩阵相对我们常规说的回旋型的蛇形矩阵不怎么一样，原来的更像是蛇盘在了那里，这个像蛇在移动
处理这种题目的方法就是多进行观察，找找规律，我在写题目的时候找到的规律是第一行数据
以样例输出为例1,3,6,10,15.前后两个数的差依次增大1
然后从第一行某元素向左下角斜着看依次减1，由此我们可以书写一下代码：
🖤代码实现🖤
n=int(input())
ans=[[0]*n for i in range(n)]
for i in range(1,n+1):
ans[0][i-1]=i*(i+1)//2
# print(ans)
# 接下来从每一个数往下移动碰到左边的边之后结束
for i in range(n):
row=0
col=i
while col!=0 and row!=n:
ans[row+1][col-1]=ans[row][col]-1
row+=1
col-=1
for i in ans:
print(*[j for j in i if j!=0])
💟Huffuman树💞
💗问题描述💗
题目描述
Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。
给出一列数{pi}={p0, p1, …, pn-1}，用这列数构造Huffman树的过程如下：
- 找到{pi}中最小的两个数，设为pa和pb，将pa和pb从{pi}中删除掉，然后将它们的和加入到{pi}中。这个过程的费用记为pa + pb。
- 重复步骤1，直到{pi}中只剩下一个数。
在上面的操作过程中，把所有的费用相加，就得到了构造Huffman树的总费用。
本题任务：对于给定的一个数列，现在请你求出用该数列构造Huffman树的总费用。
例如，对于数列{pi}={5, 3, 8, 2, 9}，Huffman树的构造过程如下：- 找到{5, 3, 8, 2, 9}中最小的两个数，分别是2和3，从{pi}中删除它们并将和5加入，得到{5, 8, 9, 5}，费用为5。
- 找到{5, 8, 9, 5}中最小的两个数，分别是5和5，从{pi}中删除它们并将和10加入，得到{8, 9, 10}，费为10。
- 找到{8, 9, 10}中最小的两个数，分别是8和9，从{pi}中删除它们并将和17加入，得到{10, 17}，费用为17。
- 找到{10, 17}中最小的两个数，分别是10和17，从{pi}中删除它们并将和27加入，得到{27}，费用为27。
- 现在，数列中只剩下一个数27，构造过程结束，总费用为5+10+17+27=59。
输入
输入的第一行包含一个正整数n（n< =100）。
接下来是n个正整数，表示p0, p1, …, pn-1，每个数不超过1000。
输出
输出用这些数构造Huffman树的总费用。
样例输入
5
5 3 8 2 9
样例输出
59
💗问题分析💗
原来的时候分享过这个问题，当时被他这个求哈夫曼权值的思想吸引到了，只不过当时的代码没有AK所有数据，我也是今天才发现。发现之后瞬间对代码进行了翻新。现在总算是稳定了。题目中给的思路也比较清晰，直接按着每一步做就好了。
💗代码实现💗
def insert(a,ls):
index=0
if not ls or ls[0]>a:
ls.insert(0,a)
return
flag=False
for i in range(1,len(ls)):
if ls[i]>a:
index=i
flag=True
break
if flag:
ls.insert(index,a)
else:
ls.append(a)
n=int(input())
ls=list(map(int,input().split()))
ans=0
ls.sort()
# print(ls)
while len(ls)>1:
a=ls.pop(0)
b=ls.pop(0)
ans+=a+b
insert(a+b,ls)
print(ans)
💟K-进制数（组合数学）💞
💚问题描述💚
题目描述
考虑包含N位数字的K-进制数. 定义一个数有效, 如果其K-进制表示不包含两连续的0.
例:
1010230 是有效的7位数
1000198 无效
0001235 不是7位数, 而是4位数.
给定两个数N和K, 要求计算包含N位数字的有效K-进制数的总数.
假设2 <= K <= 10; 2 <= N; 4 <= N+K <= 18.
输入
两个十进制整数N和K
输出
十进制表示的结果
样例输入
2
10
样例输出
90
💚问题分析💚
按照常规的思路刚开始看到这种题目是不是很头大。写的代码要适合很多进制，要数清数中有几个0，刚开始就进制转换就要废好大的劲，进行完进制的转换还要枚举数零，这样干不错也要超时。别问我怎么知道的，刚开始我就这样想的。我们不妨观察一下题目中的数据，进制要求2-10，长度4-18。哦！我是不是可以利用高中学习的排列组合进行求解（插空法）？瞬间悟了悟了。
于是我有了以下思想：
一个符合要求的数一定不是以0开头
零位的个数一定小于等于非零位的个数：（如果大于非零的个数无论怎么排，要么0在最前面要么有两个0相邻）
对于n位的偶数而言：
零的个数一定小于n//2个，零可插入的位数一定是n//2个
对于n位奇数而言：
零的个数一定小于(n-1)//2个，零可插入的位置一定是(n+1)//2个
💚代码实现💚
# 全排列
def A(n):
ans=1
for i in range(1,n+1):
ans*=i
return ans
# 组合数
def C(n,m):
return (A(n))//(A(m)*A(n-m))
n=int(input())
k=int(input())
# 总数情况
ans=0
# tk代表零的个数
tk=0
if n%2==0:
tk=n//2
else:
tk=(n-1)//2
for i in range(tk+1):
# i代表零的个数从最开始的0到最后的tk
# 选取n-i个非零数后面的空位置插入i个零
# 其余n-i个位置放置的数据是除了零之外的（如果k进制那么他只能放[1,2,3,...,(k-1)]）因为k的时候要进位，0不可以放
# 故其余n-i个位置放置的数据都是只有k-1种情况。
ans+=C(n-i,i)*(k-1)**(n-i)
print(ans)
💟k倍区间（前缀和变形）💞
💙问题描述💙
问题描述
给定一个长度为N的数列，A1, A2, … AN，如果其中一段连续的子序列A[i], A[i+1], … A[j](i <= j)之和是K的倍数，
我们就称这个区间[i, j]是K倍区间。你能求出数列中总共有多少个K倍区间吗？
输入格式
第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)
输出格式
输出一个整数，代表K倍区间的数目。
样例输入
5 2
1
2
3
4
5
样例输出
6
💙问题分析💙
这个题目是一个典型的前缀和题目
有两种思路第一种是常规思路
第二个利用了数论的知识点
暴搜法：
我在这里直接将每两个点之间的和都算出来了（用二维列表进行存储）。
然后对二维列表进行遍历找出符合条件的数据。（详见代码）
前缀和+数论：
说这个方法之前先进行一下小的科普：如果一个数a取余k==3，那么(a+3k)取余k是不是还是3（想明白这个之后再往下看）
在前缀和数组中一个位置的数据为a，在他后面有一个位置数据为b
a%k==3并且b%k==3
那么（b-a）是不是可k的倍数？是当然是。那么a-b是不是一个符合条件的区间
现在问题就转化成了前缀和中同余位置如何组合的问题
显然如果1,2,3同余我们只能枚举出这三种情况1-2，1-3，2-3
细分的话是1有两种。2有一种；
我们在进行求和的时候写成2+1对于常规情况我们也会写成n+(n-1)+…1
但是期初我们不知道1会对应多少种情况。我们也不想多写循环进行迭代更新。
于是有了代码中的方式
n+(n-1)+…1与1+…(n-1)+n是等价的
我们可以从1开始加，直到同余位置数目的最大值n
💙代码实现💙
直接暴力搜索
n,k=map(int,input().split())
ans=0
# 数列
t=[int(input()) for i in range(n)]
# 存储任意区间和
ls=[[0]*n for i in range(n)]
for i in range(n):
ls[i][i]=t[i]
if t[i]%k==0:
ans+=1
for i in range(n-1):
for j in range(i,n-1):
ls[j+1][i]=ls[j][i]+t[j+1]
if ls[j+1][i]%k==0:
ans+=1
print(ans)
利用前缀和性质
n,k=map(int,input().split())
ans=[]
cnt=[0]*100000
t=0
for i in range(n):
t+=int(input())
ans.append(t%k)
count=0
for i in ans:
count+=cnt[i]
cnt[i]+=1
print(count+cnt[0])
💟交换瓶子(问题转化)💞
💜问题描述💜
有N个瓶子，编号 1 ~ N，放在架子上。
比如有5个瓶子：
2 1 3 5 4
要求每次拿起2个瓶子，交换它们的位置。
经过若干次后，使得瓶子的序号为：
1 2 3 4 5
对于这么简单的情况，显然，至少需要交换2次就可以复位。
如果瓶子更多呢？你可以通过编程来解决。
输入格式为两行：
第一行: 一个正整数N（N<10000）, 表示瓶子的数目
第二行：N个正整数，用空格分开，表示瓶子目前的排列情况。
输出数据为一行一个正整数，表示至少交换多少次，才能完成排序。
例如，输入：
5
3 1 2 5 4
程序应该输出：
3
再例如，输入：
5
5 4 3 2 1
程序应该输出：
2
💜问题分析💜
数组中的数据要排列成为
要排列成下标1,2,3,4,5,6,7,8,…
我们可以让下标1,2,3,4,5,6,7,8,…与之对应
下标1记录1
下标2记录2
下标3记录3
…
之间是一一对应的关系
但是存在1->2->3->1的情况
我们需要变为1->1
我们需要变为2->2
我们需要变为3->3
故我们可以先交换1,3的指向，然后交换2,3的指向。
如果称1->2->3->1为一个有三个元素的环
每次交换完毕都会多出来一个自环eg:1->1
直到所有元素都为自环就满足了题意。
一个元素必定只在一个圆环中出现
要把一个圆环中的n个元素全部变为自环需要n-1次交换
假设开始一共有k个圆环(都不是自环)，一共N个元素。
则将其全部变为自环至少需要交换N-k次
所以本问题转化为了求圆环个数的问题
💜代码实现💜
N=int(input())
ls=list(map(int,input().split()))
# 记录非自环圆环的数量
count=0
# 自环数量
count1=0
for i in range(N):
# 判断是否遍历过
if ls[i]!=-1:
# 自环
if ls[i]==i+1:
count1+=1
break
# 非自环
else:
t1=t2=i
while ls[t1]!=-1:
t2=ls[t1]-1
ls[t1]=-1
t1=t2
count+=1
# 出去自环外的所有元素N减去有的环数k就是结果
print(N-count1-count)
# 拓展：如果让所有元素之间都有联系应该如何做？(合并两个环只需交换一次，所以之间输出环的个数就好了)
print(count+count1)
💟第几个幸运数(算术基本定理)💞
🤎问题描述🤎
到x星球旅行的游客都被发给一个整数，作为游客编号。
x星的国王有个怪癖，他只喜欢数字3,5和7。
国王规定，游客的编号如果只含有因子：3,5,7,就可以获得一份奖品。
我们来看前10个幸运数字是：
3 5 7 9 15 21 25 27 35 45
因而第11个幸运数字是：49
小明领到了一个幸运数字 59084709587505，他去领奖的时候，
人家要求他准确地说出这是第几个幸运数字，否则领不到奖品。
请你帮小明计算一下，59084709587505是第几个幸运数字。
🤎问题分析🤎
3、5、7都是素数。刚看到题目时就想到了使用算术基本定理相关的知识去做，首先将59084709587505进行了分解。
分解成为3a*5b*7c的形式，然后对指数进行组合（后来发现这是一个错误的思路，假设目标数分解后为3a*5b*7c直接进行组合的话结果是a*b*c。但是结果并不包含3a+1*5b*7c-1这种情况。也就是说直接进行组合会漏掉许多情况）
正确的思路如下：
由于数据中只包含3,5,7三个因子，如果想计算出有几个比59084709587505小的数直接暴力搜索即可
指数是一种数值增长比较快的函数所以不用循环那么多次。暂定每个指数枚举20次。如果不够可以再扩大范围。
由此得到了正确的答案。
🤎代码实现🤎
x=59084709587505
ans=0
ls=[3,5,7]
for i in range(100):
for j in range(100):
for k in range(100):
if (7**i*5**j*3**k)<x:
ans+=1
else:
break
print(ans)
💟四平方和(利用判断抵消一层循环)💞
💛问题描述💛
四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多4个正整数的平方和。
如果把0包括进去，就正好可以表示为4个数的平方和。
比如：
5 = 0^2 + 0^2 + 1^2 + 2^2
7 = 1^2 + 1^2 + 1^2 + 2^2 （^符号表示乘方的意思）
对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对4个数排序：
0 <= a <= b <= c <= d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法
程序输入为一个正整数N (N<5000000)
要求输出4个非负整数，按从小到大排序，中间用空格分开
例如，输入：
5
则程序应该输出：
0 0 1 2
再例如，输入：
12
则程序应该输出：
0 2 2 2
再例如，输入：
773535
则程序应该输出：
1 1 267 838
资源约定：
峰值内存消耗 < 256M
CPU消耗 < 3000ms
tips;简单深搜
💛问题分析💛
题目要我们求出所有的情况。如果只求联合主键最大的情况的话我们可以进行每次从总数中移除一个最大可开方的数。（如下）
但是题目中要求的是我们将所有的情况按联合顺序枚举出来，于是我们可以按照从小到大的顺序进行枚举，四层循环每层控制一个变量（也就是每个变量控制题目要求的四位数中的一位）满足：a2*b2*c2*d2=目标数即可
这样做有可能会超时，首先应该想到减少循环层数。我们可以将表达式变换一下通过a2*b2*c2-目标数获取d2,如果剩余的数可以开方那么就是满足条件的d，否则就不满足。（代码部分是两个思路的代码）
💛代码实现💛
import math
# 给定一个n返回其包含的最大平方值与剩余值
def Look(n):
temp=int(math.sqrt(n))
return n-temp**2,temp
n=int(input())
for i in range(4):
n,ans=Look(n)
print(ans)
# 题目的意思是有0就不要输出1，有1就不要输出2
import math
n=int(input())
flag=False
# 终止条件写为int(math.sqrt(n))+1又减少了一部分时间
for i in range(int(math.sqrt(n))+1):
for j in range(i,int(math.sqrt(n))+1):
for k in range(j,int(math.sqrt(n))+1):
# 这么写的好处直接少搜了一轮，减少了相当一部分的时间
d=n-i**2-j**2-k**2
if d<=0:
break
d=math.sqrt(d)
if d==int(d):
print(i,j,k,int(d))
flag=True
break
if flag:
break
if flag:
break
💟The 3n + 1 problem💞
🤍问题描述🤍
题目描述
请考虑以下算法以生成数字序列。以整数 n 开头。如果 n 为偶数，则除以 2。如果 n 为奇数，则乘以 3 并加 1。
使用新值 n 重复此过程，并在 n = 1 时终止。
例如，将为 n = 22 生成以下数字序列： 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
推测（但尚未证明）对于每个整数 n，此算法将终止于 n = 1。
尽管如此，这个猜想仍然适用于至少1， 000， 000的所有整数。对于输入 n，n 的循环长度是生成的数量，最多包括 1。
在上面的示例中，循环长度 22 为 16。给定任意两个数字 i 和 j，您将确定 i 和 j 之间所有数字（包括两个端点）的最大循环长度。
输入
输入将由一系列整数对 i 和 j 组成，每行一对整数。所有整数将小于 1，000，000 且大于 0。
输出
对于每对输入整数 i 和 j，输出 i、j 的顺序与它们在输入中出现的顺序相同，然后是 i 和 j 之间整数的最大循环长度。
这三个数字应用一个空格分隔，所有三个数字都在一行上，每行输入都有一行输出。
样例输入
1 10
100 200
201 210
900 1000
样例输出
1 10 20
100 200 125
201 210 89
900 1000 174
🤍问题分析🤍
题目并不难，但是一个一个进行迭代的话必定超时
所以决定用一个数组存储计算结果（因为某个位置的循环长度可能会对后面数据提供积极的作用）
从低位依次向高位迭代,最后再查表即可得到结果。有点动态规划的意思。
🤍代码实现🤍
# 存放每个位置对应的长度数量
ls=[0]*1000010
ls[0]=0
ls[1]=0
ls[2]=1
# 直接生成表，方便以后查询
for i in range(2,1000001):
tempi=0
tempa=i
while tempa!=1:
# print(tempa)
if tempa>1000000:
break
if ls[tempa]!=0:
ls[i]=tempi+ls[tempa]
break
if tempa%2==0:
tempa//=2
else:
tempa=tempa*3+1
tempi+=1
# 查表
while True:
a,b=map(int,input().split())
if a>b:
ta,tb=b,a
else:
ta,tb=a,b
print(a,b,max(ls[ta:tb+1])+1)
💟大数乘法(将两个大数分段计算)💞
💝问题描述💝
对于32位字长的机器，大约超过20亿，用int类型就无法表示了，我们可以选择int64类型，但无论怎样扩展
固定的整数类型总是有表达的极限！如果对超级大整数进行精确运算呢？
一个简单的办法是：仅仅使用现有类型，但是把大整数的运算化解为若干小整数的运算，即所谓：“分块法”。
可以把大数分成多段（此处为2段）小数，然后用小数的多次运算组合表示一个大数。
可以根据int的承载能力规定小块的大小，比如要把int分成2段，则小块可取10000为上限值。
注意，小块在进行纵向累加后，需要进行进位校正。
💝问题分析💝
这个问题是我感觉最离谱的一个，在Python中天生支持大数运算。所以感觉不到底层进行大数计算多么伟大多么困难。
作为一种计算思想Python天生支持大数计算，但是我们还是要自己模拟模拟。重在提高自己嘛。
这个大数乘法的思想就是将数据进行分段，保证每一段不溢出的情况下进行计算。每次计算完毕会进行进位，合并
以保证每个区间都在合理可控的范围。计算的话与我们乘法竖式计算很相似：
在计算的时候一定要对准位数否则会计算错误；
💝代码实现💝
# 假设9位数不会int溢出
# 以10000为单位,也就是说最大的数值是9999*9999此时便不会产生int溢出的情况
step=10000
def mut(ls,n):
# 已知n不会超过9999
# 已知ls中的每一个数不会超过9999
# 直接对列表ls乘以n,得到的结果不会超过九位数
ls=[i*n for i in ls]
i=len(ls)-1
while i>0:
# 对相应区段进行计算，将超过10000的位进行进位，将10000以下的留给自己
# 然后改变对应位置的关系
ls[i-1]=ls[i]//step+ls[i-1]
ls[i]=ls[i]%step
i-=1
if ls[0]>=step:
ls.insert(0,ls[0]//step)
ls[1]=ls[1]%step
return ls
# 经过反转让低位在前面便于计算
n1=input()[::-1]
n2=input()[::-1]
n1ls=[]
n2ls=[]
# 将输进来的数分段存储（由于数据是反转后的所以进行拼接的时候还需要反转一次）
for i in range(0,len(n1),4):
n1ls.insert(0,int(n1[i:i+4][::-1]))
for i in range(0,len(n2),4):
n2ls.insert(0,int(n2[i:i+4][::-1]))
# 存储最终的结果
ans=[0]*(len(n1ls)+len(n2ls)+1)
# 迭代其中一个列表，使用mut函数计算结果
ansi=len(ans)-1
for i in n2ls[::-1]:
ls=mut(n1ls,i)
# 临时记录ans最末位的下标
tempi=ansi
while ls:
temp=ls.pop()
ans[tempi-1]=(ans[tempi]+temp)//step+ans[tempi-1]
ans[tempi]=(ans[tempi]+temp)%step
tempi-=1
ansi-=1
# 格式化标记
flag=True
# 打印输出结果
for i in ans:
if i==0 and flag:
continue
elif flag:
# 祛除前导0
print(i,end="")
flag=False
elif not flag:
print(str(i).rjust(len(str(step))-1,"0"),end="")
完啦！！
