顯示具有 [程式解題]難度中級 標籤的文章。 顯示所有文章
顯示具有 [程式解題]難度中級 標籤的文章。 顯示所有文章

2024年6月16日 星期日

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月9日 星期二

m283. 螞蟻的擴散

         這是一題標準的DP題目,假設以dp[x][y]做為起點開始走,那麼從dp[x][y]走一步後,dp[x-1][y]跟dp[x][y-1],dp[x-1][y-1]這三個位置個會增加dp[x][y]/3的機率被走到,以此類推直到X或是Y軸為0,最後計算起點跟終點的比值即可。

        下列附上程式:

import math

def cal(x, y):
    # 初始化dp陣列
    dp = [[0] * 11 for _ in range(11)]
    
    # 設定起點的機率為1
    dp[x][y] = 1*3**(x+y)
    
    # 遞迴計算dp
    for i in range(x, 0, -1):
        for j in range(y, 0, -1):
            dp[i-1][j] += dp[i][j] / 3
            dp[i][j-1] += dp[i][j] / 3
            dp[i-1][j-1] += dp[i][j] / 3
    
    ans = int(dp[x][y] - dp[0][0])
    cc = math.gcd(int(ans), int(dp[x][y]))
    dp[x][y] //= cc
    ans //= cc
    print(str(ans) + "/" + str(dp[x][y]))
    # 將分數化簡
    '''common_factor = math.gcd(int(result), 81)
    result /= common_factor'''

try:
    while True:
        x,y = [int(i) for i in input().split()]
        cal(x,y)
except:
    pass

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

2020年9月21日 星期一

d396: 00524 - Prime Ring Problem

出處:UVA524

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

有一個環(ring)是由 n 個圈圈所組成的(在這裡 n 一定是個偶數),我們想要把 1 到 n 的自然數各放到一個圈圈中,使得相鄰 2 個圈圈中的數的和一定是質數。下圖為 n=6 的情形。

每組測試資料只包含一整數 n(0 < n <= 16)

看到上面的輸入範圍就決定暴力DFS解了,但為了幫忙加速一下,還是建立一個1~31(15+16)的質數表來加速運算。

程式碼如下:

如果有任何疑問歡迎留言或私訊討論。


prime = [0 , 0 , 1 , 1 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 1 , 0
 , 1 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 
 0 , 0 , 1 , 0 , 1]

a = []
n = 0
index = 0
def dfs(d , d1 , count , ss):
  if prime[d+d1] == 0: return
  if count == n:
    if prime[1 + d1] == 1:
      print(ss)
    return

  global a
  for i in range(2 , n+1):
    if a[i] == 1: continue
    a[i] = 1
    dfs(d1 , i , count+1 , ss + str(i) + " ")
    a[i] = 0
  


try:
  while True:
    ans= ""
    a = []
    index += 1
    n = int(input())
    a = [0]*(n+1);
    ans = "1 "
    a[1] = 1
    print("Case " + str(index) + ":" )
    for i in range(2 , n+1 , 2):
      a[i] = 1
      #ans += str(i) + " "
      dfs(1 , i , 2 , ans + str(i) + " ")
      a[i] = 0
      
except EOFError:pass


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