APCS 2026/3

註： 本人不是什麼佬，以下內容有可能有誤，請多包涵

1.比例分割

題目：

其實這題就是fancy一點的二分搜罷了，應該算送分？

解答：

from itertools import accumulate

def get_sec(ll, l, r):
    if l > r:
        return 0
    return ll[r]-ll[l-1]

def main():
    n, m = map(int, input().split())
    nl = list(map(int, input().split()))
    il = [map(int, input().split()) for i in range(m)]
    nl = [0] + list(accumulate(nl))
    for l, r, a, b in il:
        t = a/(a+b)
        u, d = r, l-1
        while u-d > 1:
            idx = (u+d)//2
            nt = get_sec(nl, l, idx) / get_sec(nl, l, r)
            if nt >= t:
                u = idx
            elif nt < t:
                d = idx
        print(u)
main()

2.觀光旅遊

題目：

這題就有點難 (我卡很久QwQ)，一開始就有想到用差分陣列的概念紀錄每一個表演開始和結束的日期，但要開一個長度10⁸的list還要做前綴合陣列大概3秒就過去了 (記憶體也會暴斃給你看)，絞盡腦汁才想出這個不知道叫啥的防法，原理是因為原本前綴合list會有大量連續的重複元素，所以改紀錄每個區間開始的index和這個區間內的值，再用二分搜找原本的index屬於哪個區間。

解答：

def main():
    ml = {}
    n, m = map(int, input().split())
    tl = list(map(int, input().split()))
    dl = [map(int, input().split()) for i in range(m)]
    sp = set()
    for i, j in dl:
        if not ml.get(i): ml[i]=0
        if not ml.get(j+1): ml[j+1]=0
        ml[i]+=1
        ml[j+1]-=1
        sp.add(i)
        sp.add(j+1)
    sp.add(0)    
    ml[0] = 0
    sl = sorted(list(sp))
    c = 0
    for i in sl:
        ml[i]+=c
        c = ml[i]
    total = 0
    for i in tl:
        u, d = len(sl), 0
        ans = None
        while u-d > 1:     
            idx = (u+d)//2
            if sl[idx]>i:
                u = idx
            elif sl[idx]<i:
                d = idx
            else:
                ans = idx
                break
        if ans is None:
            total+=ml[sl[d]]
            continue
        total+=ml[sl[ans]]
    print(total)
main()

3.校運代表隊

題目：

我看到題目時的反應是「這他媽三小」，不過後來發現數字給的不大，說實話就是要你用dfs枚舉，然後剪枝不要剪的太爛都會過 (應該ㄅwww)，後來縫縫補補也算是寫了一個差一點TLE的版本

答案：

import sys
def main():
    n, m, r, k, t = map(int, input().split())
    inp = list(map(int, input().split()))
    cl = [inp[i*r: (i+1)*r] for i in range(m)]
    idx = 0
    def dfs(q, p, depth):
        nonlocal idx, cl, r, k, t 
        for i in range(r):
            if cl[depth][i] in p:
                continue
            np = p.copy()
            np.add(cl[depth][i])
            for j in list(range(i+1, r))+[None]:
                nnp = np.copy()
                if j is not None:
                    if cl[depth][j] in nnp:
                        continue
                    nnp.add(cl[depth][j])
                nq = []
                nq.append((r*depth)+i+1)
                if j is not None:
                    nq.append((r*depth)+j+1)
                nq = q+nq
                if len(nq) == k:
                    idx+=1
                    if idx == t:
                        print(' '.join(map(str, nq)))
                        sys.exit(0)
                if len(nq) >= k:
                    continue
                if depth+1 == len(cl): break
                dfs(nq, nnp, depth+1)
        if depth+1 == len(cl): return
        dfs(q, p, depth+1)
    dfs([], set(), 0)
main()

(說實話，寫到後面我都快搞不懂我在寫啥了www