Codeforces Round 912 (Div. 2) A - C

pB思路沒錯，結果計算時的條件判斷沒寫好，rejudge後WA了，難受。但不管如何，人菜就是要多補題。

All problems solved by python

A - Halloumi Boxes (CF1903 A)

題意

給出一個長度為 $n$ 的Array $a$ ，每次可以選擇一個長度最多為 $a$ 的子陣列進行反轉，問是否能夠使 $a$ 排序成非降序。

思路：Bubble Sort

對於 $k \geq 2$ 的情況，我們可以模擬Bubble Sort的過程，故只要 $k \geq2$ 就一定可以使 $a$ 排序成非降序。
對於 $k = 1$ 的情況，則無法做排序，故只要 $a $中存在 $a_{i-1} > a_i$ 的情況，就無法使 $a$ 排序成非降序。

T = int(input())

def check(A): # A是否為升序
    for i in range(1, len(A)):
        if A[i-1] > A[i]:
            return False
    return True

for tc in range(1, T+1):
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    flag = check(A)
    if flag or K >= 2:
        print("YES")
        continue
    else:
        print("NO")
        continue

B - StORage room (CF1903 B)

題意

給出一個長度為 $n*n$ 的矩陣 $M$ ，當 i\neqj 時， $M[i][j]$ 表示 $a_i | a_j$ 的結果，問是否能找出一個長度為 $n$ 的Array $a$ ，使得 $a_i | a_j = M[i][j]$ ，如果有多種答案，輸出任一個即可。

思路：貪心

盡量讓 $a_i$ 越大越好，越大的 $a_i$ 對於 $a_i | a_j$ 能有越大的貢獻，故 $a_i = M[i][1] \& M[i][1] \& ... \& M[i][n]$ 。
計算 AND 時注意初始化 $a_i$ 的條件，最後檢查檢查 $a$ 是否滿足條件即可。

T = int(input())

def check(A, M): # 滿足 A[i] | A[j] = M[i][j]
    n = len(A)
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            if A[i] | A[j] != M[i][j]:
                return False
    return True

for tc in range(1, T+1):
    N = int(input())
    M = [list(map(int, input().split())) for _ in range(N)]

    A = [0] * N

    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            if (i==0 and j==1) or (i>=1 and j==0):
                A[i] = M[i][j]
            else:
                A[i] = A[i] & M[i][j]
    if check(A, M):
        print("YES")
        print(*A)
    else:
        print("NO")

C - Theofanis’ Nightmare (CF1903 C)

題意

給定一個包含 $n$ 個元素的 Array $a$ ，可以將其任意切分成若干個子陣列，使 $\Sigma_{i=1}^k i \cdot sum_i$ 最大，其中 $k$ 為子陣列數量， $sum_i$ 表示第 $i$ 個子陣列的總和。

思路：後綴和 + 貪心

考慮每個元素的貢獻度，為使貢獻盡可能的大，若該位置的後綴和為正，則可以切分成新的子陣列，也就是增加後面位置元素的貢獻度。
考慮 $A[i:]$ 的貢獻度， $A[0:]$ 貢獻度必為1，先加入答案。如果後綴和 $suf[i]$ 為正，則可以增加貢獻度，即在原答案的基礎上加上 $suf[i]$ 。
計算時由前往後或由後往前皆可，由前往後方便理解，由後往前可以一邊計算後綴和，一邊計算貢獻度，並節省空間複雜度。

from itertools import accumulate

T = int(input())

for tc in range(1, T+1):
    N = int(input())
    A = list(map(int, input().split()))

    
    # 後綴和，suf[i] = sum(A[i:])
    suf = list(accumulate(A[::-1], initial=0))[::-1]

    # 考慮貢獻度
    ans = suf[0] # 貢獻度都至少為1
    for i in range(1, N):
        if suf[i] >= 0: # 為使結果盡量大，當 sum(A[i:]) >= 0，可以增加A[i:]的貢獻度，即 += suf[i]
            ans += suf[i]
    print(ans)