算法刷题杂题

A

题目连接

n个人,从第一个开始传球,经过m次回到第一个人手里的方法数

做题思路:笨比方法:1作为root,建了棵二叉树,每次分裂出两个节点,然后再dfs,搜索路径数量(叶节点是1),超内存了

正确思路:dp[i][j] 表示传了i次在j手里的可能,判断一下1和n的边界情况

n,m=input().split()
n=int(n)
m=int(m)
dp=[[0 for _ in range(n)] for _ in range(m+1)]
# dp[i][j] 穿了i次在j手里的可能
dp[0][0]=1
for i in range(1,m+1):
    for j in range(n):
        if j==n-1:
            dp[i][j]=dp[i-1][0]+dp[i-1][j-1]
        elif j==0:
            dp[i][j]=dp[i-1][n-1]+dp[i-1][j+1]
        else:
            dp[i][j]=dp[i-1][j+1]+dp[i-1][j-1]
  
print(dp[m][0])

B

题目连接

n对果子,一堆堆合并,果子的数量是消耗的体力,求n堆合成一堆的最小体力

思路:哈夫曼树

import heapq

n=int(input())
nums=[]
numstr=input().split()
for i in range(n):
    heapq.heappush(nums,int(numstr[i]))
  
ans=0
while len(nums)!=1:
    a=heapq.heappop(nums)
    b=heapq.heappop(nums)
    temp=a+b
    ans+=temp
    heapq.heappush(nums,temp)
  
print(ans)

C

题目链接

一个矩阵,每个点有对应的值,从(0,0)走到(n,n),走两次,每次走过之后会把矩阵的值清零,问这两次能得到的最大值

思路:笨比方法:以为两次BFS就行,每次都拿到最大的,这样有可能本来上三角一次,下三角一次最大,但是第一次走最大路径把这个打破了,会导致上下三角有的没拿到

正确思路:f[i][j][h][k];表示两条路同时走，第一条路径走到(i,j)时，第二条走到（h,k）时的最大数字和；

n=int(input())

m=[[0]*(n+1) for _ in range(n+1)]

for _ in range(n*n):
    x,y,v=list(map(int,input().split()))
    if v==0 and x==0 and y==0:
        break
    m[x][y]=v

dp=[[[[0]*(n+1) for _ in range(n+1)] for _ in range(n+1)] for _ in range(n+1)]


for i in range(1,n+1):
    for j in range(1,n+1):
        for h in range(1,n+1):
            for k in range(1,n+1):
                dp[i][j][h][k]=max(
                    dp[i-1][j][h-1][k],
                    dp[i-1][j][h][k-1],
                    dp[i][j-1][h-1][k],
                    dp[i][j-1][h][k-1]
                )+m[i][j]+m[h][k]
                if i==h and j==k:
                    dp[i][j][h][k]-=m[h][k]
            
print(dp[n][n][n][n])

D

题目链接

一个数是两个质数的乘积,返回较大的质数

80%思路:从$n$到$n^{0.5}$遍历,余数为0就返回,80莫名其妙(答案错误),笨比,写的是$n^{0.5}$到$n$遍历了

正确思路:从$2$到$n^{0.5}$,余数为0,返回商

n=int(input())

