第15届蓝桥杯 第二场

总结下代码

一、进制

32

# 进制问题
n = 11#n进制
#讲数进制分解
#输入x，为n进制
def check(x,n):
    res = ""#当前进制的表示
    flag = True
    while x:
        num= x%n
        if num>9:
            flag = False
        if 0<=num <=9:
            res= chr(num+ord('0'))+res
        else:
            res = chr(num-10 +ord('a'))+res 
        x = x//n#变小
    print(res)
    return flag

for i in range(11,37):
    if (check(8100178706957568,i)):
        print(f"x = {i}")
        break

二 逆序对的期望

枚举所有情况，统计计算逆序对的数量
65.33

# 逆序对的期望
# 循环选择2个数，然后计算下平均


A = [ i for i in range(0,52)]
print(A)
cnt = 0
ans = 0

def get(A,n):#计算逆序数
    res = 0
    for i in range(1,n):#
        for j in range(1,i):
            if A[j]>A[i]:
                res+=1
    return res

B = [ i for i in range(0,52)]
for i in range(1,52):#一个点
    for j in range(1,52):#有边
        if i!=j:


            for l in range(1,52):
                for r in range(1,52):
                    if l!=r:
                        A = B[:] #初始化
                        A[i],A[j] = A[j],A[i] #第一次
                        A[l],A[r] = A[r],A[l]
                        cnt+=1 #1次交换
                        #计算逆序数
                        ans +=get(A,52)
print(ans/cnt)                

三 传送阵

暴力骗分

# p3
# 线性问题，
# n个起点，选择起点后顺序固定，可以进行一次临近节点扩展
# 找出最长的线路，拓扑排序
#dfs分情况：走当前，走左边，走右边。能够走两边的次数只有1次。
#从入度为0的位置找，每个点为起点求最长路径，
#求完后初始化数组
N = int(1e6+10)
n = int(input())

A = [0]*N
A[1:n+1] = list(map(int,input().split()))

ans = 0
#输入，当前的点，可以转移邻近的次数
def  dfs(u,cnt):
    #边界
    if st[u]:
        return 0 
    c = 1#本次的长度 
    t = 0
    st[u] = True 
    if  u>1 and cnt>0 and  (not st[u-1]):#没有访问
        t = max(dfs(u-1,cnt-1),t)
    if u<n and cnt >0 and (not st[u+1]):
        t = max(t,dfs(u+1,cnt-1))
    if not st[A[u]]:#下一个点未访问
        t= max(t,dfs(A[u],cnt))

    return c+t 

res = 0#最长路径

for i in range(1,n+1):
    st = [False for _ in range(N)]
    res= 0 #
    res = dfs(A[i],1)#以i为起点找
    ans = max(ans,res)
print(ans)

四 遗迹

跳过了

五 狡兔 k 窟

集合+dijkstra问题

# p5
#是树，地面是连通的
#地下有多个洞窟，不连通
# 这已经给了集合，不用并查集，但是要将一个集合的点距离设置为0
import heapq 
N = 5010
M = N*2 
e,ne,h,w = [0]*M,[0]*M,[-1]*N,[0]*M


idx = 0
n,m = map(int,input().split())
C = [0]*N
C[1:n+1] = list(map(int,input().split()))
p= [[]for _ in range(N)]#记录每个集合有哪些点
for i in range(1,n+1):
    if p[C[i]] is None:
        p[C[i]] = [i] #ci是集合
    else:
        p[C[i]].append(i)

def add(a,b,c):
    global idx
    e[idx] = b
    ne[idx] = h[a]
    h[a] = idx
    w[idx] = c
    idx+=1 

def dijkstra(start,end):
    dist[start] = 0#开始点
    q = []
    heapq.heappush(q,(0,start))#

    while q:#
        distance ,node = heapq.heappop(q)
        st[node] = True#
        i = h[node]#

        while i!=-1 :
            j = e[i]
            c = w[i]
            if not st[j] :
                dist[j] = min(dist[j],distance+c)
                heapq.heappush(q,(dist[j],j))
            i = ne[i]
        #遍历一个集合的

        if p[C[node]] is not None :
            for j in p[C[node]]:#
                if not st[j] and j !=node:
                    dist[j] = min(dist[j],distance)
                    heapq.heappush(q,(dist[j],j))
    return dist[end]
for _ in range(n-1):
    u,v = map(int,input().split())
    if C[u]==C[v]:
        val = 0
    else :
        val = 1
    add(u,v,val)
    add(u,v,val)

for _ in range(m):
    s,t = map(int,input().split())
    st = [False] *N
    dist = [1e9]*N #到每个点的距离
    res = dijkstra(s,t)
    print(res)
#2.5*10^7 8 20

六 装修

贪心做的，不能证明，但是可以过样例

#

N = int(1e6+10)

n = int(input())

edge=[]
st = [False]*N #节点
for i in range(n-1):
    u,v,w = map(int,input().split())
    edge.append((u,v,w))

#边排序
s_edge = sorted(edge,key = lambda x:x[2],reverse = True)

ans = 0

for i in range(n-1):
    u,v ,w = s_edge[i]
    if (not st[u]) and (not st[v]):
        st[u],st[v] = True,True
        ans+=w
print(ans)

七 最强小队

双指针维护区间

#nlogn

# 子序列, 首末最大，中间小的区间大小
# 这样的区间中最长的一个，有点像区间DP
# 队列的结构。队列长度为区间长度
#维护的操作，队头大于后面任何数，处理 
#还需要维护区间最大值（子区间最大值）
# 首位大于子区间最大值才行(除了左边的)

N = int(1e5+10)

A = [0]*N 
n = int(input())

A[1:n+1] = list(map(int,input().split()))

q = []#队列
ans = 0
res = 0#区间次大值
q.append(A[1])
for i in range(2,n+1):
    if A[i]<q[0]:#可以进入
        q.append(A[i])
        #如果大于次大值的话，可以计算区间长度
        if A[i]>res or len(q)<=2:
            ans = max(ans,len(q))
    else:#比A[0]大的数来了，计算区间长度先
        ans = max(ans,len(q)+1)
        q= []#新的队列
        res = 0
        q.append(A[i])
    res = max(A[i],res)
    #区间最大值怎么算 
    #除了q[0]外最大值
print(ans)

八 最长上升子序列

没有时间做
去年估分40+。省一倒数，希望这次能省一
估分：5+0+3+0+10 +3+2 = 23