Educational Codeforces Round 141 (Rated for Div. 2)【A - E】

E 题这种把两个数取上整的大小关系转化为区间覆盖问题的方法真是巧妙啊……

比赛链接：https://codeforces.com/contest/1783

A. Make it Beautiful

题解

排降序，然后把最小的一个数放前面。

代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        sort(a.begin(), a.end(), greater());

        if (a[0] == a[n - 1]) {
            cout << "NO" << "\n";
        } else {
            rotate(a.begin(), prev(a.end()), a.end());
            cout << "YES" << "\n";
            for (int i = 0; i < n; i++) {
                cout << a[i] << " \n"[i == n - 1];
            }
        }
    }

    return 0;
}

B. Matrix of Differences

题解

构造 $n^2, 1, n^2 - 1, 2, n^2 - 2, 3\dots$ ，蛇形填入矩阵即可。

代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector a(n, vector<int>(n));
        int l = 1, r = n * n, cnt = 0;
        for (int i = 0; i < n; i++) {
            if (i & 1) {
                for (int j = n - 1; j >= 0; j--) {
                    a[i][j] = cnt & 1 ? l++ : r--;
                    cnt++;
                }
            } else {
                for (int j = 0; j < n; j++) {
                    a[i][j] = cnt & 1 ? l++ : r--;
                    cnt++;
                }
            }
        }
    
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << a[i][j] << " \n"[j == n - 1];
            }
        }
    }

    return 0;
}

C. Yet Another Tournament

题解

枚举赢的次数，如果赢了 $i$ 次，只需考虑是否能赢第 $i + 1$ 个人（这个人已经赢了 $i$ 次）：

• 如果能赢，那么第 $1 \sim i + 1$ 个人都没我赢得多，答案为 $n - i$
• 如果不能赢，那么只有第 $1 \sim i$ 个人没我赢得多，答案为 $n - i + 1$

代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n, m;
        cin >> n >> m;

        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        vector<int> b(a);
        sort(b.begin(), b.end());

        vector<int> pre(n + 1);
        for (int i = 0; i < n; i++) {
            pre[i + 1] += pre[i] + b[i];
        }

        int ans = n + 1;
        for (int i = 1; i <= n; i++) {
            if (m >= pre[i]) {
                ans = min(ans, n - i + 1);
            }
            if (i < n and m >= pre[i] + max(0, a[i] - b[i - 1])) {
                ans = min(ans, n - i);
            }
        }
        cout << ans << "\n";
    }

    return 0;
}

D. Different Arrays

题解

设 $dp[i][j]$ 为 $a_i$ 值为 $j$ 时有多少种排列，答案即 $\sum \limits _{-\infty} ^{+\infty} dp[n-1][j]$ 。

当 $a_i = 0$ 时，对 $a_{i + 1}$ 的值只有一种贡献；因为值可能为负数，所以需要加上一个偏移量。

代码

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

constexpr int MOD = 998244353;
constexpr int M = 300 * 300;

int norm(int x) { if (x < 0) { x += MOD; } if (x >= MOD) { x -= MOD; } return x; }
template<class T> T binpow(T a, int b) { T res = 1; for (; b; b /= 2, a *= a) { if (b % 2) { res *= a; } } return res; }

struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    int val() const { return x; }
    Z operator-() const { return Z(norm(MOD - x)); }
    Z inv() const { assert(x != 0); return binpow(*this, MOD - 2); }
    Z &operator*=(const Z &rhs) { x = 1LL * x * rhs.x % MOD; return *this; }
    Z &operator+=(const Z &rhs) { x = norm(x + rhs.x); return *this; }
    Z &operator-=(const Z &rhs) { x = norm(x - rhs.x); return *this; }
    Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
    friend Z operator*(const Z &lhs, const Z &rhs) { Z res = lhs; res *= rhs; return res; }
    friend Z operator+(const Z &lhs, const Z &rhs) { Z res = lhs; res += rhs; return res; }
    friend Z operator-(const Z &lhs, const Z &rhs) { Z res = lhs; res -= rhs; return res; }
    friend Z operator/(const Z &lhs, const Z &rhs) { Z res = lhs; res /= rhs; return res; }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector dp(n, vector<Z>(2 * M + 1));
    dp[1][a[1] + M] = 1;

    for (int i = 1; i + 1 < n; i++) {
        for (int j = 0; j <= 2 * M; j++) {
            if (dp[i][j].val() == 0) {
                continue;
            }
            dp[i + 1][a[i + 1] + (j - M) + M] += dp[i][j];
            if (j - M != 0) {
                dp[i + 1][a[i + 1] - (j - M) + M] += dp[i][j];
            }
        }
    }

    cout << accumulate(dp[n - 1].begin(), dp[n - 1].end(), Z(0)).val() << "\n";

    return 0;
}

E. Game of the Year

题解

第一个人能杀死所有怪兽即： $\forall\ i \in [1, n], \lceil \frac{a_i}{k} \rceil \le \lceil \frac{b_i}{k} \rceil$ 。

• 当 $a_i \le b_i$ 时，上式显然成立

• 当 $a_i \gt b_i$ 时，上式成立即 $[b_i, a_i)$ 内不能有 $k$ 的倍数

所以，一个 $k$ 是否可行即判断它的所有倍数是否被某一个区间覆盖。

利用差分计算所有区间覆盖的数，之后枚举 $k$ 的倍数即可。

代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> a(n), b(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        for (int i = 0; i < n; i++) {
            cin >> b[i];;
        }

        vector<int> d(n + 1);
        for (int i = 0; i < n; i++) {
            if (a[i] > b[i]) {
                ++d[b[i]];
                --d[a[i]];
            }
        }

        for (int i = 1; i <= n; i++) {
            d[i] += d[i - 1];
        }

        vector<int> ans;
        for (int k = 1; k <= n; k++) {
            int ok = 1;
            for (int i = k; i <= n; i += k) {
                if (d[i]) {
                    ok = 0;
                    break;
                }
            }
            if (ok) ans.push_back(k);
        }

        cout << ans.size() << "\n";
        for (auto x : ans) {
            cout << x << " \n"[x == ans.back()];
        }
    }

    return 0;
}