Codeforces Round 913 (Div. 3) A - F

又是賽後補題的一天，pB 用 python 吃了 TLE ，用 c++ 才 AC 、pC 被題目騙麻了、pD 想到二分但沒想到可以用區間做。要難受的事情太多了，那就來補題吧。

All problems solved by python, pB also solved by c++.

A - Rook (CF1907 A)

題意

給定一個國際象棋的棋盤，和一個車的位置，輸出車可以攻擊到的格子編號，輸出順序沒有要求。

思路

簽到題，直接模擬即可。

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

for tc in range(1, N+1):
    x, y = list(input())
    ans = [x + str(i)  for i in range(1, 9) if i != int(y)]
    ans += [chr(ord('a') + i) + y for i in range(8) if  ord('a') + i != ord(x)]
    print(*ans, sep="\n")

B - YetnotherrokenKeoard (CF1907 B)

題意

給定一個僅包含大小寫字母的字串 SS ，其中 ′B′'B' 字元為刪除目前字元前的第一個大寫字母， ′b′'b' 字元為刪除目前字元前的第一個小寫字母，求最後剩餘的字串。

思路：Stack

  • 用兩個 stack 分別存放大寫和小寫字母的 index，遇到 b 和 B 就 pop 掉最後一個 index，最後再依序輸出即可。
  • 原本為了方便輸出，用 deque 來實作，但是 python 的 deque 會遇到 TLE ，改用 C++ 的 deque 就可以過了。
  • 賽後將 deque 改成 list ，用下標依序輸出，結果還是 TLE ，不知道為什麼。
  • 另外一種方法是先將每個字元存放在一個 ansans 中，在遇到 b 和 B 時，將 ansans 中對應的字元設為空字串，最後再將 ansans 中的字元依序輸出即可。
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
using namespace std;

int main() {
    int T;
    cin >> T;

    for (int tc = 1; tc <= T; tc++) {
        string S;
        cin >> S;

        deque<int> lower, upper;

        for (int idx = 0; idx < S.size(); idx++) {
            char ch = S[idx];
            if (ch == 'b'){
                if (!lower.empty()) {
                    lower.pop_back();
                }
            } else if (ch == 'B') {
                if (!upper.empty()) {
                    upper.pop_back();
                }
            } else if (islower(ch)){
                lower.push_back(idx);
            } else {
                upper.push_back(idx);
            }
        }

        string ans = "";
        while (!lower.empty() || !upper.empty()) {
            if (!lower.empty() && !upper.empty()) {
                if (lower.front() < upper.front()) {
                    ans += S[lower.front()];
                    lower.pop_front();
                } else {
                    ans +=S[upper.front()];
                    upper.pop_front();
                }
            } else if (!lower.empty()) {
                while (!lower.empty()) {
                    ans += S[lower.front()];
                    lower.pop_front();
                }
            } else if (!upper.empty()) {
                while (!upper.empty()) {
                    ans += S[upper.front()];
                    upper.pop_front();
                }
            }
        }
        cout << ans << endl;
    }

    return 0;
}
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
T = int(input())

for tc in range(1, T+1):
    S = input()
    lower = []
    upper = []

    n = len(S)
    ans = list(S)

    for idx, ch in enumerate(S):
        if ch == 'b':
            ans[idx] = ""
            if lower:
                ans[lower.pop()] = ""
                
        elif ch == 'B':
            ans[idx] = ""
            if upper:
                ans[upper.pop()] = ""
        elif ch.islower():
            lower.append(idx)
        else:
            upper.append(idx)
    print("".join(ans))

C - Removal of Unattractive Pairs (CF1907 C)

題意

給定一個僅包含小寫字母的字串 SS ，每次操作可以選擇兩不同的相鄰字元刪除，問在不限制操作次數的情況下，剩下的字串的最短長度是多少？

思路：計數

  • 一開始以為可以用 stack 來模擬貪心思路，若遇到AAB 或 BAA 的情況就可以刪除，但是這樣會遇到一些狀況無法處理，例如 aaaabbbbcccc 的貪心結果是 22 ，但正確結果是 00。
  • 事實上，只要出現次數最多的字元的次數 mxmx 比剩餘其他字元的出現次數加總 N−mxN - mx 多，那麼就最多就只能刪除 N−mxN - mx 個字元，即剩下 mx−(N−mx)mx - (N - mx) 個字元。若 mxmx 比剩餘其他字元的出現次數加總少，那麼就可以依照 NN 的奇偶性，來刪到剩下 00 或 11 個字元。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from collections import Counter

T = int(input())

for tc in range(1, T+1):
    N = int(input())
    S = input()

    ans = 0
    cnt = Counter(S)
    mx = cnt.most_common(1)[0][1] # most common character's frequency
    
    if mx > N - mx:
        print(mx - (N - mx))
    else:
        print(N % 2)

D - Jumping Through Segments (CF1907 D)

題意

  • 有 nn 個區間，第 ii 個區間以 [li,rj][l_i, r_j] 表示。從位置 00 出發，每次最多移動距離 kk，現在需要找到一個最小的 kk，使得第 ii 次移動都能落在區間 ii 內。
  • 由於 kk 超過答案值後，一定符合條件，反之則一定不符合，故符合單調性 。
  • 可以用二分搜答案，對於每個答案 xx ，檢查是否可以跳到終點。檢查過程中維護 區間 [l,r][l, r] ，表示目前可以跳到的區間範圍。
  • 下一個區間的最左邊界是 max(x−k,l)max(x - k, l) ，最右邊界是 min(y+k,r)min(y + k, r) ，如果下一個區間合法，即nx≤nynx \leq ny ，則更新區間範圍，否則不合法。

