2024 CCPC 网络预选赛 热身赛

Problems	AC
A. 2022 百度之星初赛第三场 字符计数	○
B. 2024 河北省赛 - J - Iris’ Food	○
C. 2024 东北省赛 - K - Tasks	⊕
D. 2024 河北省赛 - F - 3 Split

A

联通块计数

原题：2022 百度之星初赛第三场 字符计数

#include <bits/stdc++.h>
using i64 = long long;
#define int i64
#define pb push_back
#define ep emplace
#define eb emplace_back
using std::max, std::min, std::swap;
using std::cin, std::cout, std::string, std::vector;
int read(int x = 0, int f = 0, char ch = getchar()) {
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}

const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};

void solve() {
    int n = read(), m = read();

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

    vector<vector<int>> vis(n, vector<int>(m));
    std::array<int, 3> ans;

    auto bfs = [&](int sx, int sy) {
        int cnt = 0;

        std::queue<std::pair<int, int>> q;
        vis[sx][sy] = 1, q.push({sx, sy});
        while (!q.empty()) {
            cnt++;
            auto [x, y] = q.front();
            q.pop();

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx < 0 or nx >= n or ny < 0 or ny >= m) continue;
                if (a[nx][ny] == '.' or vis[nx][ny]) continue;

                q.push({nx, ny}), vis[nx][ny] = 1;
            }
        }

        ans[2] += cnt / 13, cnt %= 13;
        ans[1] += cnt / 8, cnt %= 8;
        ans[0] += cnt / 3;
    };

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (vis[i][j]) continue;
            if (a[i][j] == '.') continue;
            bfs(i, j);
        }
    }

    for (auto x : ans) cout << x << ' ';
}

signed main() {
    // sfor (int T = read(); T--; solve());
    solve();
    return 0;
}

B

原题 2024 河北省赛 - J - Iris’ Food

赛时糖丸了，写矩阵快速幂去了，赛后发现直接 $\frac{10^x - 1}{9}$ 就行了

#include <bits/stdc++.h>
using i64 = long long;
#define int i64
#define pb push_back
#define ep emplace
#define eb emplace_back
using std::max, std::min, std::swap;
using std::cin, std::cout, std::string, std::vector;
int read(int x = 0, int f = 0, char ch = getchar()) {
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}

template <class T>
constexpr T power(T a, i64 b) { T res {1}; for (; b; b /= 2, a *= a) if (b % 2) res *= a; return res; }
constexpr i64 mul(i64 a, i64 b, i64 p) { i64 res = a * b - (i64)(1.L * a * b / p) * p; res %= p; if (res < 0) res += p; return res; }
template <i64 P>
struct MInt {
    i64 x;
    constexpr MInt() : x {0} {}
    constexpr MInt(i64 x) : x {norm(x % getMod())} {}
    static i64 Mod;
    constexpr static i64 getMod() { return P > 0 ? P : Mod; }
    constexpr static void setMod(i64 Mod_) { Mod = Mod_; }
    constexpr i64 norm(i64 x) const { if (x < 0) x += getMod(); if (x >= getMod()) x -= getMod(); return x; }
    constexpr i64 val() const { return x; }
    constexpr MInt operator-() const { MInt res; res.x = norm(getMod() - x); return res; }
    constexpr MInt inv() const { return power(*this, getMod() - 2); }
    constexpr MInt &operator*=(MInt rhs) & { if (getMod() < (1ULL << 31)) x = x * rhs.x % int(getMod()); else x = mul(x, rhs.x, getMod()); return *this; }
    constexpr MInt &operator+=(MInt rhs) & { x = norm(x + rhs.x); return *this; }
    constexpr MInt &operator-=(MInt rhs) & { x = norm(x - rhs.x); return *this; }
    constexpr MInt &operator/=(MInt rhs) & { return *this *= rhs.inv(); }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) { MInt res = lhs; res *= rhs; return res; }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) { MInt res = lhs; res += rhs; return res; }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) { MInt res = lhs; res -= rhs; return res; }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) { MInt res = lhs; res /= rhs; return res; }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) { i64 v; is >> v; a = MInt(v); return is; }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) { return os << a.val(); }
    friend constexpr bool operator==(MInt lhs, MInt rhs) { return lhs.val() == rhs.val(); }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) { return lhs.val() != rhs.val(); }
    friend constexpr bool operator<(MInt lhs, MInt rhs) { return lhs.val() < rhs.val(); }
};
template <>
i64 MInt<0>::Mod = 1e9 + 7;
constexpr int P = 1e9 + 7;
using Z = MInt<P>;

const Z inv9 = Z(9).inv();

void solve() {
    int m = read();
    int a[10];
    for (int i = 0; i < 10; i++) a[i] = read();

    if (m == 1 and a[0] > 0) { puts("0"); return; }

    Z ans = 0;
    for (int i = 1; i < 10; i++) {
        if (a[i] > 0) {
            ans += Z(i) * power(Z(10), m - 1);
            a[i]--, m--;
            break;
        }
    }

    for (int i = 0; i < 10; i++) {
        int t = min(a[i], m);
        ans += Z(i) * power(Z(10), m - t) * (power(Z(10), t) - 1) * inv9;

        m -= t;
    }

    cout << ans << '\n';
}
    

signed main() {
    for (int T = read(); T--; solve());
    // solve();
    return 0;
}

C

2024 东北省赛 - K - Tasks

按 $b_i$ 分层。限制只有来自同一层的限制，和来自上一层的限制。

对于同一层的 $i, j$ 来说，若 $l_i < l_j$，则 $r_i < r_j$。

对于一个 $l_i$，找到上一层最大的满足 $l_j \le l_i$ 的 $j$。如果 $l_j = l_i$，那么 $r_i < r_j$，否则 $r_i \le r_j$

故不妨从 $l_i$ 最靠后的任务开始确定 $r_i$，取到最右的可行位置。

这样可以使得下一层的任务可以选择的位置尽可能多。

#include <bits/stdc++.h>
using i64 = long long;
#define int i64
#define pb push_back
#define ep emplace
#define eb emplace_back
using std::max, std::min, std::swap;
using std::cin, std::cout, std::string, std::vector;
int read(int x = 0, int f = 0, char ch = getchar()) {
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}

void solve() {
    int n = read();

    vector<vector<std::pair<int, int>>> mp(n + 1);
    vector<int> r(n + 1);

    for (int i = 1; i <= n; i++) {
        int l = read(), b = read();
        mp[b].pb({l, i});
    }

    #define fi first
    #define se second

    for (int i = 0; i <= n; i++) {
        int R = 1e6 + 1;
        std::sort(mp[i].begin(), mp[i].end());

        for (int j = 0; j + 1 < mp[i].size(); j++) {
            if (mp[i][j].fi == mp[i][j + 1].fi) { puts("-1"); return; }
        }

        for (int j = mp[i].size() - 1; j >= 0; j--) {
            auto [l, id] = mp[i][j];

            if (i) {
                auto it = std::upper_bound(mp[i - 1].begin(), mp[i - 1].end(), 
                    std::pair<int, int>(l, n));

                if (it == mp[i - 1].begin()) { puts("-1"); return; }
                it--;
                if (it -> fi == l) {
                    R = min(R, r[it -> se]);
                } else {
                    R = min(R, r[it -> se] + 1);
                }
            }

            r[id] = --R;

            if (l > r[id]) { puts("-1"); return; }
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << r[i] << '\n';
    }

}

signed main() {
    // for (int T = read(); T--; solve());
    solve();
    return 0;
}

D 2-sat

原题 2024 河北省赛 - F - 3 Split