A

程式碼

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

bool solve() {
    int n;
    cin >> n;
    int mx = -2e9, mi = 2e9;
    for (int i = 1;i <= n;i++) {
        int x;
        cin >> x;
        mi = min(x, mi);
        mx = max(x, mx);
    }
    if (mi < 0) cout << mi << '\n';
    else cout << mx << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

B

程式碼

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

bool solve() {
    int n;
    cin >> n;
    int pos[3];
    for (int i = 1;i <= n;i++) {
        int x;
        cin >> x;
        if (x == 1) pos[0] = i;
        else if (x == 2) pos[1] = i;
        else if (x == n) pos[2] = i;
    }
    if (pos[2] < pos[1] && pos[2] < pos[0]) cout << pos[2] << ' ' << min(pos[0], pos[1]) << '\n';
    else if (pos[2] > pos[1] && pos[2] > pos[0]) cout << pos[2] << ' ' << max(pos[0], pos[1]) << '\n';
    else cout << 1 << ' ' << 1 << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

C

題目

構造一個 $n \times m$ 的矩陣，矩陣中的元素是 $1 \sim n \times m$ 的數位，每個數位只能出現一次，要求相鄰元素差的絕對值不是個素數。

題解

知識點：構造。

方法一

按 $m$ 奇偶性分類：

$m$ 是偶數，可構造形如：

\[\begin{array}{l} &1 &2 &3 &4\\ &5 &6 &7 &8\\ &9 &10 &11 &12\\ &13 &14 &15 &16\\ \end{array} \]
可以保證左右的差的絕對值為 $1$ ，上下的差的絕對值是 $m$ 。
$m$ 是奇數，可構造形如：

\[\begin{array}{l} &1 &2 &3 &4 &5\\ &7 &8 &9 &10 &6\\ &13 &14 &15 &11 &12\\ &19 &20 &16 &17 &18\\ \end{array} \]
可以保證左右的差的絕對值為 $1$ ，上下的差的絕對值是 $m+1$ 。

時間複雜度 $O(nm)$

空間複雜度 $O(1)$

方法二

可構造形如：

\[\begin{array}{l} &1 &2 &3 &4\\ &9 &10 &11 &12\\ &17 &18 &19 &20\\ &5 &6 &7 &8\\ &13 &14 &15 &16\\ \end{array} \]

可以保證左右的差的絕對值為 $1$ ，上下的差的絕對值是 $2m$ 或 $\left( 2 \left\lfloor \dfrac{n-1}{2} \right\rfloor - 1 \right) m$ 。

特別地，當 $n = 4$ 且 $m$ 是素數時無法滿足，因此考慮 $n=4$ 時特判，構造形如：

\[\begin{array}{l} &1 &5 &9 &13 &17\\ &2 &6 &10 &14 &18\\ &3 &7 &11 &15 &19\\ &4 &8 &12 &16 &20\\ \end{array} \]

時間複雜度 $O(nm)$

空間複雜度 $O(1)$

程式碼

方法一

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

bool solve() {
    int n, m;
    cin >> n >> m;
    if (m & 1) {
        for (int i = 1;i <= n;i++)
            for (int j = 1;j <= m;j++)
                cout << (i - 1) * m + (j + i - 2) % m + 1 << " \n"[j == m];
    }
    else {
        for (int i = 1;i <= n;i++)
            for (int j = 1;j <= m;j++)
                cout << (i - 1) * m + j << " \n"[j == m];
    }
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

方法二

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

bool solve() {
    int n, m;
    cin >> n >> m;
    if (n == 4) {
        for (int i = 1;i <= n;i++)
            for (int j = 1;j <= m;j++)
                cout << i + (j - 1) * n << " \n"[j == m];
    }
    else {
        for (int i = 1;i <= n;i++) {
            int ii = i <= (n + 1) / 2 ? 2 * i - 1 : 2 * (i - (n + 1) / 2);
            for (int j = 1;j <= m;j++) {
                cout << (ii - 1) * m + j << " \n"[j == m];
            }
        }
    }
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

D

題目

給定一個只包含 ( 和 ) 兩種字元的字串 $s$ 。

現在要求從 $s_1$ 出發，最終到達 $s_n$ ，每次可以左右移動一個位置，並依次寫下到達的位置的字元。

問通過 $s$ ，最後能否寫下一個合法括號序列。

題解

知識點：STL，貪心。

首先若 $n$ 是奇數無解。

這道題本質就是判斷：

對於最後一個 (( ，其右方是否存在一個 )) 。
對於第一個 )) ，其左方是否存在一個 (( 。

特別地，對於 $s_1$ 為 ) 或 $s_n$ 為 ( ，也要認為是 )) 或 (( 。

容易證明，若不滿足兩個條件的任意一個，那麼一定無解；滿足這兩個條件，一定能構造出一個解。

到這裡，其實用兩個 set 分別維護 (( 和 )) 的位置，可以直接寫了：

若 (( 和 )) 都不存在，那麼有解。
若情況1或2滿足任意一個，那麼無解。
否則有解。

不過，接下來官方題解的做法更加簡潔。

考慮用 set 記錄所有位置 $i$ ，滿足：

若 $i$ 是奇數，滿足 $s_i$ 是 ) 。
若 $i$ 是偶數，滿足 $s_i$ 是 ( 。

可以看到，第一個滿足情況1的位置，只可能在 $s_1$ 或第一個 )) 的位置；最後一個滿足情況2的位置，只可能在 $s_n$ 或最後一個 (( 的位置。

因此，我們可以通過類似的判斷：

若沒有位置滿足，那麼有解。
若第一個記錄的位置是奇數或最後一個記錄的位置是偶數，那麼無解。
否則有解。

時間複雜度 $O((n+q) \log n)$

空間複雜度 $O(n)$

程式碼

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, q;
    cin >> n >> q;
    set<int> st;
    for (int i = 1;i <= n;i++) {
        char ch;
        cin >> ch;
        if (ch == '(' && !(i & 1) || ch == ')' && (i & 1)) st.insert(i);
    }

    while (q--) {
        int x;
        cin >> x;
        if (auto it = st.find(x);it != st.end()) st.erase(it);
        else st.insert(x);
        if (n & 1) {
            cout << "NO" << '\n';
            continue;
        }
        if (!st.size()) cout << "YES" << '\n';
        else if ((*st.begin() & 1) || !(*prev(st.end()) & 1)) cout << "NO" << '\n';
        else cout << "YES" << '\n';
    }
    return 0;
}

E

題目

給定 $n,m,k$ ，再給一個長度為 $n$ 的整數陣列 $a$ 滿足 $a_i \in [1,k]$ 。

求有多少不同的長度為 $m$ 的整數陣列 $b$ ，滿足 $b_i \in [1,k]$ 且 $a$ 是 $b$ 的子序列。

不同的定義：兩個陣列任意一個位置數位不同，可看做不同。

題解

知識點：線性dp，排列組合。

先考慮樸素的dp。

設 $f_{i,j}$ 表示考慮了 $b$ 前 $i$ 個數位，且作為 $b$ 的子序列的 $a$ 的字首的最長長度為 $j$ ，有轉移方程：

\[f_{i,j} = \begin{cases} f_{i-1,j-1} + (k-1)f_{i-1,j} &,j < n\\ f_{i-1,j-1} + kf_{i-1,j} &,j = n\\ \end{cases} \]

顯然dp是會超時的，但是我們從中可以發現，整個過程和 $a$ 一點關係都沒。

因此，我們就假設 $a_i = 1$ ，顯然求不滿足的比較容易。 $b$ 共有 $k^m$ 種，不滿足的情況為 $<n$ 個 $1$ 且其他都不為 $1$ ，因此不滿足的情況有 $\displaystyle $ 種，所以最終答案為：

\[ k^m -\sum_{i=0}^{n-1} \binom{m}{i}(k-1)^{m-i} \]

其中組合數是 $m$ 是 $10^9$ 的，因此不可以用公式法預處理階乘及其逆元，考慮用乘法公式遞推：

\[\binom{m}{i} = \frac{m-i+1}{i} \binom{m}{i-1} \]

時間複雜度 $O(n \log m)$

空間複雜度 $O(n)$

程式碼

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int P = 1e9 + 7;
namespace Number_Theory {
    int qpow(int a, ll k) {
        int ans = 1;
        while (k) {
            if (k & 1) ans = 1LL * ans * a % P;
            k >>= 1;
            a = 1LL * a * a % P;
        }
        return ans;
    }
}
namespace CNM {
    using namespace Number_Theory;
    const int N = 2e5 + 7;
    int n, m, cn[N];
    void init(int _n, int _m) {
        n = _n;
        m = _m;
        cn[0] = 1;
        for (int i = 1;i <= m;i++) cn[i] = 1LL * (n - i + 1) * qpow(i, P - 2) % P * cn[i - 1] % P;
    }
    int Cn(int m) {
        if (n == m && m == -1) return 1;
        if (n < m || m < 0) return 0;
        return cn[m];
    }
}
using Number_Theory::qpow;
using CNM::Cn;

bool solve() {
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1, x;i <= n;i++) cin >> x;
    CNM::init(m, n);
    int ans = qpow(k, m);
    for (int i = 0;i <= n - 1;i++) (ans -= 1LL * Cn(i) * qpow(k - 1, m - i) % P - P) %= P;
    cout << ans << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

Codeforces Round #877 (Div. 2) A-E

A

程式碼

B

程式碼

C

題目

題解

方法一

方法二

程式碼

方法一

方法二

D

題目

題解

程式碼

E

題目

題解

程式碼