前言

我只会到D了，剩下的看出题人题解吧，D假题了，我的是假题意做法）

题解

A.Cidoai的幂次序列

小思维，输出和即可

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    i64 n, k;
    std::cin >> n >> k;

    std::cout << 2 << '\n';
    std::cout << 1 << ' ' << n - 1 << '\n';
} 

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

B.Cidoai的平均数对

这个题可以转化为背包问题，我们把小于等于直接选上，并把的和作为背包的容量，对于那些大于的物品来说，他们超过的部分即可以看做是物品的重量，那你肯定会有疑惑为什么可以这样做，这就是平均数的性质，比如当时，我们装进去一个，此时如果再装一个物品的话，可以装某一个，如果是装俩的话，我可以装两个或者一个和一个没问题吧，那就按我之前说的，是不是就把背包容量看成了，把每个物品的重量看做是，这样去取的话平均值一点不会超过。比如数组为，且，我们会首先把选上，此时背包容量我们就看做是++，剩下的两个物品的价值看做是和然后用01背包的思想去装就好了。

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    int n, k;
    std::cin >> n >> k;

    int sum = 0, V = 0;
    std::vector<std::pair<int, int> > v;
    for (int i = 1; i <= n; i++) {
        int a, b;
        std::cin >> a >> b;
        if (b <= k) {
            sum += a;
            V += k - b;
        }
        else {
            v.push_back({a, b - k});
        }
    }

    std::vector<int> dp(V + 1);
    for (auto [a, b] : v) {
        for (int i = V; i >= b; i--) {
            dp[i] = std::max(dp[i], dp[i - b] + a);
        }
    }

    std::cout << dp[V] + sum << '\n';
} 

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

C.Cidoai的树上方案

典型的树形，每个点可以有选或不选两种状态，如果当前点选了，所有的儿子节点都不能选，如果当前节点不选，所有的儿子节点都可以选或不选

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")

using i64 = long long;
using u64 = unsigned long long;

const int mod = 998244353;

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<int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(i64 x) : x{norm(x % getMod())} {}
    
    static int Mod;
    constexpr static int getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_) {
        Mod = Mod_;
    }
    constexpr int norm(int x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr int val() const {
        return x;
    }
    explicit constexpr operator int() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) & {
        x = 1LL * 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();
    }
};

template<>
int MInt<0>::Mod = 998244353;

template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

constexpr int P = 998244353;
using Z = MInt<P>;

void solve() {
    int n;
    std::cin >> n;

    std::vector<std::vector<int> > e(n + 1);
    for (int i = 2; i <= n; i++) {
        int a;
        std::cin >> a;
        e[a].push_back(i);
    }

    std::vector<std::vector<Z> > dp(n + 1, std::vector<Z> (2, 0));
    auto dfs = [&] (auto self, int u, int f) -> void {
        if (e[u].size() == 0) {
            dp[u][0] = 1;
            dp[u][1] = 1;
            return;
        }

        Z ans = 1;
        Z res = 1;

        for (auto v : e[u]) {
            if (v == f) continue;
            self(self, v, u);
            ans *= dp[v][0] + dp[v][1];
            res *= dp[v][0];
        }
        
        dp[u][0] = ans;
        dp[u][1] = res;
    };


    dfs(dfs, 1, 0);
    
    std::cout << dp[1][0] + dp[1][1] << '\n';
} 

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

D.Cidoai的字符集合

我们把所有的单词对应的曲子放到一个集合里，集合里的任意两个都相似，然后就并查集做完了。

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    int n;
    std::cin >> n;

    std::map<std::string, std::vector<int> > mp;
    std::vector<int> p (n + 1);
    for (int i = 1; i <= n; i++) {
        int k;
        std::cin >> k;
        p[i] = i;
        for (int j = 1; j <= k; j++) {
            std::string s;
            std::cin >> s;
            mp[s].push_back(i);
        }
    }

    auto find = [&] (auto self, int x) -> int {
        if (x == p[x]) return x;
        else return p[x] = self(self, p[x]);
    };

    auto merge = [&] (int u, int v) -> void {
        int fx = find(find, u), fy = find(find, v);
        if (fx != fy) {
            p[fx] = fy;
        }
    };

    for (auto [s, v] : mp) {
        for (int i = 1; i < v.size(); i++) {
            merge(v[i], v[i - 1]);
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (p[i] == i) {
            ans ++;
        }
    }

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

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}