比賽連結

A

題解

知識點：列舉。

只要一個Q後面有一個A對應即可，從後往前遍歷，記錄A的數量，遇到Q則數量減一，如果某次Q計數為0則NO。

時間複雜度 \(O(n)\)

空間複雜度 \(O(1)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

bool solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = "?" + s;
    int cnt = 0;
    for (int i = n;i >= 1;i--) {
        if (s[i] == 'Q') {
            if (cnt == 0) return false;
            cnt--;
        }
        else cnt++;
    }
    cout << "YES" << '\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 << "NO" << '\n';
    }
    return 0;
}

B

題解

知識點：構造。

可以證明 \(\lfloor \frac{n}{2} \rfloor\) 是最優答案。交錯構造， \(i+\lfloor \frac{n}{2} \rfloor\) 和 \(i\) ，注意 \(i\) 從 \(1\) 到 \(\lfloor \frac{n}{2} \rfloor\) ，在最後如果 \(n\) 是奇數則補一個 \(n\) 。

時間複雜度 \(O(n)\)

空間複雜度 \(O(1)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

bool solve() {
    int n;
    cin >> n;
    for (int i = 1;i <= n / 2;i++) {
        cout << i + n / 2 << ' ' << i << ' ';
    }
    if (n & 1) cout << n << ' ';
    cout << '\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

題解

知識點：構造。

可以兩兩構造。找到一對非 \(0\) 數 \(a[i],a[j]\) ，當 \(a[i] = a[j]\)，如果 \(i,j\) 奇偶性相同則 \([i,i],[i+1,j]\) ，否則分段 \([i,j]\) ；當 \(a[i] \neq a[j]\) ，如果 \(i,j\) 奇偶性相同則 \([i,j]\) ，否則 \([i,i],[i+1,j]\) 。

注意兩對之間以及首尾可能會存在空隙，最後要把上面答案遍歷一遍，填補空隙。

時間複雜度 \(O(n)\)

空間複雜度 \(O(n)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int a[200007];
bool solve() {
    int n;
    cin >> n;
    vector<int> pos;
    for (int i = 1;i <= n;i++) cin >> a[i];
    for (int i = 1;i <= n;i++) {
        if (a[i]) pos.push_back(i);
    }
    if (pos.size() & 1) return false;
    if (!pos.size()) {
        cout << 1 << '\n';
        cout << 1 << ' ' << n << '\n';
        return true;
    }
    vector<pair<int, int>> v;
    for (int i = 0;i < pos.size();i += 2) {
        if (a[pos[i]] == a[pos[i + 1]]) {
            if ((pos[i] & 1) == (pos[i + 1] & 1)) {
                v.push_back({ pos[i], pos[i] });
                v.push_back({ pos[i] + 1,pos[i + 1] });
            }
            else v.push_back({ pos[i],pos[i + 1] });
        }
        else {
            if ((pos[i] & 1) != (pos[i + 1] & 1)) {
                v.push_back({ pos[i], pos[i] });
                v.push_back({ pos[i] + 1,pos[i + 1] });
            }
            else v.push_back({ pos[i],pos[i + 1] });
        }
    }
    vector<pair<int, int>> ans;
    int prer = 0;
    for (auto [i, j] : v) {
        if (i != prer + 1) ans.push_back({ prer + 1, i - 1 });
        ans.push_back({ i,j });
        prer = j;
    }
    if (ans.back().second != n) ans.push_back({ ans.back().second + 1,n });
    cout << ans.size() << '\n';
    for (auto [i, j] : ans) {
        cout << i << ' ' << j << '\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;
}

D

題解

知識點：數論，貪心。

記錄每個數位出現的次數，嘗試從小到大合成出 \(x\) 。從 \(1\) 開始往後遍歷，每次將 \(i\) 合成 \(i+1\) ，顯然 \(i+1\) 個 \(i\) 將產生 \(1\) 個 \(i+1\) 。如果出現非 \(x\) 的數 \(i\) 不能全部使用 ，那麼整個式子就無法被 \(x!\) 整除。

時間複雜度 \(O(n)\)

空間複雜度 \(O(1)\)

程式碼

#include <bits/stdc++.h>

using namespace std;

int cnt[500007];
int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, x;
    cin >> n >> x;
    for (int i = 1;i <= n;i++) {
        int tmp;
        cin >> tmp;
        cnt[tmp]++;
    }
    for (int i = 1;i < x;i++) {
        if (cnt[i] % (i + 1)) {
            cout << "NO" << '\n';
            return 0;
        }
        cnt[i + 1] += cnt[i] / (i + 1);
    }
    cout << "YES" << '\n';
    return 0;
}

E

題解

知識點：概率dp。

設 \(f[i]\) 代表將 \(i\) 個還沒排好的 \(1\) （如 1100101 有 \(2\) 個 \(1\) 沒排好）排好的期望步數。

對於 \(f[i]\) ，下一步排好一個 \(1\) （即到達 \(i-1\) 狀態）的概率是 \(\dfrac{i^2}{C_n^2}\) ，下一步啥都沒變的概率就是 \(1-\dfrac{i^2}{C_n^2}\)，於是有：

即一步到達 \(i-1\) 後再排完的期望乘這步的概率加一步啥也沒幹的期望乘這步的概率就是 \(f[i]\) 。

於是可以遞推，\(f[0] = 0\) ，求的是 \(f[cnt1]\) ，\(cnt1\) 是初始沒排好 \(1\) 的個數。

這裡其實有個概率論的定理：如果一個事件的結果A發生的概率是 \(P\) ，則一直做這件事直到第一次發生結果A的期望 \(X\) 是 \(\dfrac{1}{P}\) 。

證明：

\[\begin{aligned} X &= 1\cdot P+(X+1)\cdot (1-P)\\ P\cdot X &= 1\\ X &= \frac{1}{P} \end{aligned} \]

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

空間複雜度 \(O(n)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int mod = 998244353;

int a[200007];
ll qpow(ll a, ll k) {
    ll ans = 1;
    while (k) {
        if (k & 1) ans = (ans * a) % mod;
        k >>= 1;
        a = (a * a) % mod;
    }
    return ans;
}

bool solve() {
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    int cnt0 = count(a + 1, a + n + 1, 0);
    int cnt1 = count(a + 1, a + cnt0 + 1, 1);
    int c2 = 1LL * n * (n - 1) / 2 % mod;
    int ans = 0;
    for (int i = 1;i <= cnt1;i++) {
        ans = (ans + 1LL * c2 * qpow(1LL * i * i % mod, mod - 2) % mod) % mod;
    }
    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;
}