114 商競題解

前言

這些都是我用gpt寫的，因為我好累，剛寫完一篇文，不過做題的思路基本上都跟我當時做的差不多。

題解

A

1
2
y = int(input())
print(y + 1911)

沒啥好說。

B

1
2
3
4
n = int(input())
if n < 0:
    n = -n
print(n)

沒啥好說。

C

1
2
3
4
n = int(input())
if n % 2 == 0:
    n += 1
print(n)

沒啥好說。

D

1
2
3
4
5
6
7
8
9
T = int(input())
for _ in range(T):
    a, b = map(int, input().split())
    total = 0
    if a % 2 == 0:
        a += 1
    for i in range(a, b+1, 2):
        total += i
    print(total)

就這樣，應該還有更簡潔的寫法，不過能過就是好寫法。

E

1
2
3
n = int(input())
rev = int(str(n)[::-1])
print(rev)

沒啥好說。

F

1
2
3
4
5
6
7
8
9
10
11
12
s = input()
target = "hello"
j = 0
for c in s:
    if c == target[j]:
        j += 1
    if j == len(target):
        break
if j == len(target):
    print("YES")
else:
    print("NO")

就這樣而已，沒有必要想得太難哈。

G

1
2
3
4
5
6
7
s = input().lower()
vowels = set("aoyeui")
result = ""
for c in s:
    if c not in vowels:
        result += "." + c
print(result)

就這樣，寫的時候要注意看題目，我以為只要看aeiou就好了，繳完結果還有一個y，哭。

H

1
2
3
4
5
6
7
8
9
10
a, b = input().split()

if a == b:
    print(0)
elif (a == "B" and b == "T") or (a == "T" and b == "C") or (a == "C" and b == "W") or (a == "W" and b == "B"):
    print(1)
elif (b == "B" and a == "T") or (b == "T" and a == "C") or (b == "C" and a == "W") or (b == "W" and a == "B"):
    print(2)
else:
    print(0)

就這樣慢慢寫，要用字典也行啦。

I

1
2
3
4
5
6
s = input()
password = ""
for i in range(len(s)-1):
    dist = abs(ord(s[i]) - ord(s[i+1]))
    password += str(dist)
print(password)

嗯，好像其實也還好，基本題而已。

J

1
2
3
4
5
6
ip = input().split(".")
binary_ip = ""
for part in ip:
    binary_part = bin(int(part))[2:].zfill(8)
    binary_ip += binary_part
print(binary_ip)

zfill好用。

K

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
s = input()  
letter_to_num = {
    'A':10,'B':11,'C':12,'D':13,'E':14,'F':15,'G':16,'H':17,'I':34,
    'J':18,'K':19,'L':20,'M':21,'N':22,'O':35,'P':23,'Q':24,'R':25,
    'S':26,'T':27,'U':28,'V':29,'W':32,'X':30,'Y':31,'Z':33
}

weights = [1,9,8,7,6,5,4,3,2,1,1]

res = []

