🤡前言🤡

分享几个基础算法使用Python实现的方式以及几道简单的算法题目。

时间调整：超级简单的一个编程题

二进制数：求十进制数在二进制下的位数

回文素数：判断回文素数,打表法yyds

字母距离：求解字符串中的字母距离

CTF：模拟+计算

哈弗曼树：计算哈夫曼数的权值

抽奖：模拟+计算

前缀最值&后缀最值：空间换时间

纯质数求解：Python实现统计数字中包含的数

花园灌溉：BFS暴力搜索

💟时间调整💞

💗问题描述💗

问题描述

 现在时间是 a 点 b 分，请问 t 分钟后，是几点几分？

输入格式

 输入的第一行包含一个整数 a。

 第二行包含一个整数 b。

 第三行包含一个整数 t。

输出格式

 输出第一行包含一个整数，表示结果是几点。

 第二行包含一个整数，表示结果是几分。

样例输入

3

20

165

样例输出

6

5

样例输入

3

20

175

样例输出

6

15

数据规模和约定

 对于所有评测用例，0 <= a <= 23, 0 <= b <= 59, 0 <= t, t 分钟后还是在当天

💗问题分析💗

将现在的分钟与给的分钟相加，然后取余60得到的就是分钟数,除以60得到的就是小时数。

将新的小时数与旧的相加，得到的就是最终的结果。

💗代码实现💗

a=int(input())
b=int(input())
t=int(input())
a+=(b+t)//60
b=(b+t)%60
print(a)
print(b)

💟二进制数💞

🧡问题描述🧡

问题描述

 小明要用二进制来表示 1 到 10000 的所有整数，要求不同的整数用不同的二进制数表示，请问，为了表示 1 到 10000 的所有整数，至少需要多少个二进制位？

答案提交

 这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

 这题老实说误导了很久，总以为是要求1-10000转成二进制总共多少位，

 结果是14

🧡问题分析🧡

使用我们上篇博客提到过的不同进制之间转换,这道题使用Pyhton实现起来极为简单,使用C艹的话要求10000的二进制长度。实现方法就是对2进行取余。

🧡代码实现🧡

print(len(bin(10000)[2:]))
• 1

💟回文素数💞

💛问题描述💛

求出大于或等于 N 的最小回文素数。

回顾一下，如果一个数大于 1，且其因数只有 1 和它自身，那么这个数是素数。

例如，2，3，5，7，11 以及 13 是素数。

回顾一下，如果一个数从左往右读与从右往左读是一样的，那么这个数是回文数。

例如，12321 是回文数。

示例 1：

输入：6

输出：7

示例 2：

输入：8

输出：11

示例 3：

输入：13

输出：101

提示：

1 <= N <= 10^8

答案肯定存在，且小于 2 * 10^8

💛问题分析💛

使用Python实现这个的话属实有点吃力,在这给大家扩展一下思维,题目问的是1-2亿之间的素数回文数

既要满足两个条件,在数值很大的时候回文数是比较稀少的,所以我们可以先进行筛选,将1-2亿内的素数回文数直接筛出来,本题中使用的是埃氏筛,也就是注释的部分。全找出来可能需要几秒,我们不担心,将所有符合条件的数据打进表之后，直接将表复制进你要提交的程序,然后遍历就好。1-2亿内才有2千多个符合条件的数据。

由于这个表比较长,在这里就不直接粘进代码了。

💛代码实现💛

from math import sqrt
# 打表（这些操作不要出现在所提交的程序内）
# def F(n):
#     return str(n)==str(n)[::-1]
# # 打表法
# ansls=[]
# templs=[]
# ans=[True]*int(2*1e8+1)
# ans[0]=False
# ans[1]=False
# for i in range(2,int(sqrt(2*1e8))+1):
#     if ans[i]:
#         for j in range(i*i,int(2*1e8)+1,i):
#             ans[j]=False
# for i in range(int(2*1e8)):
#     if ans[i]==True:
#         templs.append(i)
# for i in templs:
#     if F(i):
#         ansls.append(i)
# print(len(ansls))
# print(ansls)
# 将上面得到的结果ansls中的数据直接复制过来。
ansls=[...]
n=int(input())
for i in ansls:
    if i>=n:
        print(i)
        break

💟字母距离💞

💚问题描述💚

