顯示具有 APCS 標籤的文章。 顯示所有文章
顯示具有 APCS 標籤的文章。 顯示所有文章

2024年6月16日 星期日

o077. 2. 電子畫布

題目描述:

有一個 H ╳ W 的電子畫布,一開始數值都是 0 代表未填色,接下來請模擬 N 次畫筆操作。

每次畫筆操作為選一個座標 (r,c) 停留 t 秒,他會將曼哈頓距離 <= t 的區塊染上顏色 x。若有多個顏色重複填到相同區塊,顏色的數值會累加起來。

請輸出 N 次操作後的畫布狀態。


這題簡單來說就是要想個找出距中心點等距的菱形座標。

我思考的方式很簡單,首先找到中心點,並根據該點的資料找出他離他最遠單的Y座標端點。
得到,以下這個迴圈。

for y in range(r-t,r+t+1):

注意一下,菱形的關鍵就是從中心點到任一端點都是等距,所以我們先把中心點座標取這次拿到的Y座標算出差距得到:

ydif = abs(r-y)#ydif就是中心點與這次y座標的差距

已知ydif+xdif=t,現在t跟ydif都是已知,所以xdif = t-abs(ydif),所以就可以得出下面這個迴圈:

for x in range(c-(t-ydif) , c+(t-ydif)+1):

菱形矩陣搞定後,這題就沒有其他問題囉,以下是完整程式。


def t():
    h,w,n = [int(i) for i in input().split()]
    tt = [[0 for i in range(w)] for j in range(h)]
    
    
    for j in range(n):
        r,c,t,q = [int(i) for i in input().split()]
        for y in range(r-t,r+t+1):
            if y < 0 or y > h-1: 
                continue
            ydif = abs(r-y)
            for x in range(c-(t-ydif) , c+(t-ydif)+1):
                if x < 0 or x > w-1:
                    continue
                tt[y][x] += q
    for i in tt:
        for j in i:
           print(j , end = ' ')
        print()
t()

o076. 1. 特技表演

有一個城鎮有 n 棟高樓,樓高分別為 h1,h2,.....hn,市長想要在城鎮中心舉辦高空特技表演,該特技表演會從某棟大樓上朝右側滑翔至地面。

為了表演人員的安全,滑翔的路徑樓高必須越來越低,請你找出一個最長的滑翔路徑。

簡單來說就是要從資料中找出最長的降冪集合,這題沒什麼時間問題,直接透過迴圈查找

def t():

    n = int(input())

    d = [int(i) for i in input().split()]

    c = 0

    k = 9999999999

    ans = 0

    for i in d:

        if i < k:

            c += 1

        else:

            if ans < c:

                ans = c

            c = 1

        k = i

    if ans < c:

        ans = c

    print(ans)


t()

o078. 3. 缺字問題

 題目敘述:


給定一個大小為 K 個字母的集合和字串 S,求出在使用該集合所組出長度為 L 字串中,不為字串 S 子字串的最小字典序字串為何。

自如字母集合{a,c,m},其能組出長度為 2 的字串字典序由小到大排序為: aa < ac < am  < ca < cc < cm < ma < mc < mm。字串 S 為accaamcm,因此 ma 為不在 S 內的最小字典序字串。


這題看起來就很dfs,一般APCS第三題時間上是不會過關,但這題可以,想必官方考慮到國高中生期末考將至,難度有稍微調降了。簡單來說,想辦法求出a,c,m中不重複的所有排序組合。

以下是超白話思考順序

DFS思考的重點有兩個,每次要做什麼,終止條件是什麼。

啥都還沒想到的時候就先寫出

def dfs():#先把函式建起來

再來開始思考每次呼叫函示要做什麼,以這題為例,我們要嘗試在函式內組出不同的字母排列組合,所以應該需要一個字串參數帶入函式之中。所以:

def dfs(s):

有了參數後,可以想想看終止條件是什麼,終止條件就是組出長度為L的字串,所以:

def dfs(s):

    if len(s) == L:

        dosomething

長度到了之後呢,我們程式的目標是要找出不在字串S中的子字串啊,所以:

def dfs(s):

    if len(s) == L:

        if s not in S:#代表s不在S之中

            print(s)

            return False#不要繼續找了

        return True#繼續找吧

    for i in k:

        if dfs(ss+i) == False:

            return False

k = list(input())

l = int(input())

S = input()

dfs("" )

再加上剪枝(優化加速),就變成以下這樣囉:

def dfs(ss):
    if ss in dic:
        return True
    dic[ss] = 1
    if len(ss) == l:
        if ss not in existStr:
            print(ss)
            return False
        return True
    for i in k:
        if dfs(ss+i) == False:
            return False

k = list(input())
l = int(input())
s = input()

existStr = set(s[i:i+l] for i in range(len(s) - l + 1))
dic = {}
dfs("" )




我把剪枝(用來加速)的部分標藍色,基本上這題不剪枝,也不會超時,非常佛心呢。

2024年1月12日 星期五