for letter in letter_to_num:
    num = letter_to_num[letter]
    digits = [num//10, num%10] 
    for c in s:
        digits.append(int(c)) 

    total = 0
    for i in range(11):
        total += digits[i] * weights[i]

    if total % 10 == 0:
        res.append(letter)

res.sort()
output = ""
for letter in res:
    output += letter
print(output)

這種題以前我會用條件式去判斷，有些特殊的再處理，然後經過特殊的之後就要-1之類的這樣，但現在我都用建表了哈哈，直接打比較省力啦。

L

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
T = int(input())

for _ in range(T):
    N = int(input())
    arr = list(map(int, input().split()))
    
    max_ending_here = 0
    max_so_far = -1000000 
    
    for num in arr:
        max_ending_here += num
        if max_ending_here > max_so_far:
            max_so_far = max_ending_here
        if max_ending_here < 0:
            max_ending_here = 0
    
    if max_so_far > 0:
        print(f"The maximum winning streak is {max_so_far}.")
    else:
        print("Losing streak.")

基本的DP題，就把if max_ending_here < 0:想成是如果這個投資會讓我虧錢，我就重新開始。

M

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
T = int(input())

for _ in range(T):
    a,b = list(map(int,input().split()))
    
    count = 0
    f1 = 1
    f2 = 2
    
    if f1 >= a and f1 <= b:
        count += 1
    if f2 >= a and f2 <= b:
        count += 1
    
    while True:
        f3 = f1 + f2
        if f3 > b:
            break
        if f3 >= a:
            count += 1
        f1, f2 = f2, f3
    
    print(count)

Fibonacci建議用dp，要用遞迴可以用@cache。

N

1
2
3
4
5
6
7
8
9
10
11
n = int(input())
points = []

for _ in range(n):
    x, y = map(int, input().split())
    points.append((x, y))

points.sort(key=lambda p: (p[0], p[1]))

for p in points:
    print(p[0], p[1])

lambda很好用。。。不熟建議寫個Sort! Sort!! and Sort!!!練練看，要注意那個mod是c的mod。

O

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import math

MAX = 31623

is_prime_small = [True] * (MAX + 1)
is_prime_small[0] = is_prime_small[1] = False
for i in range(2, int(math.isqrt(MAX)) + 1):
    if is_prime_small[i]:
        for j in range(i*i, MAX+1, i):
            is_prime_small[j] = False
def is_prime(n):
    if n <= MAX:
        return is_prime_small[n]
    for i in range(2, MAX+1):
        if is_prime_small[i] and n % i == 0:
            return False
    return True

T = int(input())
for _ in range(T):
    N = int(input())
    if not is_prime(N):
        print(f"{N} is not a prime number.")
    else:
        R = int(str(N)[::-1])
        if R != N and is_prime(R):
            print(f"{N} is an emirp number.")
        else:
            print(f"{N} is a prime number.")

記得要學埃式篩喔。

P

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
T = int(input())

for _ in range(T):
    N = int(input())
    n = N
    sum_factors = 0
    i = 2
    while i*i <= n:
        while n % i == 0:
            sum_factors += i
            n //= i
        i += 1
    if n > 1:
        sum_factors += n
    print(sum_factors)

這題好像在ntub zerojudge上面有變簡單，我在比賽現場有寫出一樣的code出來，結果過不了（TLE）。

Q

1
2
3
4
5
6
7
8
9
10
11
12
squares = [i*i for i in range(1, 31623)]

T = int(input())
for _ in range(T):
    a, b = map(int, input().split())
    count = 0
    for sq in squares:
        if sq > b:
            break
        if sq >= a:
            count += 1
    print(count)

就list解，這樣就好了，list這樣其實蠻快的，阿為啥是31623？，因為 $\sqrt{10^{9}}\approx 31622.7766$。

R

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
N, M = map(int, input().split())
G = [list(map(int, input().split())) for _ in range(N)]

dp = [[0]*M for _ in range(N)]
dp[0][0] = G[0][0]
for j in range(1, M):
    dp[0][j] = dp[0][j-1] + G[0][j]

for i in range(1, N):
    dp[i][0] = dp[i-1][0] + G[i][0]

for i in range(1, N):
    for j in range(1, M):
        dp[i][j] = G[i][j] + min(dp[i-1][j], dp[i][j-1])

print(dp[N-1][M-1])

dp，賽後才想到要怎麼解，如果要練dp的話，應該只能多寫了，不要看ChatGPT，自己推導出來。

S

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent, x, y):
    x_root = find(parent, x)
    y_root = find(parent, y)
    if x_root == y_root:
        return False
    parent[y_root] = x_root
    return True

T = int(input())
for _ in range(T):
    m, n = map(int, input().split())
    edges = []
    total_sum = 0
    for _ in range(n):
        x, y, z = map(int, input().split())
        edges.append((z, x, y))
        total_sum += z

    edges.sort()
    parent = list(range(m))
    mst_sum = 0
    for z, x, y in edges:
        if union(parent, x, y):
            mst_sum += z

    print(total_sum - mst_sum)

這個我是真沒輒了，真不會，我以為最後一題會像往年考DFS、BFS或是什麼樹的，結果確實考了樹，結果是最小生成樹，哭。

結語

嗯，照我看，明年的題目應該會更難，加油。