问题描述

 两个字母之间的距离定义为它们在字母表中位置的距离。例如 A 和 C 的距离为 2，L 和 Q 的距离为 5。

 对于一个字符串，我们称字符串中两两字符之间的距离之和为字符串的内部距离。

 例如：ZOO 的内部距离为 22，其中 Z 和 O 的距离为 11。

 请问，LANQIAO 的内部距离是多少？

答案提交

 这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

我们可以改写一下输入任意长度字符,判断其内部距离,字符串长度小于10w

这是一个往届蓝桥杯真题的填空题,但是我们不妨将其改写成一下

参考结果

WATJKJDXRGZNXYTW 1132

LANQIAO 162

💚问题分析💚

每个字母之间的间隔使用的是ASCII表中的距离,比如A为65,Z为90，AZ之间的距离就是25，Z与A之间的距离也是25,如果数据比较多的话可以将其写进字典,然后计算,26种字母关于个数的笛卡尔积。应该有26*26种情况,在计算A-Z距离与Z-A距离时明显重复计算了所以在得到的结果应该除以2

💚代码实现💚

s=input()
dic={chr(k):0 for k in range(65,91)}
for i in s:
    dic[i]+=1
ans=[0]*26
i=0
for k1 in dic:
    for k2 in dic:
        if dic[k1]!=0 and dic[k2]!=0 and k1!=k2:
            ans[i]+=(dic[k2]*dic[k1]*abs(ord(k1)-ord(k2)))
    i+=1
