比赛链接

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;

}