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我。

2020年12月28日 星期一

e531: 10415 - Eb Alto Saxophone Player

UVA 10415

CPE 2020/12/22考題

解題心得:

每個音階都有對應的指法,如果欲彈奏下一個音階須按下的手指與上一個重複,則不用額外計算。

1.建立MAP來儲存每個音階要按的手指

2.建立一個狀態表(陣列)來儲存每個手指當前狀態(0沒按1按),在建立一個記數表來記錄每個手指按下幾次。

3.每次讀到下一個音階時先去狀態表查閱當前手指狀態,如果該按而還沒按則按下(記數+1)。

4.依據MAP的資料把該放開的手指放開(狀態表)。


程式碼如下:

#include <iostream>
#include <map>
#include <vector>
#include <string>
using namespace std;

int main()
{
    cin.tie(0) , cin.sync_with_stdio(0);
    map<char , vector<int>> mc;
    mc['c'] = {0,0,1,1,1,0,0,1,1,1,1};
    mc['d'] = {0,0,1,1,1,0,0,1,1,1,0};
    mc['e'] = {0,0,1,1,1,0,0,1,1,0,0};
    mc['f'] = {0,0,1,1,1,0,0,1,0,0,0};
    mc['g'] = {0,0,1,1,1,0,0,0,0,0,0};
    mc['a'] = {0,0,1,1,0,0,0,0,0,0,0};
    mc['b'] = {0,0,1,0,0,0,0,0,0,0,0};
    mc['C'] = {0,0,0,1,0,0,0,0,0,0,0};
    mc['D'] = {0,1,1,1,1,0,0,1,1,1,0};
    mc['E'] = {0,1,1,1,1,0,0,1,1,0,0};
    mc['F'] = {0,1,1,1,1,0,0,1,0,0,0};
    mc['G'] = {0,1,1,1,1,0,0,0,0,0,0};
    mc['A'] = {0,1,1,1,0,0,0,0,0,0,0};
    mc['B'] = {0,1,1,0,0,0,0,0,0,0,0};
    int t;
    cin >> t;
    string s;
    getline(cin , s);
    while(t--){
        int finger[11] = {0};
        int fingerCount[11] = {0};
        getline(cin , s);
        for(int i = 0; i < s.length(); i++){
            if(mc.count(s[i]) == 0) continue;
            for(int j = 1; j < 11; j++) {
                if(mc[s[i]][j] == 1) {
                    if(finger[j] == 0) {
                        fingerCount[j]++;
                        finger[j] = 1;
                    }
                }
            }
            for(int k = 0; k <11; k++){
                finger[k] = mc[s[i]][k];
            }
        }
        
        for(int i = 1; i < 11 ;i++){
            cout << fingerCount[i] <<" ";
        }
        cout << "\n";
    }
    
    return 0;
}

o079. 4. 最佳選擇

 題目描述: 給一個長度為 n 的正整數序列 a1,a2...an ,你可以執行多次操作 (包含 0 次),每次操作只能選擇這個序列的第一個或最後一個數字,再將這個數字從序列中刪除並自己搜集起來。 求滿足總和不超過 k 且搜集的數字奇數和偶數個數相同的條件下,所能搜集的數字總和最...