print(sum(ans)//2)

💟CTF💞

💙问题描述💙

Description

在迷迷糊糊的进入大学以后，你决定参加竞赛出人头地，但是身处机算机学院的你，却发现竞赛并不等于电竞，你左选右选，发现了acm和ctf，一直想成为黑客的你，决定去ctf那里学习一下，但是当ctf要学的东西真是太多辣，pwn,web,逆向…，作为萌新的你决定多刷题。

学长给你指定了一个学习计划，考虑到计算机的本质是个二进制，所以你将在2^1

2

1天内每天刷一题，

22 天内每天刷两题,即第1,2天每天刷一题，第 3 到 6 天每天刷两题，2x

天每天刷xx题,以此类推，有算法基础的你决定写一个程序来看看自己在规定的天数内到底要写几道题

Input

一个整数 tt 表示天数(1 <=t <= 10^7)(1≤t≤10

7

)。

Output

一个整数xx表示要刷的题目数量。

Sample Input

1

9

Sample Output

1

19

💙问题分析💙

刚开始计算的时候循环内进行题目计数使用的是加法（也就是每一天写多少道题）,提交的时候超时

后面优化后是按时间段进行计算,最后得到的结果减去超出的天数乘以每天的写题量。

💙代码实现💙

# 暴力
# n=int(input())
# day=0
# ans=0
# k=0
# i=1
# if n==1:
#     print(1)
# elif n==2:
#     print(2)
# else:
#     while day<n:
#         i*=2
#         k+=1
#         for x in range(0,i):
#             ans+=k
#             day+=1
#             if day==n:
#                 break
#     print(ans)
# 优化一下
n=int(input())
day=0
ans=0
k=0
i=1
if n==1:
    print(1)
elif n==2:
    print(2)
else:
    while day<n:
        i*=2
        k+=1
        ans+=k*i
        day+=i
    ans-=(day-n)*k
    print(ans)

💟Huffuman树💞

💜问题描述💜

问题描述

 Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。

 给出一列数{pi}={p0, p1, …, pn-1}，用这列数构造Huffman树的过程如下：

 1. 找到{pi}中最小的两个数，设为pa和pb，将pa和pb从{pi}中删除掉，然后将它们的和加入到{pi}中。这个过程的费用记为pa + pb。

 2. 重复步骤1，直到{pi}中只剩下一个数。

 在上面的操作过程中，把所有的费用相加，就得到了构造Huffman树的总费用。

 本题任务：对于给定的一个数列，现在请你求出用该数列构造Huffman树的总费用。

例如，对于数列{pi}={5, 3, 8, 2, 9}，Huffman树的构造过程如下：

 1. 找到{5, 3, 8, 2, 9}中最小的两个数，分别是2和3，从{pi}中删除它们并将和5加入，得到{5, 8, 9, 5}，费用为5。

 2. 找到{5, 8, 9, 5}中最小的两个数，分别是5和5，从{pi}中删除它们并将和10加入，得到{8, 9, 10}，费用为10。

 3. 找到{8, 9, 10}中最小的两个数，分别是8和9，从{pi}中删除它们并将和17加入，得到{10, 17}，费用为17。

 4. 找到{10, 17}中最小的两个数，分别是10和17，从{pi}中删除它们并将和27加入，得到{27}，费用为27。

 5. 现在，数列中只剩下一个数27，构造过程结束，总费用为5+10+17+27=59。

输入格式

 输入的第一行包含一个正整数n（n<=100）。

 接下来是n个正整数，表示p0, p1, …, pn-1，每个数不超过1000。

输出格式

 输出用这些数构造Huffman树的总费用。

样例输入

5

5 3 8 2 9

样例输出

59

💜问题分析💜

这个题目让我刷新了对哈弗曼树的认知，原来是以为哈夫曼数计算权值的时候只能使用节点权值乘以他的距离,但是还可以实现的方式是从最底层进行加,每次累加最小的两个节点，当加到根节点的时候,权值也就计算出来了。

💜代码实现💜

n=int(input())
ls=list(map(int,input().split()))
ans=[]
while len(ls)>1:
    ls.sort(reverse=True)
    temp=ls.pop()+ls.pop()
    ls.append(temp)
    ans.append(temp)
print(sum(ans))

💟抽奖💞

🤎问题描述🤎

Description

在终于熬过了高中之后，你进入了大学，你听信了大人们的谎言，上了大学就轻松了，实际上你发现大学比高中更卷了。

但是！你已经佛系了起来，凭借着高中学过oi，在大学开始了摸鱼，而一直打LOL的你，最近发现了原神这一款游戏也很有意思，

而且作为lsp的你，对于里面的老婆你表示你全都要，但是为了计算好你怎么把原石投入池子，你需要好好计划一番。

你只喜欢up池，你当前已经拥有了xx颗原石,00个星辉，假设你不是很非也不是很欧，

每10发平均可以获得3个星辉(注意每满十发才可获得3星辉，1～9发无星辉，10～19发3星辉)，

根据原神的规则，每160颗原石可以抽一发，每5个星辉可以抽一发，作为大学生的你并没有太多钱来氪金，所以你得算一算目前到底可以抽多少发。

Input

一个整数xx，表示xx颗原石，(1 <= x <= 10^8)。

Output

一个整数nn，表示你可以抽多少发。

Sample Input 1

3200

Sample Output 1

21

🤎问题分析🤎

进行抽奖,最先应该考虑使用原石进行抽奖,然后用原石抽奖会得到许多的星辉,再使用星辉进行抽奖

星辉抽奖得到一定的抽奖次数后又可以得到星辉,就这样利滚利,抽奖的次数也就越来越多,直到星辉抽到不够5,跳出循环。

🤎代码实现🤎

x=int(input())
num=0
n=x//160
num=3*(n//10)
while num:
    if num-5>=0:
        n+=1
        if n%10==0:
            num+=3
        num-=5
    else:
        break
print(n)    

💟前缀最值&后缀最值💞

💝问题描述💝

给定一个序列,求该序列的浅前缀最小值,前缀最大值。

给定一个序列,求该序列的浅后缀最小值,后缀最大值。

💝问题分析💝

在进行线性动态规划的时候可能有需求

下一期应该是动态规划专题。这个作为铺垫

当然这只是求解思路，进行实际问题求解的时候还要看题目要求

然后定边界的大小。

💝代码实现💝

前缀最值

ls=[2,1,2,31,23,12,3,12,3,12,3,13,1,23,-1,2,31,3,1,4,2,42,14,2,31,4,53,4,53,4,6,45,7,6,5,87]
# 前缀最大值
ans=[0]*len(ls)
ans[0]=ls[0]
i=1
while i<len(ls):
    ans[i]=max(ans[i-1],ls[i-1])
    i+=1
n=int(input(“请输入要求前缀最大值数的个数”))
t=[]
for i in range(n):
    t.append(int(input()))
for i in t:
    print(ans[i])
# 前缀最小值
ans=[0]*len(ls)
ans[0]=ls[0]
for i in range(1,len(ls)):
    ans[i]=min(ans[i-1],ls[i-1])
n=int(input(“请输入要求前缀最小值数的个数”))
t=[]
for i in range(n):
    t.append(int(input()))
for i in t:
    print(ans[i])

后缀最值

ls=[1,1,2,31,23,12,3,12,3,12,3,13,1,23,1,2,31,3,1,4,2,42,14,2,31,4,53,4,53,4,6,45,7,6,5,87]
#给定一个序列,n个下标,输出下标后缀的最大值
# n=len(ls)
# ans=[0]*n
# ans[n-1]=ls[n-1]
# for i in range(n-2,-1,-1):
#     ans[i]=max(ans[i+1],ls[i+1])
# print(ans)
# 给定一个序列,n个下标,输出下标后缀最小值
n=len(ls)
ans=[0]*n
ans[n-1]=ls[n-1]
for i in range(n-2,-1,-1):
    ans[i]=min(ans[i+1],ls[i+1])
print(ans)

💟纯质数求解💞

🖤问题描述🖤

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

如果一个正整数只有 1 和它本身两个约数，则称为一个质数（又称素数）。

前几个质数是：2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, · · · 。

如果一个质数的所有十进制数位都是质数，我们称它为纯质数。

例如：2,3, 5, 7, 23, 37 都是纯质数，而 11, 13, 17, 19, 29, 31不是纯质数。

当然 1, 4, 35 也不是纯质数。请问，在 1到 20210605 中，有多少个纯质数？

🖤问题分析🖤

纯质数求解,在计算每一位的时候,只有2，3，5，7四种情况,只要有一位不是其中之一就代表

该数不是纯质数。就应该舍弃掉。带1或者0的肯定不是可以筛掉一大部分,由于是填空题这里就不再优化了，只有13w数据量,不出5秒计算完毕。

🖤代码实现🖤

import math
def judge(num):
    for i in range(2,int(math.sqrt(num))+1):
        if num%i==0:
            return False
    return True
ls=[2,3,5,7]
ans=0
for i in range(1,20210606):
    if str(i).count('1')!=0 or str(i).count('0')!=0:
        continue
    if not judge(i):
        continue
    flag=True
    j=i
    while j:
        t=j%10
        j//=10
        if t not in ls:
            flag=False
            break
    if not flag:
        continue
    else:
        ans+=1

💟花园灌溉💞

🤍问题描述🤍

题目描述

小蓝负责花园的灌溉工作。花园可以看成一个n行m列的方格图形。中间有一部分位置上安装有出水管。

小蓝可以控制一个按钮同时打开所有的出水管，打开时，有出水管的位置可以被认为已经灌溉好。

每经过一分钟，水就会向四面扩展一个方格，被扩展到的方格可以被认为已经灌溉好。

即如果前一分钟某一个方格被灌溉好，则下一分钟它上下左右的四个方格也被灌溉好。

给定花园水管的位置，请问 k 分钟后，有多少个方格被灌溉好？

输入描述

输入的第一行包含两个整数 n, m。

第二行包含一个整数 t，表示出水管的数量。

接下来 t行描述出水管的位置，其中第 i 行包含两个数 r, c 表示第 r行第 c 列有一个排水管。

接下来一行包含一个整数k。

其中，1≤n,m≤100,1≤t≤10,1≤k≤100。

输出描述

输出一个整数，表示答案。

输入输出样例

示例 1

输入：

3 6

2

2 2

3 4

1

输出：

9

🤍问题分析🤍

这个题目是今天最难得一个题目了,但是其在该类型的题中只能算是入门题。

实现之前需要先创建矩阵并初始化，然后将响应位置的花园进行填充,对于每个位置只考虑上下左右

如果没有被灌溉就进行灌溉。敢这么写主要是给定的数值范围很小。直接暴力搜索可以蒙混过关。

🤍代码实现🤍

n,m=map(int,input().split())
arr=[[0 for i in range(m)] for j in range(n)]
ans=0
ls=[]
t=int(input())
for k in range(t):
    i,j=map(int,input().split())
    i-=1
    j-=1
    arr[i][j]=1
    ls.append([i,j])
    ans+=1
k=int(input())
for i in range(k):
    temp=ls.copy()
    while temp:
        x=temp.pop(0)
        if x[0]-1>=0 and arr[x[0]-1][x[1]]==0:
            arr[x[0]-1][x[1]]=1
            ls.append([x[0]-1,x[1]])
            ans+=1
        if x[0]+1 <n and arr[x[0]+1][x[1]]==0:
            arr[x[0]+1][x[1]]=1
            ls.append([x[0]+1,x[1]])
            ans+=1
        if x[1]-1>=0 and arr[x[0]][x[1]-1]==0:
            arr[x[0]][x[1]-1]=1
            ls.append([x[0],x[1]-1])
            ans+=1
        if x[1]+1<m and arr[x[0]][x[1]+1]==0:
            arr[x[0]][x[1]+1]=1
            ls.append([x[0],x[1]+1])
            ans+=1
print(ans)