Codeforces Round ＃804 (Div. 2)（5/5）

Problem - A - Codeforces

构造+猜想

AC代码：

#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
using namespace std;
using LL = long long;

void Solve() {
    int n;
    cin >> n;
    if (n & 1) {
        cout << "-1\n";
    }
    else {
        cout << "0 0 " << n / 2 << '\n';
    }
}

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

    int T;
    cin >> T;
    rep(i, 0, T) {
        Solve();
    }

    return 0;
}

Problem - B - Codeforces

构造+找规律

AC代码：

#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
using namespace std;
using LL = long long;

void Solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int> (m));
    rep (i, 0, n) {
        rep (j, 0, m) {
            if ((i % 4 == 0 && (j % 4 == 0 || j % 4 == 3)) || ((i % 4 == 1 || i % 4 == 2) && (j % 4 == 1 || j % 4 == 2)) || (i % 4 == 3 && (j % 4 == 0 || j % 4 == 3))) {
                cout << "1 ";
            }
            else {
                cout << "0 ";
            }
        }
        cout << '\n';
    }
}

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

    int T;
    cin >> T;
    rep(i, 0, T) {
        Solve();
    }

    return 0;
}

Problem - C - Codeforces

mex数学归纳

AC代码：

#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
using namespace std;
using LL = long long;
using i64 = long long;

const int P = 1e9 + 7;
// assume -P <= x < 2P
int norm(int x) {
    if (x < 0) {
        x += P;
    }
    if (x >= P) {
        x -= P;
    }
    return x;
}
template<class T>
T power(T a, i64 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)) {}
    Z(i64 x) : x(norm(x % P)) {}
    int val() const {
        return x;
    }
    Z operator-() const {
        return Z(norm(P - x));
    }
    Z inv() const {
        assert(x != 0);
        return power(*this, P - 2);
    }
    Z &operator*=(const Z &rhs) {
        x = i64(x) * rhs.x % P;
        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;
    }
    friend std::istream &operator>>(std::istream &is, Z &a) {
        i64 v;
        is >> v;
        a = Z(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Z &a) {
        return os << a.val();
    }
};

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

    int T;
    cin >> T;
    while (T--) {
    int n;
    cin >> n;
    vector<int> a(n + 1), p(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i]++;
        p[a[i]] = i;
    }
    int l = p[1], r = p[1];
    Z ans = 1;
    for (int i = 2; i <= n; i++) {
        if (p[i] < l) {
            l = p[i];
        }
        else if (p[i] > r) {
            r = p[i];
        }
        else {
            ans *= (r - l - i + 2);
        }
    }
    cout << ans << '\n';
    }

    return 0;
}

Problem - D - Codeforces

dp

AC代码：

#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
using namespace std;
using LL = long long;

void Solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1), dp(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        vector<int> cnt(n + 1);
        dp[i] = -0x3f3f3f3f;
        int maxx = 0;
        for (int j = i - 1; j >= 0; j--) {//j+1.....i-1(i-1-j-1+1)->i-j-1
            if ((i - j - 1) % 2 == 0 && maxx <= (i - j - 1) / 2 && (j == 0 || a[i] == a[j])) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
            cnt[a[j]]++;
            maxx = max(maxx, cnt[a[j]]);
        }
    }
    int ans = 0;
    int maxx = 0;
    vector<int> cnt(n + 1);
    for (int i = n; i >= 0; i--) {
        if ((n - i) % 2 == 0 && maxx <= (n - i) / 2) {
            ans = max(ans, dp[i]);
        }
        cnt[a[i]]++;
        maxx = max(maxx, cnt[a[i]]);
    }
    cout << ans << '\n';
}

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

    int T;
    cin >> T;
    rep (i, 0, T) {
        Solve();
    }

    return 0;
}

Problem - E - Codeforces

dp+two pointers

AC代码：

#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
using namespace std;
using LL = long long;

void Solve() {
    int n, m;
    cin >> n >> m;
    vector<int> dp(m + 1);
    vector<int> cnt(m + 1);
    vector<bool> vis(m + 1);
    for (int i = 1; i <= m; i++) {
        dp[i] = i;
    }
    int l = 1e9 + 7, r = -1e9;
    rep(i, 0, n) {
        int x;
        cin >> x;
        cnt[x] = 1;
        vis[x] = true;
        l = min(x, l);
        r = max(x, r);
    }
    int ans = r - l;
    for (int i = sqrt(m) + 1; i > 0; i--) {
        for (int j = i; j <= m; j += i) {
            if (vis[j]) {
                cnt[dp[j]]--;
            }
            if (dp[j / i] >= i) {
                dp[j] = min(dp[j], dp[j / i]);
            }
            if (vis[j]) {
                cnt[dp[j]]++;
            }
        }
        while (cnt[r] == 0) {
            r--;
        }
        ans = min(ans, r - min(l, i));
    }
    cout << ans << '\n';
}

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

    int T;
    cin >> T;
    rep (i, 0, T) {
        Solve();
    }

    return 0;
}