right=int(n**0.5)
for i in range(2,right+1):
    if n%i==0:
        print(n//i)
        break

E

题目链接\

难,略

F

题目链接

n种不同面额的货币,但是有的面值能表示,有的面值不能表示,求最少只要几种货币,能和n种表示的面值一样

80%思路:如果n里面有的数能够被其他数表示,这个就是多余的,可以去掉(???抄别人100的代码也是80),判断一个数能不能被其他的表示有点背包的感觉

T=int(input())
# n=100
def check(x,lst):
    if len(lst)==0:
        return False
    dp=[False]*(x+1)
    dp[0]=True
    for num in lst:
        for index,item  in enumerate(dp):
            if index-num>=0:
                dp[index]|=dp[index-num]
        if dp[x]:
            return True
    return dp[x]
for _ in range(T):
    n=int(input())
    nums=list(map(int,input().split()))
    nums.sort(reverse=True)
    temp=0
    for index,item in enumerate(nums):
        if check(item,nums[index+1:]):
            temp+=1
    print(n-temp)

G

题目链接

n个囚犯,两个犯人中间有怨气值,把他们分成两个监狱,求一个监狱内怨气值最大的,如果监狱内的犯人之间没有怨气值,返回0

思路:不会,随便想的,想到并查集了,但是感觉更像二分图匹配,没做出来,0蛋

正确思路:并查集,但是不是两个有怨气的犯人之间,如果A和B有怨气,B和C有怨气,那么应该把A和C归并,B单独,先按照怨气值从大到小排序,如果这两个人在一个集里面了,那就说明不可避免了,

n,m=input().split()
n=int(n)
m=int(m)

parent=[-1]*(n+1)

def findx(x):
    if parent[x]!=-1:
        return findx(parent[x])
    return x

def merge(a,b):
    a_p=findx(a)
    b_p=findx(b)
    if a_p!=b_p:
        parent[a_p]=b_p

values=[]
for _ in range(m):
    a,b,c=list(map(int,input().split()))
    values.append((a,b,c))
  
values=sorted(values,key=lambda x:x[2],reverse=True)

disfriend=[0]*(n+1)

def solve():
    for a,b,c in values:
        if findx(a)==findx(b):
            print(c)
            return True
        if disfriend[a]==0:
            disfriend[a]=b
        else:
            merge(disfriend[a],b)
        if disfriend[b]==0:
            disfriend[b]=a
        else:
            merge(disfriend[b],a)
if not solve():
    print(0)

H

题目链接

在有向图G中，每条边的长度均为1，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：
1．路径上的所有点的出边所指向的点都直接或间接与终点连通。
2．在满足条件1的情况下使路径最短。

难,略

建双向边，对于正边和反边我们标记一下即可。
那么建完边后我们先从终点bfs一遍，只跑反向边，对于每个遍历到的边进行标记，这样我们就可以找出不能直接或间接到达终点的点。
得到这些点后，我们再遍历这些点的反向边的出边，将与这些点相连的点进行标记。
标记完后我们剩下的没有被第二次标记的点就是可以走的点。这时我们再从起点bfs一遍，只跑正向边，且不走被第二次标记过的点，那么第一次到达终点的时候就是可到达的最短路。

背包问题

背包问题

0-1背包

for (int i = 1; i <= N; ++i) {
    for (int j = 0; j <= V; ++j) {
        backpack[i][j] = backpack[i - 1][j];
        if (j >= cap[i]) {
            backpack[i][j] = Math.max(backpack[i][j], backpack[i - 1][j - cap[i]] + val[i]);
        }
    }
}

多重背包

for (int i = 1; i <= N; ++i) {
    for (int j = 0; j <= V; ++j) {
        backpack[i][j] = backpack[i - 1][j];
        for (int k = 1; k <= num[i]; ++k) {
            if (j >= k * cap[i]) {
                backpack[i][j] = Math.max(backpack[i][j], backpack[i - 1][j - k * cap[i]] + k * val[i]);
            }
        }
    }
}

完全背包

for (int i = 1; i <= N; ++i) {
    for (int k = 1; k * cap[i] <= V; ++k) {
        for (int j = V; j >= cap[i]; --j) {
            f[j] = Math.max(f[j], f[j - cap[i]] + val[i]);
        }
    }
}

动态规划补充

从集合的角度

有限集中的最优化

动态规划

01背包

完全背包

``

最长公共子序列

字符串编辑距离

最短路径

快速幂

# 矩阵相乘
def mul(A, B):
    # A:m*n, B:n*p  结果m*p
    m = len(A)
    n1 = len(A[0])
    n2 = len(B)
    p = len(B[0])
    if n1 !=n2:
        return
    n = n1= n2
    ans = []
    # 初始化ans
    for i in range(m):
        ans.append([0]*p) # 都用同一个变量row = [0]*p，会同时修改，所以不用同一个变量
 
    for i in range(m):
        for j in range(p):
            temp = 0
            for q in range(n):
                temp += A[i][q]*B[q][j]
                temp%=9999991
            ans[i][j] = temp
 
    return ans
 
 
def fib(n):
    if n==0:
        return 0
    elif n==1 or n==2:
        return 1
    base = [[1,1],[1,0]]
 
    n = n-2
    ans = [[1,0],[0,1]]
    while n:
        if n&1:
            ans = mul(base,ans)
        base = mul(base,base)
        n = n>>1
    # temp=mul([[1,1]],ans)
    # print(temp[0][0],ans[0][0] + ans[0][1])
    return ans[0][0] + ans[0][1]
 
if __name__=='__main__':
    # 前20个斐波那契数列
    # 0是第0个
    # 2023040313301730
    print(fib(2023040313301730)%9999991)
    # for i in range(20230403%1330173):
    #     print(fib(i),end=' ')

真题C语言网

真题官网