abc226

FiraCode · 2024-09-18 13:59:42 · 个人记录

A

一开始尝试直接输出的时候使用 %.lf 来四舍五入，但是发现 0.5 的时候会输出 0，最后还是用 \lfloor a+0.5 \rfloor 来实现的四舍五入。

B

考虑先按照长度排序，对与长度相同的，把第一个数作为第一关键字，第二个数作为第二关键字以此类推，这样相等的一定是连续一段直接统计即可。

C

显然可以从 n 开始 dfs 一遍，然后若遇到访问过的，那么它以及他后边需要的一定全解锁了，直接返回 0，否则继续下去，如果是叶子就是 t_i。

D

由于 1 \le n \le 500，考虑枚举两个点，那么对与这两个点，设最小满足的为 (a,b)，那么其他满足的一定是当前的倍数，所以我们可以求出任意两对点之间最小的 (a,b) 然后扔到 set 里，然后看有多少不同即可。

E

一开始没看到要求每个点恰好一个出边，还以为不可做。

若最后可以使每个点恰好有一个出边，那么整个图就是若干个环，而每个环有两种方案，所以答案就是 2^{\text{环的个数}}。

#include <bits/stdc++.h>

using namespace std;

namespace A {
    long double n;
    void main() {
        scanf("%Lf", &n);
        printf("%.0Lf", floor(n + 0.5));
    }
}

namespace B {
    int n;
    vector<vector<int>> v;
    void main() {
        scanf("%d", &n);
        v.push_back({});
        for (int i = 1; i <= n; ++i) {
            int l; scanf("%d", &l);
            v.push_back({});
            for (int j = 1; j <= l; ++j) {
                int a; scanf("%d", &a);
                v[i].push_back(a);
            }
        }

        sort(v.begin(), v.end(), [&](vector<int> a, vector<int> b) {
            if (a.size() != b.size()) return a.size() < b.size();
            return a < b;
        });

        int ans = n;
        for (int i = 2; i <= n; ++i) {
            if (v[i] == v[i - 1]) --ans;
        }

        printf("%d\n", ans);
    }
}

namespace C {
    typedef long long ll;
    int n;
    ll t[200010];
    vector<int> e[200010];
    bool st[200010];

    ll dfs(int u) {
        if (st[u]) return 0;
        st[u] = true;

        ll res = 0;
        for (auto t : e[u]) {
            res += dfs(t);
        }

        return res + t[u];
    }

    void main() {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            scanf("%lld", &t[i]);
            int l; scanf("%d", &l);
            for (int j = 1; j <= l; ++j) {
                int c; scanf("%d", &c);
                e[i].push_back(c);
            }
        }

        printf("%lld\n", dfs(n));
    }
}

namespace D {
    int n;
    pair<int, int> a[510];

    int gcd(int a, int b) {
        return !b ? a : gcd(b, a % b);
    }

    void main() {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            scanf("%d%d", &a[i].first, &a[i].second);
        }

        set<pair<int, int>> cnt;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (i != j) {
                    int tx = a[i].first - a[j].first, ty = a[i].second - a[j].second;
                    int t = abs(gcd(tx, ty));

                    cnt.insert({tx / t, ty / t});
                }
            }
        }

        printf("%d\n", cnt.size());
    }
}

namespace E {
    const int mod = 998244353;
    int n, m;
    vector<int> e[200010];
    bool st[200010];
    int cntE, cntV;

    void dfs(int u) {
        st[u] = true;
        ++cntV;
        cntE += e[u].size();

        for (auto v : e[u]) {
            if (!st[v]) {
                dfs(v);
            }
        }
    }

    void main() {
        int ans = 1;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; ++i) {
            int u, v; scanf("%d%d", &u, &v);
            e[u].push_back(v);
            e[v].push_back(u);
        }

        for (int i = 1; i <= n; ++i) {
            if (!st[i]) {
                cntE = cntV = 0;
                dfs(i);

                if (cntE != cntV * 2) ans = 0;
                else {
                    ans *= 2;
                    if (ans >= mod) ans -= mod;
                }
            }
        }

        printf("%d\n", ans);
    }
}