团体程序设计天梯赛PTA-SHU冲刺赛4. L22-L32

这是4.18 SHU备赛天梯赛的最后一场冲刺赛

10.病毒溯源

1.本题PTA中拓栈后会MTL，不拓栈会报非零返回

所以本题最好用栈模拟递归过程

2.源头得是入度为0的，也就是没有节点指向它

所以得设置inn是否有指向该节点

3.这题用dfs（用bfs的话不同队列之间的vis会相互影响，导致循环变异处理有问题）

4.须按字典序输出，直接数组比较即可，因为数组比较也是按照从左往右

import sys
sys.setrecursionlimit(1000)n=int(input())#病毒种类总数 0到n-1#from collections import defaultdictd={}
inn=[0]*n #记录被指向
for i in range(n):l=list(map(int,input().split()))d[i]=l[1:]for j in d[i]:if not inn[j]:inn[j]=1maxl=0
ans=[]
def dfs(b):global maxlglobal ansflag=0for j in d[b[-1]]:if vis[j]!=1:flag=1b2=b.copy()b2.append(j)vis[j]=1dfs(b2)vis[j]=0if not flag:#当前最长了if len(b)>maxl:maxl=len(b)ans=b.copy()elif len(b)==maxl:if b<ans:#字典序比较ans=b.copy()return
'''
for i in range(n):vis=[0]*nvis[i]=1dfs([i])
'''
for i in range(n):if not inn[i]:source=ibreakvis=[0]*n
vis[source]=1
dfs([source])print(len(ans))
print(*ans)'''   用bfs的话不同队列间的vis会被污染
def gei_nei(from collections import deque
def bfs(sta):q=deque([sta])vis=(sta)while q:cur=q.popleft()for nei in get_nei(cur):for i in range(n):bfs(i)
'''

11.清点代码库 

1.想将数组作为key的话得先tuple转为元组

2.对字典排序：先按值排序，即 x[1] , 然后对key排序 

dict=sorted( dict.items() , key = lambda x : ( -x[1],x[0] ) ) )

from collections import defaultdictn,m=map(int,input().split())d=defaultdict(int)for i in range(n):l=list(map(int,input().split()))d[tuple(l)]+=1#list不可作为键，转为元组
'''
d=sorted(d.items(),key=lambda x:(x[1],-sum(x[0])))#对items[1]即value进行排序#如果相同那么看key#因为要降序所以要-,且是元组，得sum
'''
d=sorted(d.items(),key=lambda x:(-x[1],x[0]))print(len(d))
'''
for i in range(-1,-len(d)-1,-1):print(d[i][1],*d[i][0])
'''
for a,b in d:print(b,*a)

 12.哲哲打游戏

 这题看着像用栈，但其实是用字典存储存档

注意：“第”是从1开始的

n,m=map(int,input().split())ma={}
for i in range(1,n+1):l=list(map(int,input().split()))k=l[0]ma[i]=l[1:]#从1开始?save={}
now=1for i in range(m):temp=list(map(int,input().split()))if temp[0]==1:save[temp[1]]=nowprint(now)elif temp[0]==2:now=save[temp[1]]else:now=ma[now][temp[1]-1]#第j个：从1开始？print(now)

 14.还原文件

我的感觉是得从大数组里面找小数组的匹配索引，所以用了KMP但是没过全部

n=int(input())
l=list(map(int,input().split()))
q=int(input())T=[]
for i in range(q):temp=list(map(int,input().split()))T.append((tuple(temp[1:]),i+1))res=[]for t,i in T:k=len(t)for j in range(n-k+1):if tuple(l[j:j+k])==t:res.append((j,i))break
res.sort()for i in range(q-1):print(res[i][1],end=' ')print(res[-1][1])