程式客棧

2024年1月8日星期一

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;
}

2020年10月30日星期五

b127: 會議中心（Room）

題目來源：https://zerojudge.tw/ShowProblem?problemid=b127

技巧：費式數列

題目老實說，看文字有點複雜😂😂😂😂😂😂😂，但仔細觀察圖面，不難發現其實是費式數列，這也是解題的一些心得，每當拿到一個新的題目，最快讓你了解題意的通常不會是題目敘述，多觀察輸出輸入，或是圖形化示例。

以下附上程式碼：

#include <iostream>
using namespace std;


int main() {
  cin.tie(0),cin.sync_with_stdio(0);
  int n = 0;
  int arr[46];
  arr[0] = 0;
  arr[1] = 1;
  arr[2] = 2;
  for(int i = 3; i < 46; i++) {
    arr[i] = arr[i-1] + arr[i-2];
  }
  int i;
  while(cin >> i) {
    cout << arr[i] << "\n";
  }
}

2020年10月29日星期四

d411: 算了好久......

題目來源：https://zerojudge.tw/ShowProblem?problemid=d411

技巧：大數運算

這題要注意的是，M值高達10^9999，這必然沒辦法用基本的數字運算來處理。

以下附上程式碼：

#include <iostream>
#include<string>
#include <math.h>
using namespace std;

int n;
void mod(string num , int m) {
  int check = 0;
  for(int i = 0; i < num.length(); i++) {
    check *= 10;
    check += num[i] - '0';
    check = check % m;
  }
  if(check == 0) {
    cout <<"YA!!終於算出"+num+"可被2的" + to_string(n)+"次整除了!!\n";
  }  else {
    cout << "可惡!!算了這麼久"+num+"竟然無法被2的"+to_string(n) + "次整除\n";
  }
  
}

int main() {
  cin.tie(0),cin.sync_with_stdio(0);
  int m;
  string num;
  while(cin >> num >> n) {
    m = pow(2 , n);
    mod(num , m);
  }
}

d356: NOIP2002 1.級數求和

題目來源：https://zerojudge.tw/ShowProblem?problemid=d356

已知：Sn= 1＋1／2＋1／3＋…＋1／n，求給定任意K直，找出SN>K時，N為何

範例輸入

範例輸出

簡易程式碼如下：

#include <iostream>
using namespace std;
int main() {
  cin.tie(0),cin.sync_with_stdio(0);
  double b = 1,c = 1,a = 1;
  cin >> a;
  while(b <= a) {
    c+=1;
    b += 1/c;
  }
  cout << c << "\n";
}

2020年10月20日星期二

f314: 3. 勇者修煉 APCS 2020.10.17

https://zerojudge.tw/ShowProblem?problemid=f314

APCS 2020.10.17

沒想到今年第三題就需要用到演算法，感覺這次的5分應該會比7月的考試更有鑑別度了。

50*10000的矩陣，每個點有三個方向，如果用DFS可能要做到海枯石爛才做得完。

仔細觀察一下，其實這題跟

https://zerojudge.tw/ShowProblem?problemid=a693

https://zerojudge.tw/ShowProblem?problemid=a694

吞食天地這兩題有87%像，如果等等程式碼看不太懂的話，建議可以先挑戰吞食天地的題組，這題我是每一行從左掃到右，從右掃到左，去找單行每個點的最佳解。(當然上走到下也要走)。

試著舉例：

第I個點的最佳解為：

max(從左走到第I-1個點+第I個點的經驗值 , 第I個點的經驗值 , 從右走到第I+1個點+第I個點的經驗值 , 從上面走到第I個點+第I個點的經驗值)。

每個點依循這原則，加上判斷一下臨界點就可以囉。

程式碼如下：

如果有問題歡迎留言或來信討論

import sys
ans=0-sys.maxsize
m,n=tuple([int(i) for i in input().split()])
MAP=[[int(j) for j in input().split()] for i in range(m)]
dp_left =[[ans for i in range(n)] for j in range(m)]
dp_right=[[ans for i in range(n)] for j in range(m)]
dp =[[ans for i in range(n)] for j in range(m)]

