class Node:
def __init__(self):
self.father = []
self.child = []
self.dis = -99999999
s = set()
n = int(input())
d = {}
for i in range(n):
c,f = input().split()
if c not in d:
d[c] = Node()
if f not in d:
d[f] = Node()
d[c].father.append(f)
d[f].child.append(c)
start,target = input().split()
d[start].dis = 0
p = [start]
keep = True
while keep:
for i in p:
for j in d[i].father:
if j not in s:
s.add(j)
d[j].dis = d[i].dis-1
p.append(j)
if j == target:
keep = False
break
for j in d[i].child:
if j not in s:
s.add(j)
d[j].dis = d[i].dis+1
p.append(j)
if j == target:
keep = False
break
if keep == False: break
print(d[target].dis)2024年1月9日 星期二
k862. 輩份比較
2024年1月8日 星期一
m685. 三角形計數器
辨別三角形相同的方式有很多,我們選其中一個方式來解題,假設兩個三角形,各三個邊由小到大分別是a,b,c 及 a1,b1,c1,如果a/b==a1/b1 and b/c == b1/c1 and c/a == c1/a1,那麼這兩個三角形及為相似三角形,最後用上set來濾掉重複的三角形即可。
n = int(input())
s = set()
for i in range(n):
d = [int(i) for i in input().split()]
d.sort()
s.add(str(d[0]/d[1]) + str(d[1]/d[2]) + str(d[2]/d[0]))
print(len(s))
m702. 傑出校友票選活動
題目要比對各個人名出現的次數,因為人名是字串,不方便直接用陣列做排序與索引,所以可以先放到map裡面去計次,記完之後再放回vector裡做排序即可。
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
int main()
{
cin.tie(0) , cin.sync_with_stdio(0);
int n,m;
cin >> n >> m;
map<string , int> t;
for(int i = 0; i < n; i++) {
string s;
cin >> s;
t[s] += 1;
}
vector<pair<int , string>> v;
for(auto it=t.begin(); it != t.end(); it++) {
pair<int,string> p;
p.first = it->second;
p.second = it->first;
v.push_back(p);
}
sort(v.begin() , v.end());
for(int i = 0; i < m; i++) {
cout << v[v.size()-1-i].second << " ";
}
cout << endl;
return 0;
}
l960. 星期幾?
題目明確給定正確的資料,將其放入清單中,再收取測資作比對即可。
h = ['Sunday', 'Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday']
s = input()
if s not in h:
print('error')
else:
print(h.index(s))
APCS 2024.01 m934. 4. 合併成本
要計算最小合併成本,就需要用到DP,DP的精髓就是分而治之,假設今天只有3個資料要合併,-1,3,-5,那麼情形不外乎是(-1,(3,-5) ) 或是 ((-1, 3),-5),從兩個之中找最小成本。如果這時候再增加一個資料如-1,3,-5,6那麼情形就是((-1,3,-5),6)或是((-1,3),(-5,6))或是(-1,(3,-5,6))之中找最小成本,我們可以發現,只要每次切割區間的左右邊界,直到找到1.左右邊界相同,代表沒有合併成本,2.左右邊界差一,那就是相鄰兩個合併,可以直接運算,3.這個左右邊界夾出來的最小成本已經算過,直接回傳資料。
以下附上完整程式碼:
def check(left , right):
if dp[left][right] != 9999999:
return dp[left][right]
if left == right: return 0
elif left == right-1:
return abs(d[left] - d[right])
mm = 9999999
for i in range(left , right):
l,r = check(left , i) , check(i+1 , right)
dp[left][right] = min(dp[left][right],abs((table[i+1] - table[left]) - (table[right+1] - table[i+1])) + l+r)
mm = min(mm,dp[left][right])
return mm
n = int(input())
d = [int(i) for i in input().split()]
dp = [[9999999 for i in range(n)] for j in range(n)]
table = [0]
for i in d:
table.append(table[-1] + i)
print(check(0,n-1))
APCS 2024.01 m932. 2. 蜜蜂觀察
按照慣例,APCS的第二題就是考二維陣列的運用,特別是邊界的判別。解這題的時候如果你可以畫個圖,或是心中畫個圖的畫就會簡單許多。
現實的資料
m,n,k = [int(i) for i in input().split()]
s = []
for i in range(m):
s.append(input())
step = [int(i) for i in input().split()]
table = [[-1,0],[0,1],[1,1],[1,0],[0,-1],[-1,-1]]
x,y = 0,m-1
sets = set()
ans = ''
for i in step:
yy,xx = table[i]
if xx+x < 0 or xx+x >= n or yy+y < 0 or yy+y >= m:
ans += s[y][x]
sets.add(s[y][x])
continue
y,x = yy+y,xx+x
ans += s[y][x]
sets.add(s[y][x])
print(ans)
print(len(sets))APCS 2024.01 m933. 3. 邏輯電路
乍看之下,本來覺得可以直接硬解,所以沒多想便用了很多清單來解題,沒想到過程中發現要記錄的資訊量很大,寫著寫著程式越來越複雜,所幸從頭開始,運用自訂結構,將每個節點所需要的欄位明確定義出來,這題就會簡單許多。
解題技巧運用到BFS再加上一些條件式判斷,依下圖為例:
class Node:
def __init__(self):
self.nexts = []#該節點是那些節點的輸入
self.val = -1
self.delay = 0
self.gate = None
self.ipt = []#那些節點是本節點的輸入
def t():
pp,q,r,m = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
t = [int(i) for i in input().split()]
nodes = []
for i in range(pp+q+r):
nodes.append(Node())
for i in range(pp):
nodes[i].val = p[i]
for i in range(pp , pp+q):
nodes[i].gate = t[i-pp]
#print(nodes)
for i in range(m):
a,b = [int(i) for i in input().split()]
a -= 1
b -= 1
nodes[a].nexts.append(b)
p = [i for i in range(pp)]
'''1 為 AND、2 為 OR、3 為 XOR、4 為 NO'''
for i in p:
if nodes[i].val == -1:continue
for j in nodes[i].nexts:#i節點是j節點的輸入
nodes[j].ipt.append(i)#j節點的輸入有添加i節點
if nodes[j].gate == 4 and len(nodes[j].ipt) == 1:
nodes[j].val = int(not nodes[nodes[j].ipt[0]].val)#j節點的值,是j的輸入的值的相反
nodes[j].delay = nodes[nodes[j].ipt[0]].delay + 1
p.append(j)
elif nodes[j].gate != 4 and len(nodes[j].ipt) == 2:
p1,p2 = nodes[nodes[j].ipt[0]] , nodes[nodes[j].ipt[1]]
if nodes[j].gate == 1:
nodes[j].val = int(p1.val and p2.val)
if nodes[j].gate == 2:
nodes[j].val = int(p1.val or p2.val)
if nodes[j].gate == 3:
nodes[j].val = int(p1.val != p2.val)
nodes[j].delay = max(p1.delay , p2.delay) + 1
p.append(j)
mm = 0
for i in range(pp+q , pp+q+r):
mm = max(nodes[nodes[i].ipt[0]].delay , mm)
print(mm)
for i in range(pp+q , pp+q+r):
print(nodes[nodes[i].ipt[0]].val , end = ' ')
print()
t() 如果有問題,歡迎留言會email我。
o079. 4. 最佳選擇
題目描述: 給一個長度為 n 的正整數序列 a1,a2...an ,你可以執行多次操作 (包含 0 次),每次操作只能選擇這個序列的第一個或最後一個數字,再將這個數字從序列中刪除並自己搜集起來。 求滿足總和不超過 k 且搜集的數字奇數和偶數個數相同的條件下,所能搜集的數字總和最...
-
要計算最小合併成本,就需要用到DP,DP的精髓就是分而治之,假設今天只有3個資料要合併,-1,3,-5,那麼情形不外乎是(-1,(3,-5) ) 或是 ((-1, 3),-5),從兩個之中找最小成本。如果這時候再增加一個資料如-1,3,-5,6那麼情形就是((-1...
-
題目描述: 給一個長度為 n 的正整數序列 a1,a2...an ,你可以執行多次操作 (包含 0 次),每次操作只能選擇這個序列的第一個或最後一個數字,再將這個數字從序列中刪除並自己搜集起來。 求滿足總和不超過 k 且搜集的數字奇數和偶數個數相同的條件下,所能搜集的數字總和最...
-
乍看之下,本來覺得可以直接硬解,所以沒多想便用了很多清單來解題,沒想到過程中發現要記錄的資訊量很大,寫著寫著程式越來越複雜,所幸從頭開始,運用自訂結構,將每個節點所需要的欄位明確定義出來,這題就會簡單許多。 解題技巧運用到BFS再加上一些條件式判斷...
