AtCoder Beginner Contest 451 题解

A

注意别把是否违法搞反, 直接模拟即可

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()
#define vec1(T, name, n, val) vector<T> name(n, val)
#define vec2(T, name, n, m, val) vector<vector<T>> name(n, vector<T>(m, val))
#define vec3(T, name, n, m, k, val) vector<vector<vector<T>>> name(n, vector<vector<T>>(m, vector<T>(k, val)))
#define vec4(T, name, n, m, k, p, val) vector<vector<vector<vector<T>>>> name((n), vector<vector<vector<T>>>((m), vector<vector<T>>((k), vector<T>((p), (val)))))

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;
using LL = long long;
using LD = long double;
using ULL = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using PLD = pair<LD, LD>;

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 Hash {
    vector<int> h, p;
    int B = 131;
    Hash(const string& s) {
        int n = s.size();
        h.resize(n + 1, 0);
        p.resize(n + 1, 1);
        for (int i = 0; i < n; ++i) {
            p[i + 1] = p[i] * B % MOD;
            h[i + 1] = (h[i] * B + s[i]) % MOD;
        }
    }

    LL get(int l, int r) {
        LL v = h[r] - h[l - 1] * p[r - l + 1] % MOD;
        v = (v % MOD + MOD) % MOD;
        return v;
    }
};

void solve() {
    string s;
    cin >> s;
    if (s.size() % 5) {
        cout << "No" << '\n';
    }
    else cout << "Yes" << '\n';
/**/ #ifdef LOCAL
    cout << flush;
/**/ #endif
}

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()
#define vec1(T, name, n, val) vector<T> name(n, val)
#define vec2(T, name, n, m, val) vector<vector<T>> name(n, vector<T>(m, val))
#define vec3(T, name, n, m, k, val) vector<vector<vector<T>>> name(n, vector<vector<T>>(m, vector<T>(k, val)))
#define vec4(T, name, n, m, k, p, val) vector<vector<vector<vector<T>>>> name((n), vector<vector<vector<T>>>((m), vector<vector<T>>((k), vector<T>((p), (val)))))

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;
using LL = long long;
using LD = long double;
using ULL = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using PLD = pair<LD, LD>;

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 Hash {
    vector<int> h, p;
    int B = 131;
    Hash(const string& s) {
        int n = s.size();
        h.resize(n + 1, 0);
        p.resize(n + 1, 1);
        for (int i = 0; i < n; ++i) {
            p[i + 1] = p[i] * B % MOD;
            h[i + 1] = (h[i] * B + s[i]) % MOD;
        }
    }

    LL get(int l, int r) {
        LL v = h[r] - h[l - 1] * p[r - l + 1] % MOD;
        v = (v % MOD + MOD) % MOD;
        return v;
    }
};

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

    for (int i = 1; i <= m; ++i) {
        cout << b[i] - a[i] << '\n';
    }
/**/ #ifdef LOCAL
    cout << flush;
/**/ #endif
}

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

移除不超过的所有树木, 经典操作, 注意方法删除的右侧是开区间

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()
#define vec1(T, name, n, val) vector<T> name(n, val)
#define vec2(T, name, n, m, val) vector<vector<T>> name(n, vector<T>(m, val))
#define vec3(T, name, n, m, k, val) vector<vector<vector<T>>> name(n, vector<vector<T>>(m, vector<T>(k, val)))
#define vec4(T, name, n, m, k, p, val) vector<vector<vector<vector<T>>>> name((n), vector<vector<vector<T>>>((m), vector<vector<T>>((k), vector<T>((p), (val)))))

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;
using LL = long long;
using LD = long double;
using ULL = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using PLD = pair<LD, LD>;

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 Hash {
    vector<int> h, p;
    int B = 131;
    Hash(const string& s) {
        int n = s.size();
        h.resize(n + 1, 0);
        p.resize(n + 1, 1);
        for (int i = 0; i < n; ++i) {
            p[i + 1] = p[i] * B % MOD;
            h[i + 1] = (h[i] * B + s[i]) % MOD;
        }
    }

    LL get(int l, int r) {
        LL v = h[r] - h[l - 1] * p[r - l + 1] % MOD;
        v = (v % MOD + MOD) % MOD;
        return v;
    }
};