類題

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
T = int(input())

def check(k):
    x, y = 0, 0 # 起始的區間範圍
    for l, r in LR:
        nx = max(x - k, l) # 下一個區間的最左邊界
        ny = min(y + k, r) # 下一個區間的最右邊界
        if nx <= ny: # 如果下一個區間合法，即左邊界<=右邊界，則更新區間範圍
            x, y = nx, ny
        else: 
            return False
    return True

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

    l, r = 0, 10**9
    while l <= r:
        mid = (l + r) // 2
        if check(mid):
            r = mid - 1
        else:
            l = mid + 1
    print(l)

E - Good Triples (CF1907 E)

題意

給定一個非負整數 nn ，令 digsum(n)digsum(n) 為 nn 的數位和。需要將 nn 拆成 33 個數 a,b,ca, b, c ，要求 n=a+b+cn = a + b + c ，同時還要求 digit(n)=digit(a)+digit(b)+digit(c)digit(n) = digit(a) + digit(b) + digit(c) 。求符合條件的 triples 有多少個，(a,b,c)(a, b, c) 與 (b,a,c)(b, a, c) 被視為是兩個不同的 triples。

思路：貪心 + 組合數學

  • 先用暴力法，分析測資的答案，以 N=11N=11 為例， 99 組答案分別為 (0,0,11)(0,0,11), (0,1,10)(0,1,10), (0,10,1)(0,10,1), (0,11,0)(0,11,0), (1,0,10)(1,0,10), (1,10,0)(1,10,0), (10,0,1)(10,0,1), (10,1,0)(10,1,0), (11,0,0)(11,0,0),。令 aia_i 表示 aa 的第 ii 位，可以由觀察發現在每個位數上， ai+bi+cia_i + b_i + c_i 皆不會產生進位。
  • 事實上，若 a+b+ca + b + c 發生進位的話，digsumdigsum 會變小，故要使條件成立，則 a+b+ca + b + c 不會發生進位，即 ai+bi+ci≤9a_i + b_i + c_i \leq 9 ，因此可以對 NN 的每個位數考慮。
  • 對於 NN 的每個位數 d=Nid = N_i ，計算 ai+bi+ci=da_i + b_i + c_i = d 的非負整數解個數，即 Hd3=Cdd+2==C2d+2{H^3_d} = C^{d+2}_d = = C^{d+2}_2 ，即為這個位數的貢獻，最後將所有位數的貢獻相乘即為答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
from math import comb

T = int(input())

for tc in range(1, T+1):
    N = int(input())

    ans = 1
    while N:
        x = N % 10
        ans *= comb(x+2, 2)
        N //= 10
    print(ans)

F - Shift and Reverse (CF1907 F)

題意

  • 給定一個由 nn 個整陣列成的Array aa，可以對這個陣列進行兩種操作：
    1. 將Array中最後一個元素移到首位，並將所有其他元素向右移動，得到 an,a1,a2,…,an−1a_n, a_1, a_2, \dots, a_{n-1}。
    2. 將整個Array反轉，得到 an,an−1,…,a1a_n, a_{n-1}, \dots, a_1。
  • 是否能用這兩種操作，對 aa 進行若干次操作，使得 aa 變成一個非遞減數列？若可以的話，輸出最少操作次數，否則輸出 −1-1。

思路：貪心

  • 把 aa 當成環首尾相連，因為兩種操作都不會更改相鄰位置的關係，因此，在環中必須存在長度至少為 nn 的連續遞增或遞減子陣列，否則不可行。
  • 由於先進行翻轉再進行向右移動，等同進行向左移動再進行翻轉，因此操作上也可以視為向左移動。
  • 若可以操作成功，則原陣列向右移動 k1k_1 次，或向左移動 k2k_2 次後為遞增或遞減陣列，對向左/向右移動，得遞增/遞減陣列，總共4種情況取最小值即可。
  • 將向左移動視為先翻轉再進行向右移動，如此就可以檢查向右移動後是否為遞增或遞減陣列，以及需要移動的次數。
  • 若右移後為遞減數列，則需要翻轉一次，操作次數要 +1+1 。若先翻轉再進行向右移動，則需要翻轉一次，操作次數也要 +1+1 。
  • 直接枚舉右移 kk 次，複雜度 O(N2)O(N^2)，會 TLE ，改為檢查有沒有連續 NN 個數字遞增或遞減，複雜度 O(N)O(N)。
  • 因為對只有一個數字的數列，無法判斷遞增或遞減，因此要特判 N=1N=1 的情況。
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
32
33
34
35
36
37
38
39
40
41
def rotate(A: list) -> int: # 檢查能否透過右移 k 次，使A變成遞增或遞減，的最小 k 值
    res = float('inf')
    cnt = 1
    for i in range(2*N-2, -1, -1): # 遞增的情況
        if A[i % N] <= A[(i+1) % N]:
            cnt += 1
        else:
            cnt = 1
        if cnt == N:
            res = min(res, N-i)
            break

    cnt = 1
    for i in range(2*N-2, -1, -1): # 遞減的情況
        if A[i % N] >= A[(i+1) % N]:
            cnt += 1
        else:
            cnt = 1
        if cnt == N:
            res = min(res, N-i+1) # 遞減，需要多一次反轉
            break
    return res

T = int(input())

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

    if N == 1: # 要特判N=1的情況
        print(0)
        continue

    res1 = rotate(A)
    res2 = rotate(A[::-1]) + 1 # 反轉算一次操作次數
    ans = min(res1, res2)
    
    if ans == float('inf'):
        print(-1)
    else:
        print(ans)

G - Lights (CF1907 G)

題意

<++>

思路：基環樹

<++>

1