Skill Competition Player Notes

# 海陸雙拼筆記🐳🐒 ## :memo: SCL 模板 #### BST 二元搜尋樹 :::spoiler ```python=1 class tree(): def __init__(self): self.data=0 self.right=None self.left=None def create_tree(root,val): newnode=tree() newnode.data=val newnode.left=None newnode.right=None if root==None: root=newnode return root else: current=root while current!=None: backup=current if current.data>val: current=current.left else: current=current.right if backup.data>val: #adj[backup.data][val]=1 #adj[val][backup.data]=1 backup.left=newnode else: #adj[backup.data][val]=1 #adj[val][backup.data]=1 backup.right=newnode return root data=[5,454,456,1,5,6,46,46,649,1564,156,1464,1454,14,566] #adj=[[0]*101 for i in range(101)] ptr=None for i in range(len(data)): ptr=create_tree(ptr,data[i]) def inorder(ptr): if ptr!=None: inorder(ptr.left) print(ptr.data,end=" ") inorder(ptr.right) inorder(ptr) ``` ::: #### heap 堆積樹 :::spoiler ```python=1 num=[454,456478,4564,564,54,564,56,4,5678,79,455456,4,45,456,4,14,565,467,5325] num_size=len(num) def heapify(n,i): root=i l=i*2 r=i*2+1 if l<n and num[l]<num[root]: root=l if r<n and num[r]<num[root]: root=r if i!=root: num[root],num[i]=num[i],num[root] heapify(n,root) def heapsort(): for i in range(num_size//2,-1,-1): heapify(num_size,i) for i in range(num_size-1,-1,-1): heapify(i,0) num[i],num[0]=num[0],num[i] heapsort() for i in num: print(i,end=" ") ``` ::: #### kruskal 最小生成樹 :::spoiler ```python=1 import heapq pq=[] num=[1]*101 parent=[0]*101 def findparent(a): while a!=parent[a]: a=parent[a] return a n,m=map(int,input().split()) for i in range(m): a,b,w=map(int,input().split()) heapq.heappush(pq,(w,a,b)) for i in range(101): parent[i]=i i=numEdge=result=0 while i<m and numEdge<n: edge=heapq.heappop(pq) a=findparent(edge[1]) b=findparent(edge[2]) if a!=b: if num[a]>num[b]: num[a]+=num[b] parent[b]=a else: num[b]+=num[a] parent[a]=b result+=edge[0] numEdge+=1 i+=1 if numEdge==n-1: print(result) else: print("no") ``` ::: #### 最小生成樹陣列版 :::spoiler ```python=1 n,m=map(int,input().split()) count=[] alldot=[] somedot=[] for i in range(m): a,b,c=map(str,input().split()) x=[] x.append(a) x.append(b) if a not in somedot: somedot.append(a) if b not in somedot: somedot.append(b) count.append(int(c)) alldot.append(x) num=[i for i in range(len(somedot))] s=sorted(count) sum=0 for i in range(len(s)): change=count.index(int(s[i])) if num[somedot.index(alldot[change][0])] != num[somedot.index(alldot[change][1])]: sum+=s[i] yo=num[somedot.index(alldot[change][0])] for v in range(len(num)): if num[v]==yo: num[v]=num[somedot.index(alldot[change][1])] count[change]=(n+1) print(sum) ``` ::: #### huffman 霍夫曼樹陣列版 :::spoiler ```python=1 #yesso是已經排序 #noso是未排序 n=eval(input()) for i in range(n): numnoso=[] m=list(map(int,input().split(','))) dot=[chr(65+i) for i in range(len(m))] alldot=[chr(65+i) for i in range(len(m))] final=['' for i in range(len(m))] for x in range(len(m)): numnoso.append(m[x]) numyesso=sorted(numnoso) for j in range(len(m)-1): x=numyesso[0] y=numyesso[1] z=x+y if x==y: firste=dot[numnoso.index(x)] k=0 while 1 : if numnoso[numnoso.index(y)+k]==numnoso[numnoso.index(x)] and dot[numnoso.index(y)+k]!=firste: seconde=dot[numnoso.index(y)+k] break k+=1 else: firste=dot[numnoso.index(x)] seconde=dot[numnoso.index(y)] for j in range(len(final)): if numnoso[j]==x and dot[j]==firste: final[j]+='0' for j in range(len(final)): if numnoso[j]==y and dot[j]==seconde: final[j]+='1' for i in range(len(dot)): if dot[i]==firste: dot[i]=firste+seconde elif dot[i]==seconde: dot[i]=firste+seconde for j in range(len(numnoso)): if numnoso[j]==x or numnoso[j]==y: numnoso[j]=z numyesso.pop(0) numyesso.pop(0) numyesso.append(z) numyesso.sort() for j in range(len(alldot)): final[j]=len(final[j]) print(*final,sep=',') ``` ::: #### huffman 霍夫曼樹 :::spoiler ```python=1 import heapq pq=[] hf=[0]*101 code=[0]*101 def dfs(id,leval): if hf[id].t==False: code[leval]="0" dfs(hf[id].le,leval+1) code[leval]="1" dfs(hf[id].ri,leval+1) else: print(hf[id].ch,end=" ") for i in range(leval): print(code[i],end=" ") print() class node: def __init__(self,id,ch,w,t,le,ri): self.id=id self.ch=ch self.w=w self.t=t self.le=le self.ri=ri c=["a","b",'c',"d","e"] w=[10,13,78,4,5] num=len(c) tmp=[] for i in range(len(c)): hf[i]=node(i,c[i],w[i],True,0,0) tmp.append(hf[i]) tmp=sorted(tmp,key=lambda x:x.w) while len(tmp)>1: a=tmp[0] del tmp[0] b=tmp[0] del tmp[0] n=node(num,None,a.w+b.w,False,a.id,b.id) hf[num]=n tmp.append(hf[num]) tmp=sorted(tmp,key=lambda x:x.w) num+=1 dfs(tmp[0].id,0) # s=("abs") # t=s.reversed(s) # print(t) ``` ::: #### DFS 迷宮 :::spoiler ```python=1 class point: def __init__(self,r,c,dis): self.r=r self.c=c self.dis=dis def bound(row,col,nr,nc): if row>0 and row<=nr and col>0 and col<=nc: return 1 else: return 0 map1=[[0]*101 for i in range(101)] val=[[0]*101 for i in range(101)] gor=[0,1,0,-1] goc=[1,0,-1,0] myq=[] r,c=map(int,input().split()) for i in range(1,r+1): line=input().split() for j in range(c): map1[i][j+1]=int(line[j]) sr,sc=map(int,input().split()) myp=point(sr,sc,1) val[myp.r][myp.c]=1 myq.append(myp) while len(myq)>0: nextp=myq[0] del myq[0] for i in range(4): if bound(nextp.r+gor[i],nextp.c+goc[i],r,c) and map1[nextp.r+gor[i]][nextp.c+goc[i]]==1 and val[nextp.r+gor[i]][nextp.c+goc[i]]==0: val[nextp.r+gor[i]][nextp.c+goc[i]]=nextp.dis+1 tmp=point(0,0,0) tmp.r=nextp.r+gor[i] tmp.c=nextp.c+goc[i] tmp.dis=nextp.dis+1 myq.append(tmp) for i in range(r): for j in range(c): print(val[i+1][j+1],end=" ") print() ``` ::: #### Dijkstra :::spoiler ```python=1 from heapq import * city={} G={} pq=[] dis=[10000000]*101 v=[0]*101 def getcityindex(p): if p not in city.keys(): city[p]=len(city) return city[p] class Edge: def __init__(self,s,t,w): self.s=s self.t=t self.w=w n=int(input()) for i in range(n): a,b,w=input().split() a=getcityindex(a) b=getcityindex(b) e1=Edge(a,b,w) e2=Edge(b,a,w) if a in G.keys(): G[a].append(e1) else: G[a]=[e1] if b in G.keys(): G[b].append(e2) else: G[b]=[e2] s=getcityindex(input()) p=(0,s) heappush(pq,p) dis[s]=0 while len(pq)>0: p=heappop(pq) s=p[1] if v[s]==0: for edge in G[s]: if v[edge.t]==0: if dis[edge.t]>dis[s]+edge.w: dis[edge.t]=dis[s]+edge.w p=(dis[edge.t],edge.t) heappush(pq,p) for i in range(len(city)): print(dis[i],end=" ") ``` ::: #### Dijkstra陣列版 :::spoiler ```python=1 n=eval(input()) dot=[] tree=[[0 for i in range(10)]for i in range(10)] for i in range(n): a,b,c=map(str,input().split()) if a not in dot : dot.append(a) if b not in dot: dot.append(b) tree[dot.index(a)][dot.index(b)]=int(c) tree[dot.index(b)][dot.index(a)]=int(c) door=[0 for i in range(len(dot))] ans=[99999 for i in range(len(dot))] m=input() ans[dot.index(m)]=0 door[dot.index(m)]=1 while 1: if door.count(1)==len(door): break else: for j in range(len(dot)): if tree[dot.index(m)][j]!=0 and (ans[dot.index(m)]+tree[dot.index(m)][j])<ans[j]: ans[j]=tree[dot.index(m)][j]+ans[dot.index(m)] little=99999 for k in range(len(ans)): if ans[k]<little and door[k]!=1: little=ans[k] for j in range(len(ans)): if ans[j]==little and door[j]!=1: door[j]=1 m=dot[j] break print(*ans) ``` 變化題：沒給距離的最短路徑 ```python=1 #UVA216 def dist(p,q,m,n): return ((p-m)**2+(m-n)**2)**0.5 def dfs(depth,path): if depth==n: if path<min_dis: min_dis=path for i in range(n): rx[i]=tmpx[i] ry[i]=tmpx[u] return for i in range(n): id used[i]==0: used[i]=1 tmpx[depth]=x[i] tmpx[depth]=y[i] if depth==0: dfs(depth+1,0) else: dfs(depth+1,path+dist(tmpx[depth],tmpy[depth],tmpx[depth-1],tmpy[depth-1])) uesd[i]=1 n=int(input()) min_dis=10000 x=[] y=[] uesd=[0]*n tmpx=[0]*n tmpy=[0]*n rx=[0]*n ry=[0]*n for i in range(n): s,k=map(int,input().split()) x.append(s) y.append(k) dfs(0,0) print(min_dis) #距離 for i in range(1,n): print(rx[i-1],ry[i-1],rx[i],ry[i],dist(rx[i-1],ry[i-1],rx[i],ry[i])) ``` ::: #### dijkstramap :::spoiler ```python=1 import heapq import sys ntime=int(input()) inf=(1000000) direct=(0,1,0,-1,0) for i in range(ntime): m=int(sys.stdin.readline().strip()) n=int(sys.stdin.readline().strip()) matrix=[] m_1=range(m+1) n_1=range(n+1) for j in m_1[0:-1]: matrix.append(list(map(int,sys.stdin.readline().strip().split()))) values=[[inf for a in n_1] for b in m_1] value[0][0]=matrix[0][0] pq=[] heapq.heappush(pq,(values[0][0],0,0)) while pq: value,x,y=heapq.heappop(pq) for c in range(4): nx,ny=direct[c]+x,direct[c+1]+y if nx<0 or ny<0 or nx>=n and ny>=m: contiune val=value+matrix[ny][nx] if values[ny][nx]>val: values[ny][nx]=val heapq.heappush(pq,[val,nx,ny]) sy.stdout.write(f'{values[m-1][n-1]}\n') ``` ::: #### distance :::spoiler ```python=1 m=int(input()) node=[[0]*9 for i in range(9)] distance=[0]*9 for i in range(m): a,b=map(int,input().split()) node[a][b]=1 node[b][a]=1 def dfs(x,px): for i in range(9): if node[x][i]==1 and i!=px: distance[i]=distance[x]+1 dfs(i,x) def tree_distance(x,y): distance[x]=0 dfs(x,y) print(distance[y]) sr,sc=map(int,input().split()) tree_distance(sr,sc) ``` ::: #### diameter :::spoiler ```python=1 m=int(input()) adj=[[0]*7 for i in range(7)] for i in range(m): a,b=map(int,input().split()) adj[a][b]=1 adj[b][a]=1 diamter=0 def dfs(x,px): global diamter h1=0 h2=0 for y in range(7): if adj[x][y]==1 and y!=px: h=dfs(y,x)+1 if h>h1: h2=h1 h1=h elif h>h2: h2=h diamter=max(diamter,h1+h2) return h1 def tree_diamter(): global diamter diamter=0 root=0 dfs(root,root) print(diamter) tree_diamter() #h032 while 1: try: n=int(input()) except: break deg=[0]*n parent=[-1]*n height=[0]*n for i in range(n-1): s,t=map(int,input().split()) parent[t]=s deg[s]+=1 que=[v for v in range(n) if deg[v]==0] front=0 diamter=0 while front<len(que): v=que[front] front+=1 p=parent[v] if p<0: break diamter=max(diamter,height[p]+height[v]+1) height[p]=max(height[p],height[v]+1) deg[p]-=1 if deg[p]==0: que.append(p) print(diamter) ``` ::: #### 前中轉後序 tree :::spoiler ```python=1 n=int(input()) prefix=[] infix=[] def travesal(n,ls,rs): global prefix,infix postfix=[] if ls==rs: return [prefix[n]] if ls>rs: return [] pos=infix.index(prefix[n]) N=[prefix[n]] L=travesal(n+1,ls,pos-1) R=travesal(n+(pos-ls)+1,pos+1,rs) if R==None: R=[] if L==None: L=[] for a in L: postfix.append(a) for a in R: postfix.append(a) for a in N: postfix.append(a) return postfix for i in range(n): infix=input().split(",") prefix=input().split(",") y=travesal(0,0,len(prefix)-1) for a in y: print(a,end=' ') ``` ::: #### 後中轉前序 tree :::spoiler ```python=1 prefix=[] infix=[] def travesal(n,ls,rs): global prefix,infix postfix=[] if ls==rs: return [prefix[n]] if ls>rs: return [] pos=infix.index(prefix[n]) N=[prefix[n]] R=travesal(n-1,pos+1,rs) L=travesal(n-(rs-pos)-1,ls,pos-1) if R==None: R=[] if L==None: L=[] for a in N: postfix.append(a) for a in L: postfix.append(a) for a in R: postfix.append(a) return postfix infix=input().split() prefix=input().split() y=travesal(len(prefix)-1,0,len(prefix)-1) for a in y: print(a,end="") ``` ::: #### 中轉後序算術 :::spoiler ```python=1 list1=[] list2=[] list3=[] list1=input() for i in list1: if i.isdigit(): list2.append(i) elif i=="(": list3.append("(") elif i=="+" or i=="-": if len(list3)>0: while list3[-1]=="+" or list3[-1]=="-" or list3[-1]=="*" or list3[-1]=="/": list2.append(list3.pop(-1)) list3.append("+") elif i=="*" or i=="/": if len(list3)>0: while list3[-1]=="*" or list3[-1]=="/": list2.append(list3.pop(-1)) list3.append("*") elif i==")": if len(list3)>0: while list3[-1]!="(": list2.append(list3.pop(-1)) list3.pop(-1) for i in list3: list2.append(i) print("".join(list2)) ``` ::: #### 後中轉前序算術 #### pathsum :::spoiler ```python=1 def run(n,n1,sum,p): global tree if n==n1: print(sum) else: s=0 if n%2==0:s=int(n/2) else:s=int((n-1)/2) if not n==1 and p!=s: run(s,n1,sum+int(tree[s]),n) s=int(n*2) if tree[s]!='null' and p!=s: run(s,n1,sum+int(tree[s]),n) s=int(n*2+1) if tree[s]!="null" and p!=s: run(s,n1,sum+int(tree[s]),n) tree=["null",1,2,3,4,5,"null",7,"null",'null',"null","null",'null',"null","null",'null',"null"] x1,x2=4,7 run(x1,x2,x1,-1) ``` ::: #### DP knapsack :::spoiler ```python=1 #無限背包 m=20 w=100 cost=[int(i) for i in input().split()] weight=[int(i) for i in input().split()] c=[0]*(w+1) def knapsack(n,w): for i in range(n): for j in range(weight[i],w+1): c[j]=max(c[j],c[j-weight[i]]+cost[i]) print(c[w]) #有限背包 n=20 w=100 c=[0]*(w+1) cost=[int(i) for i in input().split()] weight=[int(i) for i in input().split()] number=[int(i) for i in input().split()] def knapsack(n,w): for i in range(n): num=min(number[i],w//weight[i]) k=1 while num>0: if k>num: k=num num-=k j=w while j>=weight[i]*k: c[j]=max(c[j],c[j-weight[i]*k]+cost[i]*k) j-=1 k*=2 #湊硬幣 price=[5,2,6,11,1] c=[False]*1000 def knapsack(m): c[0]=True for i in range(5): for j in range(price[i],m+1): c[j]|=c[j-price[i]] if c[m]: print("y") else: print("n") #湊最少 price=[5,2,6,11,17] c=[10000]*1 def change(m): c[0]=0 for i in range(5): for j in range(price[i],m+1): c[j]=min(c[j],c[j-price[i]+1]) print("最少需要%d個硬幣"%(c[m])) #幾種湊法 coins=[1,2,5,10,20,50,100] def coin_sum(total,coins): way=[1]+([0]*tatal) for coin in coins: for i in range(coin,total+1): way[i]=way[i-coin] return [total] #P錢幣 can=[False]*1001 num=int(input()) data=[int(i) for i in input().split()] max_v=sum(data) can[0]=True for i in range(num): for k in range(max_v,data[i]-1,-1): can[k]|=can[k-data[i]] ans=[] for i in range(1,max_v): if can[i]: ans.append(i) print(len(ans)) for i in ans: print(i,end=" ") ``` ::: #### 關節點 :::spoiler 109模擬試題 G 方法一尋找一張圖的關節點有幾個點：利用 DFS 從第一個開始當作 root 開始建樹，只要發現連結的點尚未走過就當作自己的 child，而如果是有走過的點而且不是自己的 parent 表示有一條 back edge，利用這些自己這個點的 back edge 和所有自己的 **children 能走到最遠的的祖先去紀錄整體能走到最遠的的祖先到哪裡，則那位祖先只要不是 root 就是其中一個關節點**（因為它的 children 只要不經過這個點就無法連過去它 parent 以上的祖先）。而判斷祖先是否為關節點僅要判斷其 children 是否有兩個以上即可。整理： (1)若點p是深度優先搜尋樹的根節點，因為深度優先搜尋樹的子樹之間不會相連，會相連就會屬於同一子樹，所以點p只要有兩個以上的子樹，則點p就是關節點(articulation point)。 (2)若點p不是深度優先搜尋樹的根節點，點p的每個子孫都有back edge可以連到點p的祖先(不含點p)，該點就不是關節點(articulation point)，若有一個子孫沒有back edge，該點就是關節點(articulation point)。 ```python=1 #方法一 paths=[] Articulation=[] #關節點 tree_leval=0 v=[] up=[] def dfs(p,t): global paths,Articulation,tree_leval,v,up tree_leval+=1 v[t]=tree_leval up[t]=tree_leval child=0 #P點有幾個兒子 Ap=False nexp_point=0 for i in range(0,len(paths[t])): nexp_point=paths[t][i] if nexp_point!=p: if v[nexp_point]>0: up[t]=min(up[t],v[nexp_point]) else: child+=1 dfs(t,nexp_point) up[t]=min(up[t],up[nexp_point]) if up[nexp_point]>=v[t]: AP=True if (t==p and child>1) or (t!=p and AP==True): Articulation.append(t) while 1: n=int(input()) if n==0: break root=0 paths=[[] for i in range(n+1)] v=[0 for i in range(n+1)] up=[0 for i in range(n+1)] Articulation=[] while 1: x=[int(i) for i in input().split()] if root==0: root=x[0] if x[0]==0: break for i in range(1,len(x)): if x[i] not in paths[x[0]]: paths[x[0]].append(x[i]) if x[0] not in paths[x[i]]: paths[x[i]].append(x[0]) dfs(root,root) print(len(Articulation)) v=[0 for i in range(0,n+1)] ``` 方法二走訪關節點指的是在一個連通圖(DFS 或 BFS 可以走到所有點)中，如果移除該點，會使得該圖不再是連通圖，則該點為關節點。結論：只要有一點不能連到其他全部的點,此點則為關節點，**此法比較容易理解,但效率不好** ```python=1 import copy while 1: n=int(input()) if n==0: break paths=[[0 for i in range(n+1)] for j in range(n+1)] AP=[] #紀錄誰是關節點 while 1: #讀入paths x=[int(i) for i in input().split()] if x[0]==0: break for i in range(1,len(x)): paths[x[0]][x[i]]=1 paths[x[i]][x[0]]=1 cnt=0 visited1=[0 for i in range(n+1)] for i in range(1,n+1): visited=visited1.copy() bfs=[] pos=i%n+1 #下一點為起點，如果最後一點就第一點 bfs.append(pos) while len(bfs): pos=bfs[0] bfs.pop(0) #移除第一點 vistied[pos]=1 for j in range(1,n+1): if j==i: #拿掉的跳過不做 continue if visited[j]==0 and paths[pos][j]==1: bfs.append(j) for j in range(1,n+1): if visited[j]==0 and i!=j: cnt+=1 AP.append(i) break print(cnt) print("關節點",AP) ``` ::: #### loop :::spoiler ```python=1 import copy paths1=[[] for i in range(21)] vertex1=[0 for i in range(21)] visited=[] paths=[] loop_list=[] loop=-1 def dfs(v): global paths,visited,loop_list,loop count=0 if visited[v]==1: loop=v return -1 visited[v]=1 count=1 for i in paths[v]: paths[i].remove[v] y=dfs(i) if y==-1 and loop!=-1: loop_list.append(v) if v==loop: loop=-1 return -1 count+=y return count n=int(input()) for i in range(n): paths=copy.copy(paths1) vertex=copy.copy(vertex1) visited=copy.copy(vertex1) instr=input() vertex_list=[] for a in instr: x=[int(i) for i in a.split(",")] paths[x[0]].append(x[1]) paths[x[1]].append(x[0]) if vertex[x[0]]==0: vertex_list.append(x[0]) if vertex[x[1]]==0: vertex_list.append(x[1]) vertex[x[0]]=1 vertex[x[1]]=1 vertex_list=sorted(vertex_list) for a in range(0,vertex_list[-1]): paths[a]=sorted(paths[a]) loop_list=[] count=0 count=dfs(vertex_list[0]) if len(loop_list)>0: loop_list=sorted(loop_list) for a in loop_list: print(a,end=" ") else: if count==len(vertex_list): print("T") else: print('F') ``` ::: #### 經典LCS 2、3 :::spoiler ```python=1 def lcs(s1,s2): n1=len(s1) n2=len(s2) dp=[[None]*(n2+1) for _ in range(n1+1)] for i in range(n1+1): for j in range(n2+1): if i==0 or j==0: dp[i][j]=0 elif s1[i-1]==s2[j-1]: dp[i][j]=dp[i-1][j-1]+1 else: dp[i][j]=max(dp[i-1][j],dp[i][j-1]) return dp[n1][n2] x,y=map(str,input().split()) print(lcs(x,y)) ``` ```python=1 def lcs(s1,s2,s3): n1=len(s1) n2=len(s2) n3=len(s3) dp=[[[None]*(n2+1) for _ in range(n1+1)] for _ in range(n3+1)] for k in range(n3+1): for i in range(n1+1): for j in range(n2+1): if i==0 or j==0 or k==0: dp[k][i][j]=0 elif s1[i-1]==s2[j-1]==s3[k-1]: dp[k][i][j]=dp[k-1][i-1][j-1]+1 else: dp[k][i][j]=max(dp[k][i-1][j],dp[k][i][j-1],dp[k-1][i][j]) return dp[n3][n1][n2] x=list(input()) y=list(input()) z=list(input()) print(lcs(x,y,z)) ``` ::: #### LCS LIS :::spoiler ```python=1 #a676 n=int(input()) target=None while 1: try: line=[int(i) for i in input().split()] line.insert(0,0) ans=line[:] for i,l in enumerate(line): ans[l]=i if target==None: target=ans[:] continue ## LCS dp=[[0]*(n+1) for i in range(n+1)] for i in range(1,n+1): for j in range(1,n+1): if target[i]==ans[j]: dp[i][j]=dp[i-1][j-1]+1 else: dp[i][j]=max(dp[i-1][j],dp[i][j-1]) print(dp[n][n]) except: break ``` ```python=1 #d052 for _ in range(int(input())): n=int(input()) if n==0: print(0) contiune a=[None]*n for i in range(n): a[i]=int(input()) LIS=[None]*n LDS=[None]*n ans=0 for i in range(n-1,-1,-1): LIS[i]=1 LDS[i]=1 for j in range(n-1,i,-1): if a[i]>a[j] and LIS[i]<=LIS[j]: LIS[i]=LIS[j]+1 if a[i]<a[j] and LDS[i]<=LDS[j]: LDS[i]=LDS[j]+1 if ans<LIS[i]+LDS[i]-1: ans=lIS[i]+LDS[i]-1 print(ans) ``` ::: #### 產生子序列 :::spoiler ```python=1 arr=[int(i) for i in input().split()] finish=[] size=len(arr) end=2**size for index in range(end): array=[] for j in range(size): if (index>>j)%2: array.append(arr[j]) finish.append(array) print(finish) ``` ::: #### 01背包問題(取或不取) :::spoiler ```python=1 def f(w,v): #重量weight, 價值value for i in range(1, l+1): #l=len(w)-1 for j in range(1, m+1): #m=背包容量 if j>=w[i]: #如果當前的容量裝得下物品 dp[i][j]=max(dp[i-1][j-w[i]]+v[i], dp[i-1][j]) else: dp[i][j]=dp[i-1][j] return dp[-1][-1] dp=[[0 for i in range(m+1)] for j in range(l+1)] ``` ::: #### 騎士旅行問題 :::spoiler ```python=1 dx=[2,2,-2,-2,1,1,-1,-1] dy=[1,-1,1,-1,2,-1,2,-2] while 1: try: s1,s2=input().split() if s1==s2: print("To get from %s to %s takes 0 knight moves."%(s1,s2)) else: x1=ord(s1[0])-ord("a") y1=int(s1[1])-1 x2=ord(s2[0])-ord("a") y2=int(s2[1])-1 q=[(x1,x2,0)] flag=False while q: x,y,setp=q[0][0],q[0][1],q[0][2] q.pop(0) for i in range(8): nx=x+dx[i] ny=y+dy[i] if nx==x2 and ny==y2: print("To get from %s to %s takes %d knight moves."%(s1,a2,sept+1)) break if nx>=0 and nx<8 and ny>=0 and ny<8: q.append((nx,ny,setp+1)) if flag: break except: break ``` ::: #### 求最大和的子區域 :::spoiler ```python=1 #d206 a=[[0 for i in range(105)] for j in range(105)] n=int(input()) for i in range(1,n+1): list1=[int(i) for i in input().split()] for j in range(1,n+1): a[i][j]=list1[j-1] a[i][j]+=a[i][j-1] ans=0 for i in range(n): for j in range(i+1,n+1): total=0 for k in range(1,n+1): total+=a[k][j]-a[k][i] ans=max(ans,total) if total<0: total=0 print(ans) ``` ::: #### 二元樹括號輸入 :::spoiler 5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))) ```python=1 x=input().replace("　","") tree=[-1]*32 n=1 num="" for i in range(len(x)): if x[i] not in "()": num+=x[i] if x[i+1] in "()": tree[n]=int(num) num="" if x[i]=="(": if tree[2*n]==-1: n*=2 else: n=n*2+1 elif x[i]==")": if tree[n]==-1: tree[n]=0 n=int(n/2) ``` ::: #### 強連通 :::spoiler ![](https://i.imgur.com/9ccH4uz.png) ##### Kosaraju's Algorithm >使用DFS實作 >再進行一次DFS，並由離開DFS節點順序放入後，疊加進行DFS >這次的dfs中，此節點能夠碰到都是同組scc ```python=1 visit=[[] for i in range(100)] edge=[[] for i in range(100)] rev_edge=[[] for i in range(100)] group=[0]*101 path=[] def dfs1(root): global visit,group if visit[root]==1: return visit[root]=1 for i in edge[root]: dfs(i) path.append(root) def dfs2(root,ans): global visit,group if visit[root]==1: return visit[root]=1 group[root]=ans for i in rev_edge[root]: dfs2(i,ans) def kosaraju(): global visit,group cnt,q=map(int,input().split()) for i in range(q): a,b=map(int,input().split()) edge[a].append(b) rev_edge[b].append(a) visit=[0]*(101) path.clear() for i in range(cnt): if visit[i]==0: dfs1(i) visit=[0]*cnt grout=[0]*cnt for i in range(len(path)-1,-1,-1): if visit[path[i]]==0: dfs2(path[i],path[i]) print(group) kosaraju() ``` ::: #### 還原樹 (BFS,DFS) :::spoiler ```python=1 import heapq bfs=[] dfs=[] n=int(input()) v=[[] for i in range(101)] q=[] class Seg: def __init__(self,left,right): self.left=left self.right=right def slove(): global q,v q.append(Seg(0,n)) p=1 root=0 while len(q)>0: s=q.pop(0) if s.right-s.left<=1 or p==n: continue root=dfs[s.left] #print(root) pre=s.left+1 for i in range(pre,s.right): if dfs[i]==bfs[p]: q.append(Seg(pre,i)) v[root].append(dfs[i]) p+=1 pre=i if pre<s.right: q.append(Seg(pre,s.right)) bfs=[int(i) for i in input().split()] dfs=[int(i) for i in input().split()] slove() for i in v: print(i) ``` ::: #### 並查集 :::spoiler ```python=1 #f677 n,m=map(int,input().split()) parent=[int(i) for i in range(n)] for _ in range(m): a,b=map(int,input().split()) mx=max(parent[a],parent[b]) mn=max(parent[b],parent[a]) for i in range(len(parent)): if parent[i]==parent[mn]: parent[i]=parent[mx] print(parent.count(parent[0])) ``` ::: #### 二分搜 :::spoiler ```python=1 #d732 def binary_search(list1,num): low = 0 high = len(list1)-1 while(low<=high): mid = (low+high)//2 guess = list1[mid] if(guess==num): return mid elif(guess>num): high = mid-1 else: low = mid+1 return -1 ``` >可以使用bisect ```python=1 import bisect def binary_search(list1,num): return bisect.bisect_left(list1,num) ``` ::: ## :memo: 常用函式或功能 #### 以 dict value由小到大排序，若value一樣則由key 由大到小排序 ```python=1 for k,v in sorted(dict1.items(),key=lambda x:(x[1],-x[0])): print(k,v) ``` #### 增加最大遞迴深度(python 預設為1000) ``` python=1 import sys sys.setrecursionlimit(20000) ``` #### input加快 ``` python=1 m=int(sys.stdin.readline().strip()) matrix.append(list(map(int,sys.stdin.readline().strip().split(" ")))) ``` #### 位元 ```python=1 a=60 #60 = 0011 1100 b=13 #13 = 0000 1101 c=0 #& and 運算 c=a&b #12 0000 1100 # | or運算 c=a|b #61 0011 1101 #^ 互斥，對應的二進位相時，結果為1 c=a^b #49 0011 0001 # ~ 補數二進位取反 1變成0 0變成1 c=~a #-61 1100 0011 # << 二進位全部向左移若干位，高位丟棄，低位補0 c=a<<2 #240 1111 0000 #>> 二進位全部向右移 c=a>>2 #15 0000 1111 print(("1<<5的結果",1<<5)) #32 100000 ``` #### python 日期 ``` python=1 import datetime # 日期相減 begin=datetime.date(2022,11,29) end=datetime.date(2022,11,12) result=begin-end print(str(result.days)) #17 # 日期加一天 in_date="2022-11-12" dt=datetime.datetime.strptime(in_date,"%Y-%m-%d") out=(dt+datetime.timedelta(days=17)).strftime("%Y-%m-%d") print(out) #2022-11-29 #日期減一天 in_date="2022-11-29" dt=datetime.datetime.strptime(in_date,"%Y-%m-%d") out=(dt-datetime.timedelta(days=17)).strftime("%Y-%m-%d") print(out) #2022-11-12 #求星期 a,b=map(int,input().split()) print(datetime.date(2022, a, b).strftime("%A")) ``` #### 分數加減 ```python=1 #導入fractions模組 from fractions import Fraction print(Fraction(2,9)+Fraction(1,4)) #17/36 ``` #### 運算子優先權 ```python=1 (), [], {}, set() #-------- ** #-------- +x, -x, ~x #-------- *, /, // , % #-------- +, - #-------- <<, >> #-------- & ^ | < <= > >= == != in not in is is not not and or if, elif, else lambda ``` ## :memo: 重要經典題目 #### DP經典問題 :::spoiler > 給你兩個字串 S 和 T，請問 S 有多少個子序列與 T 相同呢？ input: rabbbit rabbit output: 3 ```python=1 s=input() t=input() n,m=len(s),len(t) dp=[[0]*(m+1) for _ in range(n+1)] dp[0][0]=1 for i in range(1,n+1): dp[i][0]=1 for j in range(1,m+1): if s[i-1]==t[j-1]: dp[i][j]=dp[i-1][j] else: dp[i][j]=dp[i-1][j-1]+dp[i-1][j] print(dp[n][m]) ``` 字串編輯問題 > 給你兩個字串 word1, word2。每一次可以插入、刪除、修改一個字元。請問至少要幾次操作才能將 word1 換成 word2 呢？ input: horse ros output: 3 ```python=1 word1=input() word2=input() dp=[list(range(i,m+i+1)) for i in range(n+1)] for i in range(1,n+1): for j in range(1,m+1): if word1[i-1]==word2[j-1]: dp[i][j]=dp[i-1][j-1] else: dp[i][j]=min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])+1 print(dp[n][m]) ``` > 給你兩個字串 str1 與 str2，找出一個最短的公共字串 S，使得 str1 與 str2 同時是 S 的子字串。 > input > abac > cab > output > cabac ```python=1 str1=input() str2=input() n,m=len(str1),len(str2) dp=[[0]*(m+1) for _ in range(n+1)] for i in range(1,n+1): for j in range(1,m+1): if str1[i-1]==str2[j-1]: dp[i][j]=dp[i-1][j-1]+1 else: dp[i][j]=max(dp[i-1][j],dp[i][j-1]) answer="" i,j=n,m while i>0 and j>0: if str1[i-1]==str2[j-1]: answer+=str1[i-1] i,j=i-1,j-1 elif dp[i-1][j]>dp[i][j-1]:: answer+=str1[i-1] i=i-1 else: answer+=str2[j-1] j=j-1 answer=answer[::-1] print(str1[0:i]+str2[0:j]+answer) ``` ::: #### 旗立108 G 二元樹最大路徑總和 :::spoiler ``` python=1 # AC time: 0.7s def run(n,n1,sum,p): #節點，目標節點，總和，上一個 global tree,list5 if n==n1: #如果到目標點就放在list5 list5.append(sum) return else: s=0 if n%2==0:s=int(n/2) #上一個點 else:s=int((n-1)/2) if not n==1 and p!=s : #如果上一個點不是p 也不是1 (上一個不可能是null) run(s,n1,sum+int(tree[s]),n) s=int(n*2) #左邊 if tree[s]!="null" and p!=s: run(s,n1,sum+int(tree[s]),n) s=int(n*2+1) #右邊 if tree[s]!="null" and p!=s: run(s,n1,sum+int(tree[s]),n) for _ in range(int(input())): t=input()[1:-1].replace(" ","").split(",") tree=t tree.insert(0,"null") for i in range(500): tree.append("null") list5=[] for i in range(len(tree)): for j in range(len(tree)): if tree[i].isdigit() and tree[j].isdigit(): run(i,j,int(tree[i]),-1) if len(list5)==0: print(-1) else: print(max(list5)) ``` ``` python=1 #AC time: 19ms def dfs(n, path=[]): path.append(int(tree[n])) r=0 if n*2+1<=max_node: if tree[n*2+1]!='null': dfs(n*2+1, path.copy()) r+=1 if n*2+2<=max_node: if tree[n*2+2]!='null': dfs(n*2+2, path.copy()) r+=1 if r==0: #到leaf了... lst.append(sum(path)) for _ in range(int(input())): tree=input().replace(' ','').replace('[','').replace(']','').split(',') max_node=len(tree)-1 #處理邊界,避免出現溢位 ans=[] for i in range(len(tree)): if tree[i]=='null': continue lst=[] L=0 R=0 if i*2+1<=max_node and tree[i*2+1]!='null': dfs(i*2+1,[]) if lst!=[]: L=max(max(lst),0) #如果max(lst)<0, 那就不能走, 不然路徑和會變小 lst.clear() #清空 if i*2+2<=max_node and tree[i*2+2]!='null': dfs(i*2+2,[]) if lst!=[]: R=max(max(lst),0) #如果max(lst)<0, 那就不能走, 不然路徑和會變小 ans.append(int(tree[i])+L+R) print(max(ans)) ``` ::: #### 二元一次方程式 103 B 郵票 :::spoiler ![](https://i.imgur.com/J2aINRp.png) ```python=1 for _ in range(int(input())): p,c,d,q=map(int,input().split(",")) x=(d*p-q)/(d-c) y=(c*p-q)/(c-d) print("%d,%d"%(x,y)) ``` ::: #### 110模擬 G格雷碼 :::spoiler ``` python=1 def f(x): g=['0','1'] for i in range(1, x): a=[] b=[] for j in g: a.append('0'+j) g=g[::-1] for j in g: b.append('1'+j) g=a+b return g n=int(input()) ans=f(n) for i in ans: print(i) ``` ::: #### 110 條條大路通羅馬 :::spoiler ``` python=1 def DFS(x): visited[x]=1 for i in path[x]: if visited[i]==0: DFS(i) n,m=map(int, input().split()) path=[[] for i in range(n+1)] visited=[0]*(n+1) for _ in range(m): a,b=map(int, input().split()) path[a].append(b) A,B=map(int, input().split()) DFS(A) if visited[B]==1: print('Yes') else: print('No') ``` ::: #### 111 T路徑 :::spoiler ``` python=1 from collections import deque def treepath(node,order): if node>l or tree[node]=="null": return order.append(tree[node]) if 2*node+1>l or (tree[2*node+1]=="null" and tree[2*node+2]=="null"): path="->".join(list(order)) print(path) treepath(2*node+1,order) treepath(2*node+2,order) order.pop() tree=input().split() l=len(tree)-1 path=deque() treepath(0,path) ``` ::: #### 111 E1 建樹 :::spoiler ``` python=1 while 1: try: dic={} f=False; Tree=True while 1: s=input().split() for i in s: if i=='()': f=True else: a,b=i[1:len(i)-1].split(',') if b=='': b='root' if b in dic: Tree=False dic[b]=a if f: break if 'root' not in dic: Tree=False if Tree: tree=[] tree.append(dic['root']) del dic['root'] q=['L','R'] while q: node=q.pop(0) if node in dic: tree.append(dic[node]) q.append(node+'L') q.append(node+'R') del dic[node] if len(dic)>0: print('not complete') elif not Tree: print('not complete') else: print(*tree) except: break ``` ::: #### 111 E2 迷宮 :::spoiler ``` python=1 import heapq import sys ntiem=int(input()) inf=(1000000)*9 direct=(0,1,0,-1,0) for i in range(ntiem): m=int(sys.stdin.readline().strip()) n=int(sys.stdin.readline().strip()) matrix=[] m_1=range(m+1) n_1=range(n+1) for j in m_1[0:-1]: matrix.append(list(map(int,sys.stdin.readline().strip().split()))) values=[[inf for a in n_1] for b in m_1] values[0][0]=matrix[0][0] pq=[] heapq.heappush(pq,(values[0][0],0,0)) while pq: value,x,y=heapq.heappop(pq) for c in range(4): nx,ny=direct[c]+x,dicect[c+1]+y if nx<0 or ny<0 or nx>=n or ny>=m: continue val=value+matrix[ny][mx] if values[ny][nx]>val: values[ny][nx]=val heapq.heappush(pq,[val,nx,ny]) sys.stdout.write(f"{values[m-1][n-1]}\n") ``` ::: #### 河內塔 :::spoiler ``` python=1 def hanoi_tower(n,v,m,t): if n==1: print('Move ring',n,'from',v,'to',t) #n從 v點移到t點 else: hanoi_tower(n-1,v,t,m) print('Move ring',n,'from',v,'to',t) hanoi_tower(n-1,m,v,t) n=int(input()) hanoi_tower(n,'A','B','C') ``` >河內塔變種(奇數放在b柱，偶數放在c柱) ``` python=1 #b190 #全放 ansa = 0 def f(num,a,b,c): global ansa if(num<=1): temp = dic[a].pop() print("ring %d : "%temp,end = "") dic[c].append(temp) print(a,"->",c) ansa+=1 else: f(num-1,a,c,b) f(1,a,b,c) f(num-1,b,a,c) #放一半 def g(num,a,b,c): global ansa if(num!=1): f(num-1,a,c,b) temp = dic[a].pop() print("ring %d : "%temp,end = "") dic[c].append(temp) print(a,"->",c) ansa+=1 def ans(num,a,b,c): i=0 while(num>0): g(num,a,b,c) if(i==0): a,b = b,a num-=2 i=1 else: a,b,c = b,c,a num-=1 i=0 try: while(1): dic = {} ansa = 0 n = int(input()) dic["a"] = [i for i in range(n+1,0,-1)] dic["b"] = [] dic["c"] = [] if(n%2==1): ans(n,"a","c","b") else: ans(n,"a","b","c") print("共移動了",ansa,"步") except EOFError: pass ``` >河內塔變種-在無法枚舉全部情況(數字給很大)的情況下求出第n步移動情況 ``` python=1 #e790求n盤河內塔第m步的移動情況 point1 = [2,3,1] point2 = [3,2,1] a,b = map(int,input().split()) ans = (bin(b)[2:][::-1]).index("1")+1 ans2 = 0 if(a%2==0): point1,point2 = point2,point1 for j in range(ans-1): ans2 = ans2*2+1 if(ans%2==0): lans1 = point1[((b-ans2)//2**ans)%3] lans2 = point1[(((b-ans2)//2**ans)%3-1)%3] else: lans1 = point2[((b-ans2)//2**ans)%3] lans2 = point2[(((b-ans2)//2**ans)%3-1)%3] print("move %d from %d to %d"%(ans,lans2,lans1)) ``` ::: #### 104 F 矩陣相乘求9999 :::spoiler ``` python=1 for _ in range(int(input())): m,r,r1,n=map(int,input().split(",")) lista=[] for i in range(m): lista.append([int(i) for i in input().split()]) listb=[] for i in range(r1): listb.append([int(i) for i in input().split()]) listc=[] for i in range(m): listc.append([int(i) for i in input().split()]) INF=100000000 check=INF #ans for i in range(m): if 9999 in lista[i]: #如果9999在lista中 lista999=lista[i].index(9999) #找出lista的位置 for k in range(n): #找出listb相對位置 if listb[lista999][k]!=0: #相對位置不是0 如果是0相乘就是0 沒有意義 sum1=0 for j in range(r): #這裡開始相乘 if lista[i][j]==9999: #如果是9999 就把相對位置記錄起來 ans1=listb[j][k] else: sum1+=listb[j][k]*lista[i][j] #不是就相乘 check=(listc[i][k]-sum1)/ans1 #透過C求解 if check!=INF: #如果不是10000代表算出答案那就可以離開 break if check==INF: #如果還是10000代表9999不再a中，從b找 newb=[] #翻轉一下比較方便 for i in range(n): newb.append([]) for j in range(r1): newb[i].append(listb[j][i]) #完成反轉 for i in range(len(newb)): #跟a差不多 if 9999 in newb[i]: t=newb[i].index(9999) for k in range(m): if lista[k][t]!=0: ans1=0 sum1=0 for gg in range(r): if newb[i][gg]==9999: ans1=lista[k][gg] else: sum1+=lista[k][gg]*newb[i][gg] check=(listc[k][i]-sum1)/ans1 if check!=INF: break if check!=INF: break print(int(check)) ``` ::: #### 最大連續和 :::spoiler ```python=1 list1=[int(i) for i in input().split()] sum=0 mx=-1e9 for i in range(len(list1)): sum+=list1[i] mx=max(sum,mx) if sum<0: sum=0 print(mx) ``` ::: #### 103 E 撲克牌 :::spoiler ``` python=1 from itertools import combinations def dfs(tmp): #判斷同色 end=0 for i in tmp: if not(i<14): break else: end=1 if end==0: for i in tmp: if not(i>13 and i<27): break else: end=1 if end==0: for i in tmp: if not(i>26 and i<40): break else: end=1 if end==0: for i in tmp: if not(i>39): break else: end=1 return end for _ in range(int(input())): list1=[int(i) for i in input().split()] list2=list(combinations(list1,5)) ans=[] t=0 for i in list2: tmp=i tmp=sorted(tmp) end=0 s=0 rrr=0 if dfs(tmp)==1: #符合同色判斷連續 for i in range(1,len(tmp)): if tmp[i]-tmp[i-1]==1: s+=1 if s==4: t=7 end=1 s=0 if (tmp[0]-1)%13==0: #A換成14 tmp[0]+=13 tmp.sort() for i in range(1,len(tmp)): if tmp[i]-tmp[i-1]==1: s+=1 if s==4: t=7 end=1 if end==0: sorttmp=[] for i in tmp: if i<14: sorttmp.append(i) elif i<27: sorttmp.append(i-13) elif i<40: sorttmp.append(i-26) else: sorttmp.append(i-39) for i in sorttmp: if sorttmp.count(i)==4: t=6 end=1 break if end==0: three=0 two=0 for i in sorttmp: if sorttmp.count(i)==2: two+=1 if sorttmp.count(i)==3: three+=1 if two==2 and three==3: t=5 end=1 if end==0: if three==3: t=3 end=1 if two==4: t=2 end=1 if two==2: t=1 end=1 if end==0: s=0 sorttmp.sort() for i in range(1,len(sorttmp)): if sorttmp[i]-sorttmp[i-1]==1: s+=1 if s==4: t=4 end=1 else: s=0 if 1 in sorttmp: sorttmp[sorttmp.index(1)]=14 sorttmp.sort() for i in range(1,len(sorttmp)): if sorttmp[i]-sorttmp[i-1]==1: s+=1 if s==4: t=4 end=1 ans.append(t) print(max(ans)) ``` ::: #### 108旗立H 求完全平方數有幾個 :::spoiler > Lagrange 四平方和定理：任何一个正整数都可以表示成不超过四个整数的平方之和。 > 满足四数平方和定理的数n（这里要满足由四个数构成，小于四个不行），必定满足 n = 4a ( 8 b + 7 ) ``` python=1 # TLE time:6s def f(n): cnt=n num=2 while num*num>=n: a=n/(num*num) b=n%(num*num) cnt=min(cnt,a+f(b)) num+=1 return cnt for _ in range(int(input())): n=int(input()) print(int(f(n))) #AC time:19ms def num(n): while n%4==0: n//=4 if n%8==7: #7=4+1+1+1 return 4 for i in range(n+1): tmp=i*i if tmp<=n: if (int(n-tmp)**0.5)**2+tmp==n: return 1+(0 if tmp==0 else 1) else: break return 3 for _ in range(int(input())): print(num(int(input()))) ``` ::: #### 105旗立E 最小成本生成樹及次小生成樹 :::spoiler > 次小生成樹求法為：先刪去每個邊求最小成本，裝進list中，若最小生成樹大於list的一半他就是次小，如果沒有那就將不是最小的裝進list2中，再找min ``` python=1 import heapq import copy for _ in range(int(input())): #求最小生成樹 instr=input().split() parent=[0]*1001 num=[1]*1001 pq=[] def findparent(a): if a not in city.keys(): city[a]=len(city) return city[a] city={} def getcityindex(p): if p not in city.keys(): city[p]=len(city) return city[p] m=len(instr) for i in range(m): s=instr[i] a,b,c=s.split(",") w=int(w) a=getcityindex(a) b=getcityindex(b) heapq.heapppush(pq,(w,a,b)) n=len(city) for i in range(1001): parent[i]=i i=numEdge=result=0 while i<m and numEdge<n: edge=heapq.heappop(pq) a=findparent(edge[1]) b=findparent(edge[2]) if a!=b: if num[a]>num[b]: parent[b]=a num[a]+=num[b] else: parent[a]=b num[b]+=num[b] numEdge+=1 result+=int(edge[0]) i+=1 ans1=result # 最小生成樹到此結束 anslist=[] #求次小生成樹 for i in range(m): newinstr=copy.deepcopy(instr) del newinstr[i] #以下求法跟上面一樣 parent=[0]*1001 num=[1]*1001 pq=[] def findparent(a): while a!=parent[a]: parent[a]=a return a city={} def getcityindex(p): if p not in city.keys(): city[p]=len(city) return city[p] m=len(newinstr) for i in range(m): s=newinstr[i] a,b,w=s.split(",") w=int(w) a=findparent(a) b=findparent(b) heapq.heapppush(pq,(w,a,b)) n=len(city) for i in range(1001): parent[i]=i i=numEdge=rseult=0 while i<m and numEdge<n: edge=heapq.heappop(pq) a=findparent(edge[1]) b=findparent(edge[2]) if a!=b: if num[a]>num[b]: parent[b]=a num[a]+=num[b] else: parent[a]=b num[b]+=num[a] numedge+=1 result+=int(edge[0]) i+=1 ans.append(result) #次小生成樹求法到此結束，以下開始判斷 if anslist.count(ans1)>len(anslist1)//2: print(ans1,ans1) else: newans=[] for i in anslist: if i!=ans1: newans.append(i) if len(newans)==0: #不太會有這個可能，但還是判斷一下 print(ans1,ans2) else: print(ans1,min(newans1)) ``` ::: #### a249: 00679 - Dropping Balls :::spoiler ``` python=1 for _ in range(int(input())): D,I=map(int, input().split()) idx=1 remainder=I for i in range(D-1): if remainder%2==1: idx=2*idx remainder=(remainder+1)//2 #remainder餘數 else: idx=2*idx+1 remainder//=2 print(idx) ``` ::: #### 110群科Q8 交換物品 :::spoiler ![](https://i.imgur.com/lyKScww.png) ``` python=1 I=[] vertex=[] inf=99999 while 1: try: x=input().split() I.append(x) vertex.append(x[0]) vertex.append(x[1]) except: break vertex=[0]+(list(set(vertex))) start=vertex.index(I[0][0]) end=vertex.index(I[-2][-2]) I.pop() n=len(vertex) m=len(I) visited=[0 for i in range(n+1)] data=[[inf for i in range(n+1)] for j in range(n+1)] dis=[inf for i in range(n+1)] visited[start]=1 for i in range(1,n+1): for j in range(1,n+1): if i==j: data[i][j]=0 for i in range(m): data[vertex.index(I[i][0])][vertex.index(I[i][1])]=int(I[i][2]) for i in range(1,n+1): dis[i]=data[start][i] paths=[start for i in range(n+1)] for i in range(n): minn=inf for j in range(1,n+1): if visited[j]==0 and minn>dis[j]: minn=data[i][j] u=j visited[u]=1 for j in range(1,n+1): if dis[j]>dis[u]+data[u][j]: dis[j]=dis[u]+data[u][j] paths[j]=u print(dis[end]) whlk=[end] k=end while k!=start: k=paths[k] walk.append(k) for i in walk[::-1]: print(vertex[i],end=" ") ``` ::: #### 連續加總 :::spoiler ```python=1 #UVA 11254 def check(n,r): a=2*n+r-r**2 if a%(2*r)==0: return (a/(2*r)) return -1 n=int(input()) while n>0: m=int((2*n)**0.5) p=0 for i in range(m,0,-1): a=check(n,i) if a!=-1: print("%d = %d + ... + %d"%(n,a,a+i-1)) break n=int(input()) ``` ::: #### 矩陣快速冪 :::spoiler >本方法可使O(n)降為O(log n) ```python=1 #ZJ-a451,TA001-TB01 #返回兩個2*2矩陣相乘結果 def arrmult(arr1,arr2,m): ansarr = [[0,0],[0,0]] ansarr[0][0]=(arr1[0][0]*arr2[0][0]+arr1[0][1]*arr2[1][0])%m ansarr[0][1]=(arr1[0][0]*arr2[0][1]+arr1[0][1]*arr2[1][1])%m ansarr[1][0]=(arr1[1][0]*arr2[0][0]+arr1[1][1]*arr2[1][0])%m ansarr[1][1]=(arr1[1][0]*arr2[0][1]+arr1[1][1]*arr2[1][1])%m return ansarr.copy() #矩陣快速冪 def fastmult(arr,b,m): if(b<=1): return arr if(b%2==0): return fastmult(arrmult(arr,arr,m),b//2,m) return arrmult(arr,fastmult(arrmult(arr,arr,m),b//2,m),m) def fib(n,m): if(n==0): return 0 if(n==1): return 1 if(n==2): return 1 fibarr = [[1,1],[1,0]] theans = fastmult(fibarr,n-2,m) return (theans[0][0]+theans[0][1])%m try: while(1): n,m = map(int,input().split()) print(fib(n,2**m)) except EOFError: pass ``` ::: #### 輸入整數轉羅馬符號 :::spoiler ```python=1 n=int(input()) for i in range(n): num = int(input()) if 1 <= num <= 3999: val = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1] syb = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"] roman_num = '' i = 0 while num > 0: if num >= val[i]: roman_num += syb[i] num -= val[i] else: i += 1 print(roman_num) ``` ::: #### 輸入羅馬符號轉整數 :::spoiler ```python=1 roman_numerals = ["I", "V", "X", "L", "C", "D", "M"] integer_values = [1, 5, 10, 50, 100, 500, 1000] roman_numeral = input() total = 0 prev_value = 0 for numeral in roman_numeral: value = integer_values[roman_numerals.index(numeral)] if value > prev_value: total += value - 2 * prev_value else: total += value prev_value = value print(total) ``` ::: #### 108正式-F 循環小數 :::spoiler ```python=1 t = int(input()) for _ in range(t): a,b = map(int,input().split()) num = a%b arr1 = [num] arr2 = [] while(1): arr2.append((10*num)//b) num = (10*num)%b if(num in arr1): ansindex = arr1.index(num) break arr1.append(num) print(a//b,end = ".") if(len(arr2[ansindex:])>50): print(*arr2[:ansindex],"(",*arr2[ansindex:ansindex+50],"...)",sep = "") else: print(*arr2[:ansindex],"(",*arr2[ansindex:],")",sep = "") ``` ::: #### 點圖 :::spoiler #### 求平行四邊形給定平行四邊形的兩個相鄰邊的端點的 (x, y)座標。找到第四個點的 (x, y)座標。 ```python=1 while 1: try: except: list1=[eval(i) for i in input().split()] list3=[] list3.append(list1[0],list1[1]) list break ]=999999 print(sum) ``` ::: #### 高精度運用 :::spoiler >大數-所有大數運算都可以變更快速(尤其是計算冪次和取餘的部分 ```python=1 #e036 from decimal import * setcontext(Context(prec=MAX_PREC,Emax=MAX_EMAX)) #計算2^82589933 a = Decimal(2) b = Decimal(82589933) print(a**b) ``` ::: #### 喬瑟夫問題 :::spoiler ```python=1 #d192 def josephus(n,k): #遞迴在數字太大的時候容易炸開，遞推比較保險 survivor = 0 for i in range(2, n + 1): survivor = (survivor+k)%i return survivor+1 t = int(input()) for i in range(t): print("Case %d: " % (i+1), end="") n, k = map(int, input().split()) print(josephus(n,k)) ``` ::: ## :memo: 賽前重點刷題 [a676](https://zerojudge.tw/ShowProblem?problemid=a676) -LIS [f168](https://zerojudge.tw/ShowProblem?problemid=f168) -分配寶物 [d536](https://zerojudge.tw/ShowProblem?problemid=d536) -圖形迴圈偵錯 [d768](https://zerojudge.tw/ShowProblem?problemid=d768) -DFS [c001](https://zerojudge.tw/ShowProblem?problemid=c001) -LCS [c547](https://zerojudge.tw/ShowProblem?problemid=c547) -DP 爬樓梯 [e544](https://zerojudge.tw/ShowProblem?problemid=e544) -DNA sort [d908](https://zerojudge.tw/ShowProblem?problemid=d908) -最佳路徑 [b537](https://zerojudge.tw/ShowProblem?problemid=b537) -分數運算 [d378](https://zerojudge.tw/ShowProblem?problemid=d378) -最小路徑地圖 [d192](https://zerojudge.tw/ShowProblem?problemid=d192) -喬瑟夫 [c350](https://zerojudge.tw/ShowProblem?problemid=c350) - 數學 [c317](https://zerojudge.tw/ShowProblem?problemid=c317) - 硬幣問題 [e339](https://zerojudge.tw/ShowProblem?problemid=e339) - 前綴和 [a982](https://zerojudge.tw/ShowProblem?problemid=a982) - 迷宮問題 [b184](https://zerojudge.tw/ShowProblem?problemid=b184) - 背包 [d904](https://zerojudge.tw/ShowProblem?problemid=d904) - 硬幣 [d637](https://zerojudge.tw/ShowProblem?problemid=d637) - 背包 [c117](https://zerojudge.tw/ShowProblem?problemid=c117) - 騎士旅行問題 [c126](https://zerojudge.tw/ShowProblem?problemid=c126) - 前中轉後 [a410](https://zerojudge.tw/ShowProblem?problemid=a410) - 解方程式 [f671](https://zerojudge.tw/ShowProblem?problemid=f671) - 最短路徑 [f678](https://zerojudge.tw/ShowProblem?problemid=f678) - 最小生成樹 [f673](https://zerojudge.tw/ShowProblem?problemid=f673) - 樹高 [d453](https://zerojudge.tw/ShowProblem?problemid=d453) - 最短距離 [b674](https://zerojudge.tw/ShowProblem?problemid=b674) - is it a tree [a129](https://zerojudge.tw/ShowProblem?problemid=a129) - 最小生成樹 [f675](https://zerojudge.tw/ShowProblem?problemid=f675) - BST [d526](https://zerojudge.tw/ShowProblem?problemid=d526) - BST [f698](https://zerojudge.tw/ShowProblem?problemid=f698) - 後序運算 [d862](https://zerojudge.tw/ShowProblem?problemid=c126) - 背包 [a252](https://zerojudge.tw/ShowProblem?problemid=a252) - LCS [a445](https://zerojudge.tw/ShowProblem?problemid=a445) - 並查集 [e586](https://zerojudge.tw/ShowProblem?problemid=e586) - 最小生成樹 [f291](https://zerojudge.tw/ShowProblem?problemid=f291) - 試算表 [e626](https://zerojudge.tw/ShowProblem?problemid=f291) - 連續和 ## :memo: 函式研究與筆記暫存(會調整或刪除) #### 內建函式 :::spoiler ```python=1 #本地x,y,z,a,b代表數字，list開頭代表陣列，s代表字串，c代表單一字元，func代表函式 abs(x) #取絕對值 bin(x) #數字轉二進位 hex(x) #數字轉16進位 int(s,b) #把某進位轉換成10進位 chr(x) #回傳對應ASCII碼的文字 ord(c) #回傳此字元的ASCII碼 ``` :::