Codeforces Round 909 (Div. 3) A - F

補題補題。

All problems solved by python

A - Game with Integers (CF1899 A)

題意

兩個人玩遊戲，給定一個數 NN , 每人能夠對數字進行執行 +1+1 或 −1-1 的操作，若操作完 NN 是 33 的倍數則該名玩家獲勝，但若超過10次操作沒有結果，則後手獲勝，問先手的人能否獲勝。

思路

若第一輪先手無法獲勝，則後手必可以將先手的操作抵銷，故先手獲勝的條件是第一次操作就能獲勝，即 N mod 3N \bmod 3 餘 11 或 22。

1
2
3
4
5
6
7
8
T = int(input())

for _ in range(T):
    N = int(input())
    if N % 3 == 0:
        print("Second")
    else:
        print("First")

B - 250 Thousand Tons of TNT (CF1899 B)

題意

有 NN 個箱子，接下來給定一個 Array AA ， AiA_i 代表第 ii 個箱子的重量，要將這些箱子裝在卡車上，每輛卡車所裝的箱子數要相同，求最重的卡車與最輕的卡車的重量差的最大值。

思路：枚舉+前綴和

  • 先將 AA 的前綴和算出來，方便之後計算卡車上的重量。
  • 之後枚舉每輛卡車上的箱子數目 kk ，若 NN 可以被 kk 整除，則可以裝箱子，否則不行。計算每輛卡車有 kk 個箱子時，最重和最輕的卡車的重量，並更新答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from itertools import accumulate

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

    pre = list(accumulate(A, initial=0)) # prefix sum

    ans = 0
    for k in range(1, N // 2 + 1): # 枚舉每輛卡車裝的箱子數量 k 
        if N % k == 0:
            mx = -float('inf')
            mn = float('inf')
            for j in range(k, N + 1, k):
                mx = max(mx, pre[j] - pre[j - k]) # 單一卡車上最大重量
                mn = min(mn, pre[j] - pre[j - k]) # 單一卡車上最小重量
            ans = max(ans, mx - mn) # 找出最大的差值
    print(ans)

C - Yarik and Array (CF1899 C)

題意

求最大連續子陣列和，但要求連續兩個元素的奇偶性不同。

思路：DP

令 dp[i]dp[i] 表示 以 aia_i 結尾的最大子陣列和，檢查奇偶性是否相同，若相同則 dp[i]=aidp[i] = a_i ，否則 dp[i]=dp[i−1]+aidp[i] = dp[i-1] + a_i ，最後答案為 dpdp 中的最大值。

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

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

    dp = [0] * (N+1) # dp[i] 表示 以 a_i 結尾的最大子陣列和
    dp[1] = A[1]
    for i in range(2, N+1):
        if A[i-1] % 2 != A[i] % 2: # 奇偶性不同
            dp[i] = max(dp[i-1] + A[i], A[i])
        else: # 奇偶性相同
            dp[i] = A[i]
    print(max(dp[1:]))

D - Yarik and Musical Notes (CF1899 D)

題意

給定一個陣列 aa ，令 bib_i = 2ai2 ^ {a_i}，求滿足 bibjb_i ^ {b_j} = bjbib_j ^ {b_i} 的數對 (i,j)(i, j) 的數量

思路：數學 + Counter

  • 先化簡 bibjb_i ^ {b_j} = bjbib_j ^ {b_i}

(2ai)(2aj)=(2aj)(2ai)⇒2ai∗2aj=2aj∗2ai⇒ai∗2aj=aj∗2ai⇒aiaj=2(ai−aj)\begin{align} & (2^{a_i}) ^ {(2^{a_j})} = (2^{a_j}) ^ {(2^{a_i})} \\ & \Rightarrow 2^{a_i * 2^{a_j}} = 2^{a_j * 2^{a_i}} \\ & \Rightarrow {a_i * 2^{a_j}} = {a_j * 2^{a_i}} \\ & \Rightarrow \frac{a_i}{a_j} = 2^{(a_i-a_j)} \\ \end{align}

  • aiaj\frac{a_i}{a_j} 是 22 的冪次方，所以 ai=aja_i = a_j 或 ai=1,aj=2a_i = 1, a_j = 2 或 ai=2,aj=1a_i = 2, a_j = 1 ，遍歷 aa 時，同時維護每個數的出現數量即可。
  • 如果不對對訪問量最大的兩個 key 先初始化的話，就算用 defaultdict 也會有 TLE 的問題，
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import sys
from collections import defaultdict

input = sys.stdin.readline
print = sys.stdout.write

T = int(input())

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

    ans = 0
    cnt = defaultdict(int)
    cnt[1] = cnt[2] = 0 # 不加這行會 TLE

    for val in A:
        ans += cnt[val] # ai = aj
        if val == 1: # ai = 2, aj = 1
            ans += cnt[2]
        elif val == 2: # ai = 1, aj = 2
            ans += cnt[1]
        cnt[val] += 1
    print(f"{ans}\n")

E - Queue Sort (CF1899 E)

題意

  • 給定一個由 nn 個整陣列成的 Array AA ，需要用以下操作將 AA 做非遞減排序，求操作數。 (以下兩個步驟視為1次操作)
  • 將 AA 的第一個元素取出，並放到最後一個元素。
  • 將這個被放到最後的元素與前一個元素交換，直到它成為第一個元素或是嚴格大於前一個元素。

思路：觀察

  • 可以觀察 testcase #3 ， [4,3,1,2,6,4]→[3,1,2,6,4,4]→[1,2,6,3,4,4]→[2,6,3,4,4,1]→[6,3,4,4,1,2,]→[6,3,4,4,1,2,][4,3,1,2,6,4] \rightarrow [3,1,2,6,4,4] \rightarrow [1,2,6,3,4,4] \rightarrow [2,6,3,4,4,1] \rightarrow [6,3,4,4,1,2,] \rightarrow [6,3,4,4,1,2,]
  • 操作到最小元素後，相鄰的順序就不會再發生變化，因此若最小元素後有遞減的情況，則不可能操作成非遞減序列，反之，操作數為最小元素前的元素個數。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
T = int(input())

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

    min_val = float("inf")
    min_idx = -1
    for idx, num in enumerate(A):
        if num < min_val:
            min_val = num
            min_idx = idx
    flag = False # 最小元素後是否有遞減的情況
    for i in range(min_idx + 1, N):
        if A[i - 1] > A[i]: # 出現遞減的情況
            flag = True
            break
    if flag:
        print(-1)
    else:
        print(min_idx)

F - Alex’s whims (CF1899 F)

題意

  • 有 nn 個頂點，可以以任意方式構造成一棵樹，接下來有 dd 個數，表示共有 dd 輪。每一輪可以選擇一個已有的邊將其刪除，然後再連一邊形成一顆新的樹，要求每一輪都有兩個葉子節點的距離恰好為 did_i 。
  • 輸出 n−1n-1 條邊表示樹的構造，和每輪的操作方式。答案不唯一，只要符合條件即可

思路

  • 創造一條有 nn 個點的Path(鏈)，再每一輪中，我們固定第一個點和最後一個點的距離為我們要的 did_i ，因此每次操作都是把最後一個點移動到某個點上
  • 以範例的第2個測資為例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
T = int(input())

for _ in range(T):
    N, Q = map(int, input().split())
    D = [int(input()) for _ in range(Q)]
    # print edges
    for i in range(1, N):
        print(i, i + 1)
    # print operation
    last = N - 1 # 上次移動到哪個點上
    for d in D:
        if last == d:
            print(-1, -1, -1)
        else:
            print(N, last, d)
            last = d