比賽連結

A

題目

知識點：模擬。

確定開頭字母，然後迴圈比較即可。

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

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

題解

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

using namespace std;

bool solve() {
    string s;
    cin >> s;
    string t = "Yes";
    int pos = -1;
    if (s[0] == t[0]) pos = 0;
    else if (s[0] == t[1]) pos = 1;
    else if (s[0] == t[2]) pos = 2;
    else return false;
    for (auto ch : s) {
        if (ch != t[pos]) return false;
        pos = (pos + 1) % 3;
    }
    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

題目

知識點：列舉。

找到總和等於 \(sum + s\) 的排列，其中 \(sum\) 是原來序列的和。這個排列的最大數位不能小於原來序列裡的最大數位，否則不合法。

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

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

題解

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

using namespace std;

bool solve() {
    int m, s;
    cin >> m >> s;
    int mx = 0, sum = 0;
    for (int i = 1;i <= m;i++) {
        int x;
        cin >> x;
        sum += x;
        mx = max(x, mx);
    }
    int ans = -1;
    for (int i = 1;i <= 70;i++) {
        if (i * (i + 1) / 2 == sum + s) {
            ans = i;
            break;
        }
    }
    if (ans >= mx) cout << "YES" << '\n';
    else cout << "NO" << '\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

題目

知識點：貪心。

分類討論：

1. \(a=b\) ，不用操作。
2. \(|a-b|\geq x\) ，一次操作。
3. 先將 \(a\) 變 \(l\) （或 \(r\) ），再將 \(l\) （或 \(r\) ）變成 \(x\) ，兩次操作（如果可以的話）。
4. 先將 \(a\) 變 \(l\) （或 \(r\) ），再將 \(l\) （或 \(r\) ）變成 \(r\) （或 \(l\) ），再將 \(r\) （或 \(l\) ）變成 \(x\) ，三次操作（如果可以的話）。
5. 無解，因為 \(a\) 變換到 \(l\) 或 \(r\) 將會擁有與 \(b\) 的最大距離，再不行就無解。

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

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

題解

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

using namespace std;

bool solve() {
    int l, r, x;
    int a, b;
    cin >> l >> r >> x;
    cin >> a >> b;
    if (a == b) cout << 0 << '\n';
    else if (abs(a - b) >= x) cout << 1 << '\n';
    else if (a - l >= x && b - l >= x || r - a >= x && r - b >= x) cout << 2 << '\n';
    else if (a - l >= x && r - l >= x && r - b >= x || r - a >= x && r - l >= x && b - l >= x) cout << 3 << '\n';
    else cout << -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;
}

D

題目

知識點：數論，貪心。

顯然儘可能配對 \(2\) 和 \(5\) 因子，隨後儘可能乘 \(10\) 。

先找到 \(n\) 中已有的 \(2\) ，\(5\)因子數量，然後先用 \(mul\) 配平因子數（這樣操作的得到的 \(mul\) 最小）。

之後，給 \(mul\) 乘 \(10\) 直到再次操作會超過 \(m\) 。

最後把 \(mul\) 加倍到最大值 \(m\) 內最大值。

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

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

題解

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

using namespace std;

bool solve() {
    int n, m;
    cin >> n >> m;

    int t = n;
    int c2 = 0, c5 = 0;
    while (t % 2 == 0) t /= 2, c2++;
    while (t % 5 == 0) t /= 5, c5++;

    int mul = 1;
    while (c2 < c5 && mul * 2LL <= m) mul *= 2, c2++;
    while (c2 > c5 && mul * 5LL <= m) mul *= 5, c5++;
    while (mul * 10LL <= m) mul *= 10;

    cout << 1LL * n * (m / mul) * mul << '\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;
}

E

題目

顯然貪心策略是從小到大吸收，考慮道具使用順序。

方法一

知識點：列舉，dfs。

只有三個道具，直接搜尋所有使用順序即可，每次先把能吸收的吸收了。

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

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

方法二

知識點：線性dp。

設 \(dp[i][j][k]\) 表示吸收了前 \(i\) 個人， \(2\) 倍道具剩 \(j\) 個， \(3\) 倍道具剩 \(k\) 個的最大能量。

轉移時，先從吸收了 \(i-1\) 個人的狀態轉移到吸收了 \(i\) 個人的狀態，再考慮吸收了 \(i\) 個人的狀態後使用道具的情況。

使用道具時的轉移不需要考慮轉移順序。某個狀態被其他的狀態更新後，再使用道具的狀態一定會被更新他的狀態包括，因此不需要考慮更新順序。

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

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

題解

方法一

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

using namespace std;

int n;
int a[200007];

int dfs(int pos, int cntg, int cntb, ll h) {
    while (pos <= n && h > a[pos]) h += a[pos++] / 2;
    int mx = pos - 1;
    if (cntg >= 1) mx = max(mx, dfs(pos, cntg - 1, cntb, h * 2));
    if (cntb >= 1) mx = max(mx, dfs(pos, cntg, cntb - 1, h * 3));
    return mx;
}

bool solve() {
    int h;
    cin >> n >> h;
    for (int i = 1;i <= n;i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    cout << dfs(1, 2, 1, h) << '\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;
}

方法二

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

using namespace std;

int a[200007];
ll f[200007][3][2];
bool solve() {
    int n, h;
    cin >> n >> h;
    for (int i = 1;i <= n;i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1;i <= n;i++)
        for (int j = 0;j <= 2;j++)
            for (int k = 0;k <= 1;k++)
                f[i][j][k] = 0;
    f[0][2][1] = h;
    f[0][1][1] = h * 2;
    f[0][2][0] = h * 3;
    f[0][0][1] = h * 4;
    f[0][1][0] = h * 6;
    f[0][0][0] = h * 12;
    for (int i = 1;i <= n;i++) {
        for (int j = 0;j <= 2;j++)
            for (int k = 0;k <= 1;k++)
                if (f[i - 1][j][k] > a[i]) f[i][j][k] = max(f[i][j][k], f[i - 1][j][k] + a[i] / 2);
        for (int j = 0;j <= 2;j++) {
            for (int k = 0;k <= 1;k++) {
                if (j >= 1) f[i][j - 1][k] = max(f[i][j - 1][k], f[i][j][k] * 2);
                if (k >= 1) f[i][j][k - 1] = max(f[i][j][k - 1], f[i][j][k] * 3);
                if (j >= 2) f[i][j - 2][k] = max(f[i][j - 2][k], f[i][j][k] * 4);
                if (j >= 1 && k >= 1) f[i][j - 1][k - 1] = max(f[i][j - 1][k - 1], f[i][j][k] * 6);
                if (j >= 2 && k >= 1) f[i][j - 2][k - 1] = max(f[i][j - 2][k - 1], f[i][j][k] * 12);
            }
        }
    }
    for (int i = n;i >= 0;i--)
        for (int j = 0;j <= 2;j++)
            for (int k = 0;k <= 1;k++)
                if (f[i][j][k]) {
                    cout << i << '\n';
                    return true;
                }
    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;
}

F

題目

知識點：貪心，列舉。

顯然答案不會大於等於 \(p\) ，即只需要考慮 \(a_n\) 關於缺失數位的大小即可，用 set 存出現過的數。

如果沒有小於 \(a_n\) 的缺失數位，就不需要進位，設最大的缺失數位為 \(mx\) （不存在則設為 \(a_n\) ），答案為 \(mx - a_n\) 。

如果有小於 \(a_n\) 的缺失數位，則必須進位。進位後，一定會出現 \(0\) 以及模擬進位後變化的最高位的數位，需要納入 set 。隨後找到小於 \(a_n\) 的最大缺失數位 \(mx\) （不存在則設為 \(0\) ），答案為 \(mx + p-a_n\) 。

因為給出的數位最多隻有 \(100\) 個，所以每次找數位的次數不會超過 \(100\) 次。

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

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

題解

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

using namespace std;

int a[107];
bool solve() {
    int n, p;
    cin >> n >> p;
    for (int i = 1;i <= n;i++) cin >> a[i];
    set<int> st;
    for (int i = 1;i <= n;i++) st.insert(a[i]);
    bool cf = 0;
    for (int i = a[n];i >= 0 && !cf;i--) cf |= !st.count(i);
    if (cf) {
        st.insert(0);
        for (int i = n - 1;i >= 0;i--) {
            if (a[i] + 1 < p) {
                st.insert(a[i] + 1);
                break;
            }
        }
        int mx = a[n] - 1;
        while (mx > 0 && st.count(mx)) mx--;
        cout << mx + p - a[n] << '\n';
    }
    else {
        int mx = p - 1;
        while (mx > a[n] && st.count(mx)) mx--;
        cout << mx - a[n] << '\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;
}

G

題目

知識點：構造，二分，貪心。

顯然，\(a_{2i} = b_i\) 最優，接下來考慮 \(a_{2i-1}\) 。

首先，我們希望出現在前面的數位儘可能小，但因為留下的數位是較大的，不一定能讓後面數位有解。於是，若要確定這個數位，那麼就必須每次都需要檢查一遍後面的數位是否還有解，這樣很難以較小複雜度實現。

但是，我們知道出現在後面的數位要儘可能大，我們可以從後往前確定數位，這樣就儘可能保留了小的數位，使得前面的數有解。並且，保留的數位不會比這種方案更小，因此如果前面的數位還是無解，那就真的無解。

因此，我們先把 \(1\) 到 \(n\) 存在 set 中，把出現過的數位刪除。如果刪除的數位已經刪過，那麼不可能是個排列，所以無解。然後，從後往前，確定未出現的數中小於 \(b_i\) 的最大數當作 \(a_{2i-1}\) ，如果沒有則無解。

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

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

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

using namespace std;

int a[200007], b[100007];
bool solve() {
    int n;
    cin >> n;
    for (int i = 1;i <= n / 2;i++) cin >> b[i], a[i * 2] = b[i];
    set<int> st;
    for (int i = 1;i <= n;i++) st.insert(i);
    for (int i = 1;i <= n / 2;i++) {
        if (!st.count(b[i])) return false;
        st.erase(b[i]);
    }
    for (int i = n / 2;i >= 1;i--) {
        auto pos = st.lower_bound(b[i]);
        if (pos == st.begin()) return false;
        a[i * 2 - 1] = *prev(pos);
        st.erase(prev(pos));
    }
    for (int i = 1;i <= n;i++) cout << a[i] << ' ';
    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;
}