AtCoder Beginner Contest 448 题解

A

直接模拟即可

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<LD, LD> PLD;

const int N = 1e5 + 10, MOD = 998244353;
const int INF = 1e9;
const LL LL_INF = 1e18;
const LD EPS = 1e-8;
const int dx4[] = {-1, 0, 1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

istream &operator>>(istream &is, i128 &val) {
    string str;
    is >> str;
    val = 0;
    bool flag = false;
    if (str[0] == '-') flag = true, str = str.substr(1);
    for (char &c: str) val = val * 10 + c - '0';
    if (flag) val = -val;
    return is;
}

ostream &operator<<(ostream &os, i128 val) {
    if (val < 0) os << "-", val = -val;
    if (val > 9) os << val / 10;
    os << static_cast<char>(val % 10 + '0');
    return os;
}

bool cmp(LD a, LD b) {
    if (fabs(a - b) < EPS) return 1;
    return 0;
}

void solve() {
    int n, x;
    cin >> n >> x;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    for (int i = 1; i <= n; ++i) {
        if (a[i] < x) {
            x = a[i];
            cout << 1 << '\n';
        }
        else cout << 0 << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    while (T--) solve();
    cout << fixed << setprecision(15);

    return 0;
}

B

题目意思有点麻烦, 但是可以贪心的想因为没个菜只会用一种胡椒

为了使得总的使用量最大, 可以优先使用库存量最大的胡椒

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<LD, LD> PLD;

const int N = 1e5 + 10, MOD = 998244353;
const int INF = 1e9;
const LL LL_INF = 1e18;
const LD EPS = 1e-8;
const int dx4[] = {-1, 0, 1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

istream &operator>>(istream &is, i128 &val) {
    string str;
    is >> str;
    val = 0;
    bool flag = false;
    if (str[0] == '-') flag = true, str = str.substr(1);
    for (char &c: str) val = val * 10 + c - '0';
    if (flag) val = -val;
    return is;
}

ostream &operator<<(ostream &os, i128 val) {
    if (val < 0) os << "-", val = -val;
    if (val > 9) os << val / 10;
    os << static_cast<char>(val % 10 + '0');
    return os;
}

bool cmp(LD a, LD b) {
    if (fabs(a - b) < EPS) return 1;
    return 0;
}

struct F {
    int id;
    int v;

    bool operator< (const F &a) const {
        return v > a.v;
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<F> a(m + 1);
    vector<int> s(m + 1);
    for (int i = 1; i <= m; ++i) {
        cin >> a[i].v;
        a[i].id = i;
        s[i] = a[i].v;
    }

    vector<int> need(m + 1);
    for (int i = 1; i <= n; ++i) {
        int type, v;
        cin >> type >> v;
        need[type] += v;
    }

    sort(a.begin() + 1, a.begin() + m + 1);

    int ans = 0;
    for (int i = 1; i <= m; ++i) {
        int j = a[i].id;
        if (s[j] >= need[j]) ans += need[j];
        else ans += s[j];
    }

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    while (T--) solve();
    cout << fixed << setprecision(15);

    return 0;
}

C

注意到, 每次操作不会真删除小球, 并且每次最多操作 $k \le 5$ 个小球, 直接用 $multiset$ 维护即可

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<LD, LD> PLD;

const int N = 1e5 + 10, MOD = 998244353;
const int INF = 1e9;
const LL LL_INF = 1e18;
const LD EPS = 1e-8;
const int dx4[] = {-1, 0, 1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

istream &operator>>(istream &is, i128 &val) {
    string str;
    is >> str;
    val = 0;
    bool flag = false;
    if (str[0] == '-') flag = true, str = str.substr(1);
    for (char &c: str) val = val * 10 + c - '0';
    if (flag) val = -val;
    return is;
}

ostream &operator<<(ostream &os, i128 val) {
    if (val < 0) os << "-", val = -val;
    if (val > 9) os << val / 10;
    os << static_cast<char>(val % 10 + '0');
    return os;
}

bool cmp(LD a, LD b) {
    if (fabs(a - b) < EPS) return 1;
    return 0;
}

void solve() {

    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    multiset<int> st;
    for (int i = 1; i <= n; ++i) cin >> a[i], st.insert(a[i]);

    while (q--) {
        int k;
        cin >> k;
        vector<int> del;
        for (int i = 0; i < k; ++i) {
            int id;
            cin >> id;
            auto it = st.lower_bound(a[id]);
            st.erase(it);
            del.push_back(a[id]);
        }
        cout << *st.begin() << '\n';
        for (int v : del) st.insert(v);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    while (T--) solve();
    cout << fixed << setprecision(15);

    return 0;
}

D

可以尝试以 $1$ 号点为根节点, 这样所有的路径都是从根节出发的

然后 $dfs$ 过程中记录一个桶和 $flag$ 记录当前路径上是否存在相同的数字

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<LD, LD> PLD;

const int N = 1e5 + 10, MOD = 998244353;
const int INF = 1e9;
const LL LL_INF = 1e18;
const LD EPS = 1e-8;
const int dx4[] = {-1, 0, 1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

istream &operator>>(istream &is, i128 &val) {
    string str;
    is >> str;
    val = 0;
    bool flag = false;
    if (str[0] == '-') flag = true, str = str.substr(1);
    for (char &c: str) val = val * 10 + c - '0';
    if (flag) val = -val;
    return is;
}

ostream &operator<<(ostream &os, i128 val) {
    if (val < 0) os << "-", val = -val;
    if (val > 9) os << val / 10;
    os << static_cast<char>(val % 10 + '0');
    return os;
}

bool cmp(LD a, LD b) {
    if (fabs(a - b) < EPS) return 1;
    return 0;
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    vector<vector<int>> g(n + 1);
    for (int i = 1; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    vector<int> ans(n + 1);
    function<void(int, int, bool, unordered_map<int, int>&)> dfs = [&](int u, int fa, bool flg, unordered_map<int, int> &mp) {
        bool cur = flg;
        if (mp[a[u]] > 0) cur |= 1;
        ans[u] = cur;
        mp[a[u]]++;
        for (int v : g[u]) {
            if (v == fa) continue;
            dfs(v, u, cur, mp);
        }
        mp[a[u]]--;
    };

    unordered_map<int, int> mp;
    dfs(1, 0, 0, mp);

    for (int i = 1; i <= n; ++i) {
        if (ans[i]) cout << "Yes" << '\n';
        else cout << "No" << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    while (T--) solve();
    cout << fixed << setprecision(15);

    return 0;
}

E

注意到 $n$ 可以认为有无穷位的

$\left \lfloor \frac{N}{M} \right \rfloor \mod 10007$

等价于

$\left \lfloor N \right \rfloor \mod M \times 10007$

因此问题转化为如何求 $N$ 注意到假设当前加入的一串数字是 $l_i$ 个 $c_i$ 当前数字是 $N$

那么加入后的 $N$ 变为

$N \times 10 ^ {l_di} + c_i \times 11...1$ , $1$ 的数量有 $l_i$ 个

那么问题转化为

如何快速的求 $11...1$ 的值, 可以首先预处理 $1\sim 10 ^ 6$ 长度的 $1$ 串的值

如果 $l_i > 10 ^ 6$ 将 $l_i$ 拆分, 因为长度最多 $10 ^ 9$ , 最多拆 $1000$ 次如果 $l_i \le 10 ^ 6$ , 直接 $O(1)$ 查表

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<LD, LD> PLD;

const int N = 1e6 + 10;
LL MOD = 1e4 + 7;
const int INF = 1e9;
const LL LL_INF = 1e18;
const LD EPS = 1e-8;
const int dx4[] = {-1, 0, 1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

istream &operator>>(istream &is, i128 &val) {
    string str;
    is >> str;
    val = 0;
    bool flag = false;
    if (str[0] == '-') flag = true, str = str.substr(1);
    for (char &c: str) val = val * 10 + c - '0';
    if (flag) val = -val;
    return is;
}

ostream &operator<<(ostream &os, i128 val) {
    if (val < 0) os << "-", val = -val;
    if (val > 9) os << val / 10;
    os << static_cast<char>(val % 10 + '0');
    return os;
}

bool cmp(LD a, LD b) {
    if (fabs(a - b) < EPS) return 1;
    return 0;
}

LL q_pow(LL a, LL b) {
    LL ans = 1;
    a %= MOD;
    while (b) {
        if (b & 1) ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

void solve() {
    LL k, m;
    cin >> k >> m;
    vector<LL> f(N);
    vector<LL> t(N);

    t[0] = 1;
    MOD = 10007ll * m;
    for (int i = 1; i < N; ++i) {
        f[i] = (f[i - 1] * 10ll + 1) % MOD;
        t[i] = t[i - 1] * 10 % MOD;
    }

    auto calc = [&](int len) {
        LL ans = 0;
        int sz = 1e6;
        int cnt = len / sz;
        for (int i = 1; i <= cnt; ++i) {
            ans = (ans * t[sz] % MOD + f[sz]) % MOD;
        }
        int r = len % sz;
        ans = (ans * t[r] % MOD + f[r]) % MOD;
        return ans;
    };

    LL cur = 0;
    cur = 0;
    for (int i = 0; i < k; ++i) {
        int c, l;
        cin >> c >> l;
        cur = cur * q_pow(10, l) % MOD;
        cur = (cur + 1ll * c * calc(l)) % MOD;
        cur %= MOD;
    }

    cur /= m;
    cout << cur % MOD << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    while (T--) solve();
    cout << fixed << setprecision(15);

    return 0;
}

F

分块内这样走一定是比较优的

因此可以对 $x$ 分块, 对 $y$ 排序, 如果是奇数块从小到大排, 如果是偶数块从大到小排, 这样首尾能相接, 代价比较小

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<LD, LD> PLD;

const int N = 2e7 + 10, MOD = 998244353;
const int INF = 1e9;
const LL LL_INF = 1e18;
const LD EPS = 1e-8;
const int dx4[] = {-1, 0, 1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

istream &operator>>(istream &is, i128 &val) {
    string str;
    is >> str;
    val = 0;
    bool flag = false;
    if (str[0] == '-') flag = true, str = str.substr(1);
    for (char &c: str) val = val * 10 + c - '0';
    if (flag) val = -val;
    return is;
}

ostream &operator<<(ostream &os, i128 val) {
    if (val < 0) os << "-", val = -val;
    if (val > 9) os << val / 10;
    os << static_cast<char>(val % 10 + '0');
    return os;
}

bool cmp(LD a, LD b) {
    if (fabs(a - b) < EPS) return 1;
    return 0;
}

void solve() {
    int n;
    cin >> n;
    vector<PII> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i].x >> a[i].y;
    int sz = N / 240;

    cout << 1 << ' ';
    for (int l = 0, r = sz, t = 1; l < N; l = r + 1, r = min(N - 1, r + sz), t++) {
        vector<array<int, 3>> vec;
        for (int i = 2; i <= n; ++i) {
            if (a[i].x >= l && a[i].x <= r) {
                vec.push_back({a[i].y, a[i].x, i});
            }
        }

        sort(all(vec), [&](const array<int, 3> &x, const array<int, 3> &y) {
            if (t & 1) return x[0] < y[0];
            return x[0] > y[0];
        });

        for (auto[y, x, id] : vec) cout << id << ' ';
    }

    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    while (T--) solve();
    cout << fixed << setprecision(15);

    return 0;
}