void solve() {
    int q;
    cin >> q;
    multiset<int> st;
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int h;
            cin >> h;
            st.insert(h);
        }
        else {
            int h;
            cin >> h;
            auto it = st.upper_bound(h);
            st.erase(st.begin(), it);
        }
        cout << st.size() << '\n';
    }
/**/ #ifdef LOCAL
    cout << flush;
/**/ #endif
}

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

注意到生成数的范围不会超过, 因此可以用一个优先队列维护

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()
#define vec1(T, name, n, val) vector<T> name(n, val)
#define vec2(T, name, n, m, val) vector<vector<T>> name(n, vector<T>(m, val))
#define vec3(T, name, n, m, k, val) vector<vector<vector<T>>> name(n, vector<vector<T>>(m, vector<T>(k, val)))
#define vec4(T, name, n, m, k, p, val) vector<vector<vector<vector<T>>>> name((n), vector<vector<vector<T>>>((m), vector<vector<T>>((k), vector<T>((p), (val)))))

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;
using LL = long long;
using LD = long double;
using ULL = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using PLD = pair<LD, LD>;

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 Hash {
    vector<int> h, p;
    int B = 131;
    Hash(const string& s) {
        int n = s.size();
        h.resize(n + 1, 0);
        p.resize(n + 1, 1);
        for (int i = 0; i < n; ++i) {
            p[i + 1] = p[i] * B % MOD;
            h[i + 1] = (h[i] * B + s[i]) % MOD;
        }
    }

    LL get(int l, int r) {
        LL v = h[r] - h[l - 1] * p[r - l + 1] % MOD;
        v = (v % MOD + MOD) % MOD;
        return v;
    }
};

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

void solve() {
    int n;
    cin >> n;
    LL m = INF;
    priority_queue<LL, vector<LL>, greater<LL>> q;
    vector<string> a;
    set<LL> st;

    for (LL i = 1; i <= m; i *= 2) {
        a.push_back(to_string(i));
        q.push(i);
        st.insert(i);
    }

    int cnt = 0;
    while (q.size()) {
        LL u = q.top();
        q.pop();
        cnt++;
        if (cnt == n) {
            cout << u << '\n';
            break;
        }
        for (string v : a) {
            int t = v.size();
            i128 new_v = u * q_pow(10, t) + stoll(v);
            if (new_v > INF) continue;
            if (st.count(new_v)) continue;
            st.insert(new_v);
            q.push(new_v);
        }
    }
/**/ #ifdef LOCAL
    cout << flush;
/**/ #endif
}

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

观察点的数量是, 也就是左右的做法

我的最初想法是做判断, 打算交上去试试, 但是明显是无法通过的因为复杂度不对 但是过了大部分数据

因此大方向是对的

可以构建最小生成树, 然后对每个点跑最短路

判断相较于原图是否有松弛边

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()
#define vec1(T, name, n, val) vector<T> name(n, val)
#define vec2(T, name, n, m, val) vector<vector<T>> name(n, vector<T>(m, val))
#define vec3(T, name, n, m, k, val) vector<vector<vector<T>>> name(n, vector<vector<T>>(m, vector<T>(k, val)))
#define vec4(T, name, n, m, k, p, val) vector<vector<vector<vector<T>>>> name((n), vector<vector<vector<T>>>((m), vector<vector<T>>((k), vector<T>((p), (val)))))

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;
using LL = long long;
using LD = long double;
using ULL = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using PLD = pair<LD, LD>;

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 Hash {
    vector<int> h, p;
    int B = 131;
    Hash(const string& s) {
        int n = s.size();
        h.resize(n + 1, 0);
        p.resize(n + 1, 1);
        for (int i = 0; i < n; ++i) {
            p[i + 1] = p[i] * B % MOD;
            h[i + 1] = (h[i] * B + s[i]) % MOD;
        }
    }

    LL get(int l, int r) {
        LL v = h[r] - h[l - 1] * p[r - l + 1] % MOD;
        v = (v % MOD + MOD) % MOD;
        return v;
    }
};

