這題是很好的遞迴問題，每次遞迴的時候都要帶入此次遞迴的左右邊界、及這次是要取區間最大還是取區間最小的flag。
完整程式如下：
def t(l , r , isBig):
if l == r-1:
return d[l]
m = (l+r)//2
if isBig:
g = max(t(l,m,0) , t(m,r,0))
else:
g = min(t(l,m,1) , t(m,r,1))
return g
n = int(input())
d = [int(i) for i in input().split()]
print(t(0,n,1))
白話來說，就是把測資去掉所有2、3、5的因數後，如果只剩下1，就顯示ugly，反之顯示beautiful，這邊就運用while來重複檢測輸入是否尚能被2、3、5整除，如果可以就將其整除後再檢查一次，直到不能在除2、3、5為止。
程式碼如下：
def t():
n = int(input())
while n % 2 == 0:
n //= 2
while n % 3 == 0:
n //= 3
while n % 5 == 0:
n //= 5
if n == 1:
print('ugly')
else:
print('beautiful')
t()
三個輸入乘以固定的比率，算出最終答案，如果是使用python要小心浮點數運算預設是帶小數的資料，記得要取整數。
以下附上完整程式：
try:
while True:
p,n,m = [int(i) for i in input().split()]
print(int(p*0.2+n*0.3+m*0.5))
except:
pass
考試中常常用到排序，只是往往不會只是單純排序，有些時候，會需要在排序的資料裡面，添加一些不必要排序的資料，就像這題，表面是針對戰鬥力排名，但輸出的時候是要輸出攻擊力與防禦力，所以基本上的做法就是依序將[戰鬥力、攻擊力、防禦力]當成一筆資料塞入陣列之中，透過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])
沒有太過分的求因數，小心避開當輸入為1、找因數的迴圈終點記得開根號處理，很多神奇的技巧如6n+1,6n-1，找因數的時候一次間隔兩個數....技巧都不需用上。
以下附上完整程式碼：
def t():
n = int(input())
if n == 1:
print(0)
return
p = int(n**0.5) + 1
total = 0
for i in range(1,p):
if n % i == 0:
j = n//i
if j == i or j == n:
total += i
else:
total += i + j
print(total)
t()
這題就是單純的16進制轉換題，如果同樣的題目，是十進制出題，那是絕對的送分題，以十進制來看，假設收到三個char(a,b,c)需要我們將它組成一個百位數數字，那麼程式作法拆解下來就是total = a - char(0) ，再來是total = total * 10 + b - char(0) ，最後是total = total * 10 + c - char(0) ，數學式子去理解就是total = a * 100 + b * 10 + c，那麼將同樣概念運用在這題就沒問題了。
以下附上完整程式：
d = input().split()
ft,st = 0,0
f,s = d
for i in range(len(f)):
ft = ft * 26 + (ord(f[i]) - ord('A')+1)
for i in range(len(s)):
st = st * 26 + (ord(s[i]) - ord('A')+1)
print(st - ft + 1)
這題是標準的DP問題，扣除每一行的頭跟尾(都是1)，每一行的資料都是由上一行的正上方與左上方提供。
以下附上完整程式碼：
n = int(input())
d = [[1 for i in range(21)] for j in range(21)]
for i in range(1,n+1):
for j in range(i):
if j != 0 and j != i-1:
d[i][j] = d[i-1][j] + d[i-1][j-1]
print(d[i][j] , end = ' ')
print()
這是一題標準的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
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)辨別三角形相同的方式有很多，我們選其中一個方式來解題，假設兩個三角形，各三個邊由小到大分別是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))
題目要比對各個人名出現的次數，因為人名是字串，不方便直接用陣列做排序與索引，所以可以先放到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;
}
題目明確給定正確的資料，將其放入清單中，再收取測資作比對即可。
h = ['Sunday', 'Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday']
s = input()
if s not in h:
print('error')
else:
print(h.index(s))
要計算最小合併成本，就需要用到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的第二題就是考二維陣列的運用，特別是邊界的判別。解這題的時候如果你可以畫個圖，或是心中畫個圖的畫就會簡單許多。
現實的資料
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))乍看之下，本來覺得可以直接硬解，所以沒多想便用了很多清單來解題，沒想到過程中發現要記錄的資訊量很大，寫著寫著程式越來越複雜，所幸從頭開始，運用自訂結構，將每個節點所需要的欄位明確定義出來，這題就會簡單許多。
解題技巧運用到BFS再加上一些條件式判斷，依下圖為例：
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我。