APCS 2024.01 m931. 1. 遊戲選角

         考試中常常用到排序,只是往往不會只是單純排序,有些時候,會需要在排序的資料裡面,添加一些不必要排序的資料,就像這題,表面是針對戰鬥力排名,但輸出的時候是要輸出攻擊力與防禦力,所以基本上的做法就是依序將[戰鬥力、攻擊力、防禦力]當成一筆資料塞入陣列之中,透過sort指令,因為系統預設的sort指令會先依第一個欄位排序,如果第一個欄位相同就繼續比第二個,以此類推。

        完整程式如下:

n = int(input())
p = []
for i in range(n):
    q,m = [int(i) for i in input().split()]
    p.append([q**2 + m**2 , q , m])
p.sort()

print(p[-2][1] , p[-2][2])

2024年1月8日 星期一

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

f312. 1.人力分配 APCS 2020.10.17

APCS 2020.10.17第一題的題目:
其實近幾年題目的第一題考驗的都不是程式能力,而是閱讀能力,基本上第一題所需要用到的就是基本條件式與迴圈的結合,只要讀懂題意,相信都是可以做出來的。
題目就如上面所說,A1 A2 B1 B2 C1 C2由測資提供,X2跟X1則依據題目所提供的總人數有所變化,以總人數2人為例,則兩間工廠的人數有[0,2] , [1,1] , [2,0]這三種組合。


解題程式如下:

如果有不清楚的歡迎留言或直接寄信給我討論囉。

import sys
a,b,c = tuple([int(i) for i in input().split()])
a1,b1,c1 = tuple([int(i) for i in input().split()])
n = int(input())
maxValue = -1 * sys.maxsize
for i in range(n+1):
  y = a * i*i + b * i + c + a1*(n-i)*(n-i) + b1 * (n-i) + c1
  if y > maxValue:
    maxValue = y

print(maxValue)


2020年9月19日 星期六

c292: APCS2017-0304-3數字龍捲風

 題目來源:APCS2017-0304

檢測平台:https://zerojudge.tw/ShowProblem?problemid=c292


首先先定義四個方向的X、Y偏移量:

EX.

a = [[0 , -1] , [-1 , 0] , [0 , 1] , [1 , 0]]
這題乍看可能不好著手,這時需要做的就是好好檢視測試數據,
仔細觀察測資,你會發現基本上每個方向移動的步數為1,1,2,2,3,3......

好囉,程式碼如下:
如果有問題歡迎留言或私訊討論囉。
a = [[0 , -1] , [-1 , 0] , [0 , 1] , [1 , 0]]

n = int(input())
d = int(input())
t = []
for i in range(n):
  t.append([int(i) for i in input().split()])

x = y = int(len(t) / 2)
s = str(t[x][y])

end = 0
for i in range(1,len(t)+1):
  if end == 1: break
  for k in range(0 , 2):
    if end == 1:break
    for j in range(i):
      x += a[d][0]
      y += a[d][1]
      if x < 0 or y < 0 or x == len(t) or y == len(t):
        end = 1
        break;
      s += str(t[x][y])
    d += 1
    d %= 4
print(s)

2020年7月13日 星期一

b967: 第 4 題 血緣關係 解題心得

zerojudge題目網址:https://zerojudge.tw/ShowProblem?problemid=b967
題目來源:APCS考題
題目網址:
https://docs.google.com/viewer?a=v&pid=sites&srcid=ZGVmYXVsdGRvbWFpbnx6c2dpdGl0aXR8Z3g6NDQ4NmIyNzljY2Q2N2ZiYg

解題策略:
將這棵樹視為無向樹,從任一起點出發,找尋離自己最遠的兩個端點,且不能經過重複的點,將距離相加就是答案,例如以0為起點,015+036或014+036距離都是2,所以2+2=4,或者以1為起點出發。14+1036或15+1036距離為1+3=4。
為了完成上面解法,在收測資的時候需要讓每個端點都知道自己可以到哪幾個端點。

程式碼如下:
有任何問題歡迎留言或私我或是MAIL給我。
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> nodes;
vector<int> book;
int ans;


int dfs(int now, int last_steps) {
    book[now] = 1;
    int dis1 = 0 , dis2 = 0 , dis;
    for (int x : nodes[now]) {
        if (!book[x]) {
            dis = dfs(x, last_steps + 1) + 1;
            if (nodes[now].size() == 0) continue;
            if (dis >= dis1) {
                dis2 = dis1;
                dis1 = dis;
            }
            else if (dis > dis2) {
                dis2 = dis;
            }
        }
    }
    ans = max(max(ans, dis1 + dis2), dis1 + last_steps);
    return dis1;
}

int main() {
    cin.tie(0),cin.sync_with_stdio(false);
    int n, a, b;
    while (cin >> n) {
        ans = 0;
        nodes.clear();
        nodes.resize(n);
        book.assign(n, 0);
        for (int i = 1; i < n; i++) {
            cin >> a >> b;
            nodes[a].push_back(b);
            nodes[b].push_back(a);
        }
        dfs(0, 0);
        cout << ans << "\n";
    }
}

o079. 4. 最佳選擇

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