void solve() {
    int n;
    cin >> n;
    struct F {
        int a, b, c;
        bool operator<(const F& f) const {
            return c < f.c;
        };
    };

    vector<int> p(n + 1, 0);
    for (int i = 1; i <= n; ++i) p[i] = i;

    function<int(int)> find = [&](int u) -> int {
        if (u != p[u]) {
            p[u] = find(p[u]);
        }
        return p[u];
    };

    vector<F> ed;
    ed.reserve(n * n / 2);
    vec2(int, dis, n + 1, n + 1, 0);

    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            cin >> dis[i][j];
            dis[j][i] = dis[i][j];
            ed.push_back({i, j, dis[i][j]});
        }
    }

    sort(all(ed));
    vector<vector<PLL>> g(n + 1);
    for (auto [a, b, c] : ed) {
        int fa1 = find(a), fa2 = find(b);
        if (fa1 == fa2) continue;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
        p[fa2] = fa1;
    }

    vec2(LL, d, n + 1, n + 1, -1);

    auto bfs = [&](int x) {
        d[x][x] = 0;
        queue<int> q;
        q.push(x);
        while (q.size()) {
            int u = q.front();
            q.pop();
            for (auto &[v, w] : g[u]) {
                if (d[x][v] == -1) {
                    d[x][v] = d[x][u] + w;
                    q.push(v);
                }
            }
        }
    };

    for (int i = 1; i <= n; ++i) bfs(i);

    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            if (dis[i][j] != d[i][j]) {
                cout << "No" << '\n';
                return;
            }
        }
    }

    cout << "Yes" << '\n';

/**/ #ifdef LOCAL
        cout
        << flush;
/**/ #endif
}

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

扩展域并查集题

对于一个二分图来说, 当前点染成黑色或者白色都是可以的

因此对于原集合, 扩展成

假设当前需要添加边, 那么找两对节点

然后判断

• 是否构成了奇环, 如果是奇环输出
• 如果是重边, 直接输出答案
• 否则需要撤销原来产生的贡献, 将两个连通块合并, 再累加贡献

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()
#define vec1(T, name, n, val) vector<T> name(n, val)
#define vec2(T, name, n, m, val) vector<vector<T>> name(n, vector<T>(m, val))
#define vec3(T, name, n, m, k, val) vector<vector<vector<T>>> name(n, vector<vector<T>>(m, vector<T>(k, val)))
#define vec4(T, name, n, m, k, p, val) vector<vector<vector<vector<T>>>> name((n), vector<vector<vector<T>>>((m), vector<vector<T>>((k), vector<T>((p), (val)))))

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;
using LL = long long;
using LD = long double;
using ULL = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using PLD = pair<LD, LD>;

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 Hash {
    vector<int> h, p;
    int B = 131;
    Hash(const string& s) {
        int n = s.size();
        h.resize(n + 1, 0);
        p.resize(n + 1, 1);
        for (int i = 0; i < n; ++i) {
            p[i + 1] = p[i] * B % MOD;
            h[i + 1] = (h[i] * B + s[i]) % MOD;
        }
    }

    LL get(int l, int r) {
        LL v = h[r] - h[l - 1] * p[r - l + 1] % MOD;
        v = (v % MOD + MOD) % MOD;
        return v;
    }
};

void solve() {
    int n, q;
    cin >> n >> q;

    int m = (n + 1) * 2;
    vector<bool> vis(m);
    vector<int> p(m), sz(m);

    LL ans = 0;
    bool ok = 1;

    for (int i = 0; i < m; ++i) p[i] = i;
    for (int i = 0; i <= n; ++i) sz[i] = 1;

    function<int(int)> find = [&](int x) {
        if (p[x] != x) return p[x] = find(p[x]);
        return p[x];
    };

    while (q--) {
        int a, b;
        cin >> a >> b;
        int x1 = find(a);
        int x2 = find(a + n);
        int y1 = find(b);
        int y2 = find(b + n);

        if (x1 == y1 || !ok) {
            cout << -1 << '\n';
            ok = 0;
        }
        else if (x1 == y2) {
            cout << ans << '\n';
        }
        else {
            // 首先将贡献撤销
            if (vis[x1]) ans -= sz[x1], vis[x1] = 0;
            if (vis[x2]) ans -= sz[x2], vis[x2] = 0;
            if (vis[y1]) ans -= sz[y1], vis[y1] = 0;
            if (vis[y2]) ans -= sz[y2], vis[y2] = 0;

            // 然后累加贡献
            sz[x1] += sz[y2];
            sz[y1] += sz[x2];
            p[y2] = x1, p[x2] = y1;

            if (sz[x1] < sz[y1]) {
                vis[x1] = 1;
                ans += sz[x1];
            }
            else {
                vis[y1] = 1;
                ans += sz[y1];
            }

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

/**/ #ifdef LOCAL
        cout << flush;
/**/ #endif
    }
}

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;
}