dp_right[0][0] = MAP[0][0]
dp_left[0][n-1] = MAP[0][n-1]
for i in range(1,n):
  dp_right[0][i] = max([dp_right[0][i-1] + MAP[0][i] , MAP[0][i]])
  dp_left[0][n-i-1] = max([dp_left[0][n-i] + MAP[0][n-i-1] , MAP[0][n-i-1]])
  dp[0][i] = max([dp_right[0][i] , dp_left[0][i]])
  dp[0][n-i-1] = max([dp_right[0][n-i-1] , dp_left[0][n-i-1]])

half = int(n/2)
for j in range(1,m):
  for i in range(0,n):
    if i == 0:
      dp_right[j][i] = dp[j-1][i]
    else:
      dp_right[j][i] = max([dp_right[j][i-1], dp[j-1][i]])
    dp_right[j][i] += MAP[j][i]

    if i == 0:
      dp_left[j][n-i-1] = dp[j-1][n-i-1]
    else:
      dp_left[j][n-i-1] = max([dp_left[j][n-i] , dp[j-1][n-i-1]])
    dp_left[j][n-i-1] += MAP[j][n-i-1]

    if i >= half:
      dp[j][i] = max([dp_right[j][i] , dp_left[j][i]])
      dp[j][n-i-1] = max([dp_right[j][n-i-1] , dp_left[j][n-i-1]])


print(max(dp[m-1]))

f313: 2. 人口遷移 APCS 2020.10.17

https://zerojudge.tw/ShowProblem?problemid=f313

APCS 2020.10.17

這題比較要注意的是，先遷徙，再加總，如果邊遷徙邊作加總會算錯的唷，這題測資很善良的讓你知道邊遷邊加是錯的，如果是我就不會這麼善良了^.^。

解題程式碼如下：

如果有任何問題歡迎留言或來信討論。

import sys
a = []
r,c,k,m = tuple([int(i) for i in input().split()])

for i in range(r):
  a.append([int(j) for j in input().split()])
for i in range(m):
  b = [[0 for _ in range(c)] for _ in range(r)]
  for j in range(r):
    for l in range(c):
      if a[j][l] != -1:
        temp = int(a[j][l] / k)
        if j-1 >= 0 and a[j-1][l] != -1:
          b[j][l] -= temp
          b[j-1][l] += temp
        if j+1 < r and a[j+1][l] != -1:
          b[j][l] -= temp
          b[j+1][l] += temp
        if l-1 >= 0 and a[j][l-1] != -1:
          b[j][l] -= temp
          b[j][l-1] += temp
        if l+1 < c and a[j][l+1] != -1:
          b[j][l] -= temp
          b[j][l+1] += temp
  for j in range(r):
    for l in range(c):
      if a[j][l] == -1: continue
      a[j][l] += b[j][l]


maxI = -1
minI = sys.maxsize
for i in range(r):
  for j in range(c):
    if a[i][j] == -1: continue
    if a[i][j] > maxI:
      maxI = a[i][j]
    if a[i][j] < minI:
      minI = a[i][j]

print(minI)
print(maxI)

訂閱：文章 (Atom)

程式客棧

2024年1月8日星期一

APCS 2024.01 m933. 3. 邏輯電路

2020年12月28日星期一

e531: 10415 - Eb Alto Saxophone Player

2020年10月30日星期五

b127: 會議中心（Room）

2020年10月29日星期四

d411: 算了好久......

d356: NOIP2002 1.級數求和

2020年10月20日星期二

f314: 3. 勇者修煉 APCS 2020.10.17

f313: 2. 人口遷移 APCS 2020.10.17

o079. 4. 最佳選擇

檢舉濫用情形

文章分類

2024年1月8日 星期一

2020年12月28日 星期一

2020年10月30日 星期五

2020年10月29日 星期四

2020年10月20日 星期二

2024年1月8日星期一

2020年12月28日星期一

2020年10月30日星期五

2020年10月29日星期四

2020年10月20日星期二