1. * # Python題目解題
# hello :100: :memo:
## BST 二元搜尋樹
:::spoiler
```python=1
class tree: #二元樹宣告
def __init__(self):
self.data=0
self.left=None
self.right=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:
backup.left=newnode
else:
backup.right=newnode
return root
def inorder(ptr): #中序走訪
if ptr!=None:
inorder(ptr.left)
print(ptr.data)
inorder(ptr.right)
def postorder(ptr): #後序走訪
if ptr!=None:
postorder(ptr.left)
postorder(ptr.right)
print(ptr.data)
def preorder(ptr): #前序走訪
if ptr!=None:
print(ptr.data)
preorder(ptr.left)
preorder(ptr.right)
def search(ptr, val): #二元樹搜尋
while 1:
if ptr==None:
return None
if ptr.data==val:
return ptr
elif ptr.data>val:
ptr=ptr.left
else:
ptr=ptr.right
```
:::
## DP動態規劃
#### 最長遞增子序列
:::spoiler
```python=1
while 1:
try:
s=list(map(int,input().split()))
m=[1 for i in range(0,len(s))]
for i in range(0,len(s)):
for j in range(0,i):
if s[j]<s[i]:
if m[j]+1>m[i]:
m[i]=m[j]+1
print(max(m))
except:
break
```
:::
#### 切棍子
:::spoiler
```python=1
v=[0,1,5,8,9,10,12,17,20,24,25]
dp=[0]*11
for i in range(1, 11):
dp[i]=0
for j in range(1, i+1):
if dp[i-j]+v[j] > dp[i]:
dp[i]=dp[i-j]+v[j]
n=int(input())
print(dp[n])
```
:::
#### b589
:::spoiler
```python=1
dp1=[0 for i in range(100)]
while 1:
n=int(input())
if n==0:
break
x=list(map(int, input().split()))
dp=dp1.copy()
for i in range(0,n):
dp[i+1]=max(dp[i+1], dp[i]+x[i])
dp[i+2]=max(dp[i+2], dp[i]+2*x[i])
print(max(dp[n],dp[n+1]))
```
:::
#### 方格棋盤
:::spoiler
```python=1
#方格棋盤路線
#從左上角走到右下角的最大總和
#只能往右或往下
#最後一格一定是從dp[i-1][j] or dp[i][j-1]走過來的
m,n=map(int, input().split())
g=[]
for _ in range(m):
g.append(list(map(int, input().split())))
dp=[[0 for i in range(n)] for j in range(m)]
dp[0][0]=g[0][0]
for i in range(1,m):
dp[i][0]=dp[i-1][0]+g[i][0]
for i in range(1,n):
dp[0][i]=dp[0][i-1]+g[0][i]
for i in range(1,m):
for j in range(1,n):
dp[i][j]=max(dp[i-1][j], dp[i][j-1])+g[i][j]
print(dp[-1][-1])
#input1
#3 4
#2 -2 3 3
#-6 5 2 -8
#3 7 -5 4
#input2
#2 5
#1 2 3 1 -5
#-2 5 -8 2 1
#output1
#11
#output2
#10
```
:::
#### 小朋友上樓梯
:::spoiler
```python=1
#小朋友上樓梯最小成本
#DP
#一次只能走一階或兩階
#最後一步一定是一階或是兩階 #c[i-1] or c[i-2]
n=int(input())
c=list(map(int, input().split()))
for i in range(2,n):
c[i]=c[i]+min(c[i-1],c[i-2])
print(c[-1])
#input1
#8
#2 1 1 7 3 2 9 2
#input2
#5
#1 2 3 1 5
#output1
#9
#output2
#8
```
:::
#### 不連續的表演酬勞
:::spoiler
```python=1
#第一行為正整數n，第二行為n個正整數，代表每一天的酬勞
#限制:不能連續兩天表演
#選或不選
n=int(input())
p=list(map(int, input().split()))
dp=[0 for i in range(n)]
dp[0]=p[0]
dp[1]=max(dp[0], dp[1])
for i in range(2, n):
dp[i]=max(p[i]+dp[i-2], dp[i-1])
#如果選, 前一天就不能選-> p[i]+dp[i-2]
#如果沒選, 酬勞就是前一天->dp[i-1]
print(dp[n-1])
#input1
#5
#1 2 3 1 5
#input2
#8
#2 1 1 7 3 2 9 2
#output1
#9
#output2
#18
```
:::
# :memo: 正式試題
## 103
#### 103 撲克牌
:::spoiler
```python=1
from itertools import combinations #組合
for _ in range(int(input())):
ans=[]
s=list(map(int, input().split()))
data=list(combinations(s, 5)) #從6張卡片中取出5張
for card_type in data:
score=[] #5張牌的分數
suit=[] #花色--> 0黑桃 1紅心 2方塊 3梅花
point=[] #牌的點數
cnt=[] #計算每種點數共有幾張
for i in card_type:
suit.append((i-1)//13)
point.append((i-1)%13 if i%13!=0 else 13) #點數13因為取餘數剛好會等於0, 所以+13
for i in set(point): #計算點數的張數
cnt.append(point.count(i))
cnt.sort() #cnt要做排序, 因為[1, 4] != [4, 1]
min_card=min(card_type) #5張牌中最小的點數
point=sorted(point)
if point==[1, 2, 3, 4, 5] or point==[1, 10, 11, 12, 13]: #先處理順子的特殊情況
if len(set(suit))==1: #看所有牌是否為相同的花色
score.append(7)
else:
score.append(4)
elif point==[i for i in range(min_card, min_card+5)]: #順子的一般情況
if len(set(suit))==1:
score.append(7)
else:
score.append(4)
elif cnt==[1, 4]: #四張相同的牌-->四條
score.append(6)
elif cnt==[2, 3]: #三張相同的牌+兩張相同的牌-->葫蘆
score.append(5)
elif cnt==[1, 1, 3]: #三張相同的牌-->三條
score.append(3)
elif cnt==[1, 2, 2]: #兩張相同的牌+兩張相同的牌-->二條
score.append(2)
elif cnt==[1, 1, 1, 2]: #兩張相同的牌-->一條
score.append(1)
else:
score.append(0) #雜牌
ans.append(max(score))
print(max(ans))
```
:::
#### 103 樹的某節點到根節點的距離
:::spoiler
```python=1
n=int(input())
for _ in range(n):
a,b,c=map(int, input().split(','))
path=[[] for i in range(a)]
for i in range(a):
s=list(map(int, input().split()))
path[s[0]]=s[1:]
ans=[]
for i in range(b):
node=path[c][i]
cnt=0
while node!=999:
node=path[node][i]
cnt+=1
ans.append(cnt)
for i in ans[:-1]:
print(i, end=',')
print(ans[-1])
```
:::
## 104
#### 104 矩陣的乘法
:::spoiler
```python=1
for _ in range(int(input())):
a,b,c,d=map(int, input().split(','))
A=[]
B=[]
AB=[]
for i in range(a):
A.append(list(map(int, input().split())))
for i in range(c):
B.append(list(map(int, input().split())))
for i in range(a):
AB.append(list(map(int, input().split())))
INF=100000000
ty=INF
for i in range(a):
if 9999 in A[i]:
idxA=A[i].index(9999)
for k in range(d):
if B[idxA][k]!=0:
sum=0
for j in range(b):
if A[i][j]==9999:
e=B[j][k]
else:
sum+=A[i][j]*B[j][k]
ty=(AB[i][k]-sum)/e
if ty!=INF:
break
if ty==INF:
rB=[]
for i in range(d):
rB.append([])
for j in range(c):
rB[i].append(B[j][i])
#print(rB)
for i in range(len(rB)):
if 9999 in rB[i]:
t=rB[i].index(9999)
for k in range(a):
if A[k][t]!=0:
cnt=0
sum=0
for l in range(b):
if rB[i][l]==9999:
cnt=A[k][l]
else:
sum+=A[k][l]*rB[i][l]
ty=(AB[k][i]-sum)/cnt
if ty!=INF:
break
if ty!=INF:
break
print(int(ty))
#for i in B:
# print(i)
#print('---')
#for i in rB:
# print(i)
```
:::
#### 104 最小成本生成樹
:::spoiler
```python=1
for _ in range(int(input())):
parent=[int(i) for i in range(10)]
s=input().split()
data=[]
for i in s:
i=i.split(',')
data.append((ord(i[0])-65,ord(i[1])-65,int(i[2])))
data=sorted(data, key=lambda x:x[2])
cost=0
for i in data:
a,b,c=i[0],i[1],i[2]
if parent[a]==parent[b]:
continue
cost+=c
mn=min(parent[a],parent[b])
mx=max(parent[a],parent[b])
for j in range(len(parent)):
if parent[j]==parent[mn]:
parent[j]=parent[mx]
print(cost)
```
:::
## 105
#### 105E 是否為heap tree or binary search tree
:::spoiler
```python=1
for _ in range(int(input())):
tree=list(map(int, input().split(',')))
maxnode=len(tree)-1
max_heap=True
min_heap=True
bin_search=True
for i in range(len(tree)):
num=[]
num.append(tree[i])
if i*2+1<=maxnode:
num.append(tree[i*2+1])
if i*2+2<=maxnode:
num.append(tree[i*2+2])
if len(num)==1:
continue
if len(num)==2:
if num[0]>num[1]:
min_heap=False
if num[0]<num[1]:
max_heap=False
bin_search=False
if len(num)==3:
if num[0]>num[1] or num[0]>num[2]:
min_heap=False
if num[0]<num[1] or num[0]<num[2]:
max_heap=False
if num[0]<num[1] or num[0]>num[2]:
bin_search=False
if min_heap or max_heap:
print('H')
elif bin_search:
print('B')
else:
print('F')
```
:::
#### 105F 後序表示法
:::spoiler
```python=1
def f(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=f(n+1,ls,pos-1)
R=f(n+(pos-ls)+1,pos+1,rs)
if R==None:
R=[]
if L==None:
L=[]
for i in L:
postfix.append(i)
for i in R:
postfix.append(i)
for i in N:
postfix.append(i)
return postfix
for _ in range(int(input())):
infix=input().replace(' ','').split(',')
prefix=input().replace(' ','').split(',')
ans=f(0,0,len(prefix)-1)
print(','.join(ans))
```
:::
#### 105G 兩字串LCS
:::spoiler
```python=1
for _ in range(int(input())):
a='0'+input()
b='0'+input()
dp=[[0 for i in range(len(b))] for j in range(len(a))]
for i in range(1,len(a)):
for j in range(1,len(b)):
if a[i]==b[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[-1][-1])
```
:::
#### 105H 霍夫曼編碼
:::spoiler
```python=1
# 解法一
n=int(input())
tree=[]
#樹深度追蹤
def tree_lv(node,lv):
global tree
node[2]=lv
if node[3]>=0:
tree_lv(tree[node[3]],lv+1) #左兒子
if node[4]>=0:
tree_lv(tree[node[4]],lv+1) #右兒子
for i in range(0,n):
x=list(map(int, input().split(',')))
node=[]
for a in range(0,len(x)):
node.append([a,x[a],0,-1,-1])
node=sorted(node, key=lambda x:x[1])
tree=[]
num=len(node)
mx_num=num
#建樹, num>=len(tree) 為中繼點
while len(node)>1:
a=node[0]
b=node[1]
c=[num,a[1]+b[1],0,a[0],b[0]] #合併為中繼點
num+=1
tree.append(a)
tree.append(b)
node[1]=c
node.remove(a)
node=sorted(node,key=lambda x:x[1])
tree.append(node[0])
tree=sorted(tree,key=lambda x:x[0])
#print(tree)
tree_lv(node[-1],0)
#print(tree)
for i in range(0,mx_num-1):
print(tree[i][2], end=',')
print(tree[mx_num-1][2])
```
:::
:::spoiler
```python=1
# 解法二
for _ in range(int(input())):
s=list(map(int, input().split(",")))
n=l=len(s)
tree=[]
for i in range(l):
tree.append((i, s[i])) # 編號, 次數
result=[]
parent=[None]*l
while len(tree)>1:
tree.sort(key=lambda x:x[1])
a=tree.pop(0)
b=tree.pop(0)
newnode=a[1]+b[1]
tree.append((l, newnode))
parent.append(None)
parent[a[0]]=l
parent[b[0]]=l
l+=1
for i in range(n):
cu=parent[i]
cnt=0
while cu!=None:
cu=parent[cu]
cnt+=1
result.append(cnt)
print(*result, sep=",")
```
:::
## 106
#### 106B 羅馬數字轉整數
:::spoiler
```python=1
num={'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
def g(key):
pre=None
sum=0
for i in range(len(key)):
sum+=num[key[i]]
if (key[i]=='X' or key[i]=='V') and pre=='I':
sum-=2
if (key[i]=='L' or key[i]=='C') and pre=='X':
sum-=20
if (key[i]=='M' or key[i]=='D') and pre=='C':
sum-=200
pre=key[i]
return sum
for _ in range(int(input())):
key=input().strip()
print(g(key))
```
:::
#### 106G 樹
:::spoiler
```python=1
"""
這題跟zerojudge b517是否為樹類似
我的想法是先判斷這張圖是不是樹，不是樹的話，再去看他有沒有形成迴圈
要符合樹的條件有以下兩點：
1. 節點(node)-1 == 邊(edge) 的數量
2. DFS拜訪完的節點數量 == 輸入時出現過的節點數量
"""
def dfs(x, px): #判斷是否為樹函式
visited.append(x)
for i in range(20):
if path[x][i]==1 and i!=px and i not in visited:
dfs(i, x)
def Cycle(x, px): #尋找形成迴圈的所有節點
global start
visited_cyc.append(x)
for i in range(20):
if path[x][i]==1 and i==start and i!=px and i in visited_cyc:
visited_cyc.append(i)
if path[x][i]==1 and i!=px and i not in visited_cyc:
Cycle(i, x)
for _ in range(int(input())):
s=input().split()
path=[[0 for _ in range(20)] for _ in range(20)]
node=[0]*20 #紀錄出現過的節點
edge=0 #紀錄邊的數量
root=None
for i in s:
a, b=map(int, i.split(","))
if root==None:
root=a
path[a][b]=1; path[b][a]=1
node[a]=1; node[b]=1
edge+=1
node_num=node.count(1) #設為1的即為出現過的節點
is_tree=True #是否為樹
visited=[]
dfs(root, root)
#這邊用來判斷符不符合樹的條件
if node_num-1!=edge or len(visited)!=node_num:
is_tree=False
#如果是樹就直接輸出T
if is_tree:
print("T")
else:
cycle=[]
"""
如果visited==node_num，代表符合第二點條件，
那就不可能是森林，所以必定有形成迴圈的情況。
"""
if len(visited)==node_num:
for i in range(20):
if node[i]==1:
start=i #紀錄第一個走訪的節點
visited_cyc=[]
Cycle(i, i)
#如果重複走到第一個節點，代表此節點是迴圈節點之一
if visited_cyc.count(i)>1:
cycle.append(i)
print(*cycle, sep=", ")
#否則就是森林，直接輸出F
else:
print("F")
```
:::
## 107
#### 107B 井字棋
:::spoiler
```python=1
for x in range(int(input())):
lst=[]
for i in range(3):
lst.append(list(input().strip()))
player=[0]*3
for i in range(3):
if len(set(lst[i]))==1 and lst[i][0]!='0':
player[int(lst[i][0])]+=1
for i in range(3):
num=[]
for j in range(3):
num.append(int(lst[j][i]))
if len(set(num))==1 and num[0]!=0:
player[num[0]]+=1
if lst[0][0]==lst[1][1]==lst[2][2] and lst[0][0]!='0':
player[int(lst[0][0])]+=1
if lst[0][2]==lst[1][1]==lst[2][0] and lst[0][2]!='0':
player[int(lst[0][2])]+=1
mx=max(player)
if mx==0:
print(3)
else:
print(player.index(mx))
```
:::
#### 107G 找兩節點之間的最長路徑
:::spoiler
```python=1
def dfs(x):
if x>=l:
return -1
if tree[x]=="null":
return -1
return max(dfs(x*2+1)+1, dfs(x*2+2)+1)
for _ in range(int(input())):
tree=input()[1:-1].split(",")
l=len(tree)
ans=0
for i in range(l):
tmp=2+dfs(i*2+1)+dfs(i*2+2)
if tmp>ans:
ans=tmp
print(ans)
```
:::
#### 107H 循環排列
:::spoiler
```python=1
for _ in range(int(input())):
s=input().replace('[','').replace(']','').split(',')
ans=[]
visited=[]
for i in range(len(s)):
cyc=[]
idx=i+1
if idx not in visited:
while idx not in cyc:
visited.append(idx)
cyc.append(idx)
idx=int(s[idx-1])
if cyc!=[]:
ans.append(cyc)
print(ans)
```
:::
## 108
#### 108B 保齡球計分
:::spoiler
```python=1
for _ in range(int(input())):
data=[]
s=input().split()
for i in s:
if i=='X':
data.append(10)
elif i=='/':
data.append(10-data[-1])
else:
data.append(int(i))
total=0
cnt=0
while len(data)>0:
cnt+=1
score=0
a=data.pop(0)
if a==10:
score+=a+data[0]+data[1]
if cnt==10:
data.pop(0)
data.pop(0)
else:
if len(data)==0:
break
b=data.pop(0)
if a+b==10:
if cnt!=10:
score+=a+b+data[0]
else:
score+=a+b+data[0]
data.pop(0)
else:
score+=a+b
total+=score
print(total)
```
:::
#### 108F 循環小數
:::spoiler
```python=1
for _ in range(int(input())):
a,b=map(int, input().split())
q=str(a//b)+'.'
a=a%b
r=[]
r.append(a)
s1=''
round=''
while a>0:
a*=10
s1+=str(a//b)
a=a%b
if a in r:
c=r.index(a)
round=s1[0:c]+'('+s1[c:]+')'
break
else:
r.append(a)
if len(s1)>=50:
round+='('+s1+'...)'
break
if len(round)==0:
print(q+s1+'(0)')
else:
print(q+round)
```
:::
#### 108G 著色問題
:::spoiler
```python=1
n=int(input())
while n!=0:
m=int(input())
color=[-1 for i in range(n)]
f=True
for i in range(m):
a,b=map(int, input().split())
if color[a]==-1 and color[b]==-1:
color[a]=True
color[b]=False
elif color[a]==color[b]:
f=False
elif color[a]==-1:
color[a]=not(color[b])
else:
color[b]=not(color[a])
print('BICOLORABLE.' if f else 'NOT BICOLORABLE.')
n=int(input())
```
:::
#### 108H 數字迷宮
:::spoiler
```python=1
from heapq import *
for _ in range(int(input())):
n=int(input())
m=int(input())
g=[]
for _ in range(n):
g.append(list(map(int, input().split())))
visited=[[False for i in range(m)] for j in range(n)]
dxy=((0,1),(1,0),(-1,0),(0,-1))
visited[0][0]=True
q=[(g[0][0],0,0)]
while q:
val,r,c=heappop(q)
val=abs(val)
for i in range(4):
newr=r+dxy[i][0]
newc=c+dxy[i][1]
if 0<=newr<n and 0<=newc<m and not visited[newr][newc]:
visited[newr][newc]=True
g[newr][newc]=val+g[newr][newc]
heappush(q, (g[newr][newc], newr,newc))
print(g[-1][-1])
```
:::
## 109
#### 109B 打印機
:::spoiler
```python=1
for _ in range(int(input())):
n=list(input().strip())
num=''
for i in range(len(n)):
if int(n[i])==4:
n[i]='3'
num+='1'
else:
num+='0'
print(''.join(n), int(num))
```
:::
#### 109F 最大子數列問題(最大連續和)
:::spoiler
```python=1
for _ in range(int(input())):
mx=-1e9
s=list(map(int, input().split()))
sum=0
for i in s:
sum+=i
mx=max(sum, mx)
if sum<0:
sum=0
print(mx)
```
:::
#### 109G 錄音帶(背包問題)
:::spoiler
```python=1
def f(w,v):
for i in range(1,T+1):
for j in range(1,N+1):
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]
while 1:
try:
s=list(map(int, input().split()))
N=s[0]
T=s[1]
w=[0]+s[2:]
v=[0]+s[2:]
dp=[[0 for i in range(N+1)] for j in range(T+1)]
ans=f(w,v)
print(ans)
except:
break
```
:::
#### 109H 特殊郵件
:::spoiler
```python=1
for _ in range(int(input())):
n=int(input())
path=[0 for i in range(n+1)]
for i in range(n):
a,b=map(int, input().split())
path[a]=b
visited1=[0 for i in range(n+1)]
max_cost=0
for i in range(1,n+1):
visited=visited1.copy()
visited[i]=visited[0]=1
nxt=path[i]
cnt=0
while visited[nxt]==0:
cnt+=1
visited[nxt]=1
nxt=path[nxt]
if cnt>max_cost:
max_cost=cnt
ans=i
print(ans)
```
:::
## 110
#### 110M 矩陣的直積
:::spoiler
```python=1
a,b,c,d=map(int, input().split())
AB=[]
A=[]
B=[]
for _ in range(a):
A.append(list(map(int, input().split())))
for _ in range(c):
B.append(list(map(int, input().split())))
r=0
for i in range(a):
for j in range(c):
AB.append([])
for k in range(b):
for l in range(d):
AB[r].append(A[i][k]*(B[j][l]))
r+=1
for i in AB:
print(*i)
```
:::
#### 110N 字串編輯距離
:::spoiler
```python=1
a='0'+input()
b='0'+input()
dp=[[0 for i in range(len(b))] for i in range(len(a))]
for i in range(1,len(a)):
dp[i][0]=i
for i in range(1,len(b)):
dp[0][i]=i
for i in range(1,len(a)):
for j in range(1,len(b)):
if a[i]==b[j]:
dp[i][j]=dp[i-1][j-1]
else:
dp[i][j]=min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1
print(dp[-1][-1])
```
:::
#### 110O 三字串LCS
:::spoiler
```python=1
a='0'+input()
b='0'+input()
c='0'+input()
dp=[[[0 for i in range(len(c))] for i in range(len(b))] for i in range(len(a))]
for i in range(1,len(a)):
for j in range(1,len(b)):
for k in range(1,len(c)):
if a[i]==b[j]==c[k]:
dp[i][j][k]=dp[i-1][j-1][k-1]+1
else:
dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k],dp[i][j][k-1])
print(dp[-1][-1][-1])
```
:::
#### 110P 錢幣
:::spoiler
```python=1
n=int(input())
s=list(map(int, input().split()))
can=[False]*100001
max_v=sum(s)
can[0]=True
for i in range(n):
for j in range(max_v,s[i]-1,-1):
can[j]|=can[j-s[i]]
ans=[]
for i in range(1, max_v+1):
if can[i]:
ans.append(i)
print(len(ans))
print(*ans)
```
:::
#### 110Q 果子堆合併
:::spoiler
```python=1
while 1:
try:
n=int(input())
s=list(map(int, input().split()))
s.sort()
sum=0
for i in range(n-1):
a=s.pop(0)
b=s.pop(0)
sum+=a+b
s.append(a+b)
s.sort()
print(sum)
except:
break
```
:::
#### 110R 條條大路通羅馬
:::spoiler
```python=1
n,m=map(int, input().split())
path=[[] for i in range(n+1)]
for _ in range(m):
a,b=map(int, input().split())
path[a].append(b)
visited=[0 for i in range(n+1)]
def dfs(x):
visited[x]=1
for i in path[x]:
if visited[i]==0:
dfs(i)
a,b=map(int, input().split())
dfs(a)
if visited[b]==1:
print('Yes')
else:
print('No')
```
:::
## 111模擬
#### 111E1 二元樹
:::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
```
:::
#### 111E2 迷宮
:::spoiler
```python=1
import heapq
for _ in range(int(input())):
n=int(input())
m=int(input())
G=[]
for i in range(n):
s=list(map(int, input().split()))
G.append(s)
v=[[False for i in range(m)] for i in range(n)]
dx=(0,0,1,-1)
dy=(1,-1,0,0)
queue=[(G[0][0],0,0)]
while queue!=[]:
pair=heapq.heappop(queue)
num=pair[0]
y=pair[1]
x=pair[2]
for i in range(4):
r=dy[i]+y
c=dx[i]+x
if r<0 or c<0 or r>n-1 or c>m-1 or v[r][c]:
continue
G[r][c]=num+G[r][c]
v[r][c]=True
heapq.heappush(queue, (G[r][c],r,c))
print(G[-1][-1])
```
:::
#### 111T 路徑
:::spoiler
```python=1
def dfs(x,path):
path.append(tree[x])
r=0
if x*2+1<=max_node and tree[x*2+1]!='null':
r+=1
dfs(x*2+1, path.copy())
if x*2+2<=max_node and tree[x*2+2]!='null':
dfs(x*2+2, path.copy())
r+=1
if r==0:
ans.append(path)
tree=input().split(',')
max_node=len(tree)-1
ans=[]
dfs(0,[])
for i in ans:
print(*i,sep='->')
```
:::
## 111
#### 111G 編碼
:::spoiler
```python=1
for _ in range(int(input())):
s=input()
alpha=[]
num=[]
number=''
for i in range(len(s)):
if s[i].isalpha():
alpha.append(s[i])
if number!='':
num.append(int(number))
number=''
else:
number+=s[i]
if number!='':
num.append(int(number))
for i in range(len(num)):
print(alpha[i]*num[i], end='')
print()
```
:::
#### 111H 分組反轉字串
:::spoiler
```python=1
while 1:
s=input().split()
if s[0]=='0':
break
group=int(s[0])
data=s[1]
num=int(len(data)/group)
str1=''
ans=''
for i in range(len(data)):
str1+=data[i]
if (i+1)%num==0:
ans+=str1[::-1]
str1=''
print(ans)
```
:::
#### 111I 字元出現字數
:::spoiler
```python=1
data=[]
s=input().strip()
s1=list(set(s))
for i in s1:
data.append((ord(i), s.count(i)))
data.sort(key=lambda x:(x[1], -x[0]))
for i in data:
print(*i)
```
:::
#### 111J 質數
:::spoiler
```python=1
def f(n):
if n<2:
return False
for i in range(2, int(n**0.5)+1):
if n%i==0:
return False
return True
for aa in range(int(input())):
if aa>0:
print()
m,n=map(int, input().split())
for i in range(m, n+1):
if f(i):
print(i)
```
:::
#### 111K 質因數
:::spoiler
```python=1
def f(n):
k=0
for i in range(2, int(n**0.5)+1):
if n%i==0:
k=i
break
if k!=0:
num.append(k)
f(n//k)
else:
num.append(n)
while 1:
n=int(input())
if n==0:
break
if n==1:
print('1 : 0')
continue
num=[]
f(n)
num=set(num)
print('%d : %d'%(n,len(num)))
```
:::
#### 111M 格雷碼
:::spoiler
```python=1
n=int(input())
g=['0','1']
for i in range(1, n):
a=[]
b=[]
for j in g:
a.append('0'+j)
g=g[::-1]
for j in g:
b.append('1'+j)
g=a+b
for i in g:
print(i)
```
:::
#### 111Q 二元樹資訊
:::spoiler
```python=1
def height(l, r):
left=0
right=0
if l!=-1:
left=height(Node[l][0],Node[l][1])+1
if r!=-1:
right=height(Node[r][0],Node[r][1])+1
return max(left, right)
def depth(n, cnt_d):
d[n]=cnt_d
for i in Node[n]:
if i!=-1:
depth(i, cnt_d+1)
n=int(input())
Node=[]
parent=[-1]*n
deg=[]
h=[]
d=[None]*n
for i in range(n):
node, l, r=map(int, input().split())
Node.append((l, r))
#計算子節點數量、尋找父節點
for i in range(n):
cnt_deg=0
for j in Node[i]:
if j!=-1:
cnt_deg+=1
parent[j]=i
deg.append(cnt_deg)
#計算深度
root=parent.index(-1)
depth(root, 0)
#計算高度、輸出
for i in range(n):
h.append(height(Node[i][0],Node[i][1]))
print('node %d: parent = %d, degree = %d, depth = %d, height = %d,'\
%(i, parent[i], deg[i], d[i], h[i]))
```
:::
## 112
#### 112J 七段顯示器
:::spoiler
```python=1
for _ in range(int(input())):
n=int(input())
mod=n%2
if mod==0:
a="1"
n-=2
else:
a="7"
n-=3
b=(n//2)*"1"
print(a+b)
```
:::
#### 112K 字串
:::spoiler
```python=1
for _ in range(int(input())):
n=int(input())
ans=set()
s=list(input())
for i in range(len(s)-1):
s1=s.copy()
for j in range(i, i+2):
s1[j]=""
rst="".join(s1)
ans.add(rst)
print(len(ans))
```
:::
#### 112P 魔術方陣
:::spoiler
```python=1
arr=[]
for _ in range(3):
arr.append(list(map(int, input().split())))
a=arr[1][0]+arr[2][0]
b=arr[0][1]+arr[2][1]
c=arr[2][0]+arr[2][1]
total=(a+b+c)//2
arr[0][0]=total-a
arr[1][1]=total-b
arr[2][2]=total-c
for i in arr:
print(*i)
```
:::
#### 112R 樹的直徑
:::spoiler
```python=1
#直接窮舉每個節點到其他節點的距離#
def dfs(x, cnt):
visited[x]=1
distance[x]=cnt
for i in path[x]:
if visited[i]==0:
dfs(i, cnt+1)
n=int(input())
path=[[] for _ in range(n+1)]
for _ in range(n-1):
a, b=map(int, input().split())
path[a].append(b)
path[b].append(a)
rst=[]
for i in range(1, n+1):
visited=[0]*(n+1)
distance=[0]*(n+1)
dfs(i, 0)
rst.append(max(distance))
print(max(rst))
```
:::
#### 112S 迴圈
:::spoiler
```python=1
def dfs(x):
visited[x]=1
v1.append(x)
for i in path[x]:
if visited[i]==0:
dfs(i)
n, m=map(int, input().split())
path=[[] for _ in range(n+1)]
node=[0]*(n+1)
visited=[0]*(n+1)
for _ in range(m):
a, b=map(int, input().split())
path[a].append(b)
path[b].append(a)
node[a]=1
node[b]=1
ans=0
data=[]
for i in range(len(node)):
if node[i]==1 and visited[i]==0:
#print(i)
v1=[]
dfs(i)
data.append(v1)
for i in data:
for j in i:
if len(path[j])!=2:
#Hint 1.
#循環圖(cycle graph)內所有節點的鄰居和連出的邊都等於2
break
else:
ans+=1
print(ans)
```
:::
# 模擬試題
#### 104模擬3_1 是否為樹
:::spoiler
```python=1
for _ in range(int(input())):
data=[]
g={}
node=set()
edge=0
s=input().split()
for i in s:
a,b=i.split(',')
data.append((int(a),int(b)))
for a,b in data:
node.add(a)
node.add(b)
edge+=1
if a not in g:
g[a]=[b]
else:
g[a]+=[b]
if b not in g:
g[b]=[a]
else:
g[b]+=[a]
Tree=True
if edge!=len(node)-1:
Tree=False
if Tree:
node=list(node)
visited=[]
def dfs(x):
global Tree
visited.append(x)
for i in g[x]:
if i not in visited:
dfs(i)
dfs(node[0])
if len(node)!=len(visited):
Tree=False
if Tree:
print('T')
else:
print('F')
```
:::
#### 108旗立 尋找樹中最大路徑和
:::spoiler
```python=1
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))
#input 1
#6
#[-23, -48, 41, 10, 3, -46, 8, -39, 31, 32, -26, 40, -35, -28, 6, 26, 37, 5, 20, 16, 22, 37, 10, 17, 27, -20, -18, -20, -18]
#[1, -26, -26, -6, -36, 6, 13, 18, -45, 26, 38, -47, -1, -42, 5, -17, 46, 40, 6, -33, -35, -49, -26, 24, -15]
#[12, -27, 23, -23, 29, -44, 31, 9, 15, 41, 29, -9, -30, -27, 37, 14, 40, 35, 34]
#[-30, 47, -14, -9, 27, 7, 36, 15, -50, 1, -42, 22, -18]
#[-23, -1, -42, 47, 18, -1, 40, -7, -33, -2, -14, 44, -22, -13, -16, 39, 1, -18, 15, 12, -23, -14, 37, -49, null, 46]
#[-33, 20, 20, 38, -6, -7, -19, -9, 26, 37, -8, -41, -19, 4, -31, 44, -9, 13, 7, -23, 16, 13, 8, -10, 18, -33, -33, 47, 12]
#input 2
#9
#[17, -40, -42, 3, 25, 19, -24, -28, 11, -40, -49, -32, -16, -24, -35, -41, 39, -20, -33, 39, 35]
#[21, 23, -33, 5, 48, 27, 43, 17, 40, -3, -8, 8, -48, 3, 48, -39, -23, 24, 47, 9, 8, -46, 14]
#[-26, -39, -25, 44, -2, 16, -2, -41, 19, -4, 31, 8, -36, -21, -5, 18, -7, -39, 22, 43, 19, -38, 6, 42, -32, 41, -36]
#[3, 8, -42, -14, -46, 3, 15, 18, 24, -9, 32, 44, -2, -16, -44, -34, 4, -37, -5, 1, 41, -36, 43, 43, 40, 32, -18, 5]
#[38, 1, 11, -47, 35, 39, 22, -28, -41, 26, 31, -50, 20, 21, 41, 50, -29]
#[26, 15, 28, 20, -14, -36, 20, 16, -34, -4, -27, -29, -40, -16, 49, 34, -20, -18, -6, -1, -32, -5, -18, -47, 20, 21]
#[-1]
#[-1,9,20,null,null,15,7]
#[-3,-2,-1]
#outout1
#84
#64
#146
#81
#119
#144
#output 2
#39
#194
#85
#127
#179
#208
#-1
#43
#-1
```
:::
#### 109模擬 關節點
:::spoiler
```python=1
while 1:
n=int(input())
if n==0:
break
path=[[0 for i in range(n+1)] for j in range(n+1)]
AP=[]
while 1:
x=list(map(int, input().split()))
if x[0]==0:
break
for i in range(1,len(x)):
path[x[0]][x[i]]=1
path[x[i]][x[0]]=1
visited1=[0 for i in range(n+1)]
for i in range(1, n+1): #1~n+1-> 每一個節點
visited=visited1.copy()
BFS=[]
pos=i%n+1
BFS.append(pos)
while BFS:
pos=BFS.pop(0)
visited[pos]=1
for j in range(1,n+1):
if j==i:
continue
if visited[j]==0 and path[pos][j]==1:
BFS.append(j)
for j in range(1,n+1):
if visited[j]==0 and i!=j:
AP.append(i)
break
print(len(AP))
```
:::
Google Drive
Gist
Clipboard
Sign in with Wallet
