题解 | #牛客小白月赛60题解#

小竹与妈妈

https://ac.nowcoder.com/acm/contest/45670/A

以下代码均通过pypy3 ac

由题意可知，设年龄为k，那么有a×k+b=x，解方程即可

a,b,x=map(int,input().split())
print((x-b)//a)

B走丢的小竹

一共n个门，如过通向b的门有p个，那么这一次查询的答案就是n-p，建立数组统计通向每个房间的门的数量即可

n,m,q=map(int,input().split())
a=[0]+list(map(int,input().split()))
count=[0]*(m+5)
for aa in a:
    count[aa]+=1
for i in range(q):
    b=int(input())
    print(n-count[b])

C小竹关禁闭

建立数组ans，其中ans[i]表示的是最后一个利用的绳子不大于i的时候的最长总长度，那么，对于每一个i，就有ans[i]=max(ans[i-1],l[i]+ans[i-k-1])，动态规划即可

n,k=map(int,input().split())
l=list(map(int,input().split()))
ans=l[0:k+1]
for i in range(1+k,len(l)):
    ans.append(max(ans[-1],l[i]+max(ans[:i-k])))
print(max(ans))

D游戏购买！

首先BFS预处理求出起点和中间（小胖和小猪家）分别到每个商店的最短距离，然后枚举所有符合条件的商店位置，每个商店到两家的距离之和就是距离，所有这样的距离求和即可

from typing import *
from collections import *
move=[[0,1],[0,-1],[1,0],[-1,0]]
def get(a:int,b:int,grid:List[List[int]])->List[List[int]]:
    q=deque([[a-1,b-1,0]])
    ans=[[-1]*2000 for i in range(2000)]
    ans[a-1][b-1]=0
    while q:
        arr=q.popleft()
        for m in move:
            x,y=arr[0]+m[0],arr[1]+m[1]
            if x<0 or x>=len(grid) or y<0 or y>=len(grid[0]) or ans[x][y]>=0 or grid[x][y]==-1:
                continue
            ans[x][y]=arr[2]+1
            q.append([x,y,arr[2]+1])
    return ans
n,m,x=map(int,input().split())
sx,sy,ex,ey=map(int,input().split())
grid=[]
for i in range(n):
    grid.append(list(map(int,input().split())))
ans=1000000
d1,d2=get(sx,sy,grid),get(ex,ey,grid)
for i in range(n):
    for j in range(m):
        if d1[i][j]>=0 and d2[i][j]>=0 and grid[i][j]>x:
            ans=min(ans,d1[i][j]+d2[i][j])
print(-1 if ans==1000000 else ans)

E寻找小竹！

这是一棵树，也就是说，但是建立边的时候，需要判断一下边两头的节点是否为互为优雅，也就是他们的最大公约数是否有至少俩不同的质因数，那么就需要先跑一边质数筛，同时标记（singal）一下质数的若干次方这些数，然后建图要保证两头的gcd不是质数也不是那些singal，之后BFS寻找最大连通分量即可

import math
from collections import *
isPrime=[1]*(10**6*6)
singal=[0]*(10**6*6)
singal[1]=1
for i in range(2,10**6*5+5):
    if isPrime[i]:
        for k in range(2,66):
            if i**k>=10**6*5+5:
                break
            singal[i**k]=1
        for k in range(2,10**7):
            if i*k>=10**6*5+5:
                break
            isPrime[i*k]=0
n=int(input())
a=[0]+list(map(int,input().split()))
path=[[] for i in range(n+5)]
for i in range(n-1):
    x,y=map(int,input().split())
    g=math.gcd(a[x],a[y])
    if not isPrime[g] and not singal[g]:
        path[x].append(y)
        path[y].append(x)
has=[0]*(n+5)
ans=0
for i in range(n+1):
    if not has[i]:
        count=1
        has[i]=1
        q=deque([i])
        while q:
            b=q.popleft()
            for c in path[b]:
                if not has[c]:
                    count+=1
                    q.append(c)
                    has[c]=1
        ans=max(ans,count)
print(ans)

F被抓住的小竹

题意没读懂，看着别人的题解敲得代码。。。。式子还是很简单的

mod=10**9+7
fac=[1]
for i in range(1,100005):
    fac.append(i*fac[-1]%mod)
t=int(input())
for i in range(t):
    n=int(input())
    print((n+3)*(n+2)*(n+1)*n*n*n*(n-1)*(n-1)//96*fac[n-2]%mod)