2024年1月9日 星期二

k862. 輩份比較

        假設B,C是A的祖先,D,E是A的子孫,F是E的子孫,如果我們先忽略輩分這件事情,單純從A點走到F,那就是一個單純的BFS就可以解決的事情,只要在BFS的基礎上,讓每個節點記錄自己的父輩與子孫輩的成員即可。





下列附上程式碼:


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月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的第二題就是考二維陣列的運用,特別是邊界的判別。解這題的時候如果你可以畫個圖,或是心中畫個圖的畫就會簡單許多。

        現實的資料


        但我們收到清單後,資料長成這樣s = ['TyuI','ABaB']。舉個例子,起點從A開始,假設先往右上走,從上圖來說會走到T,但從清單中的結構來說,位置只是往上跑而已,依照這樣的邏輯,依序將,六個方向對應到清單的變化整理出來,這題就沒有問題了。以下附上完整程式:

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))

        有問題歡迎留言,或email與我討論。





APCS 2024.01 m933. 3. 邏輯電路

        乍看之下,本來覺得可以直接硬解,所以沒多想便用了很多清單來解題,沒想到過程中發現要記錄的資訊量很大,寫著寫著程式越來越複雜,所幸從頭開始,運用自訂結構,將每個節點所需要的欄位明確定義出來,這題就會簡單許多。

        解題技巧運用到BFS再加上一些條件式判斷,依下圖為例:


        第0步的起點為g1,g2,g3,g4,g5,第一步的起點為g6,g7,g8,g9,第二步的起點為g6,g10,g11,第三步為g11,你會發現第一步的g6沒有馬上走到g12,這也是這題的重點之一,因為第一次走到g1->g6的時候,g6還算不出答案,它還在等待g7->g6,因為g6必須湊齊g1,g7才能得到輸出。
        以下附上完整程式:

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 且搜集的數字奇數和偶數個數相同的條件下,所能搜集的數字總和最...