牛客练习赛128

A Cidoai 的幂次序列

给定 $n, k$ ，你需要构造一个长为 $m$ 的正整数序列 $a$ ，满足 $2 \leq m \leq k, \sum_{i = 0}^{m - 1} a_{i}^{a_{(i + 1) mod m}} = n$ 。

（注：右上角为 $a_{(i + 1) mod m}$ ，取模符号在下标处。）

你需要保证对于所有 $a_{i}$ 都有 $0 < a_{i} \leq n$ 。

直接两个数即可。

cout << "2\n";
cout << n - 1 << " " << 1 << '\n';

B Cidoai 的平均数对

给定 $n$ 对数 $(a_{i}, b_{i})$ 和参数 $k$ ，你需要选出一些对使得在满足 $b_{i}$ 的平均值不超过 $k$ 的同时， $a_{i}$ 的和最大，求出这个最大值。

背包变种问题，真搞不懂为什么写不出来

这个题的难点在于转换问题，只需要对于每个 $b_{i} \to b_{i} - k$ 就可以转换为原始的 DP 问题

操作之后需要满足平均值不超过 0，可以设置一个偏移量，使之 DP 时不超过这个值即可。
也可以先将所有 $\leq 0$ 的数全部先选择了 (这些数是必选的)，然后将这些数的和作为容量来做 DP

没有想到转换的方式... 这是第二种，也感觉更好理解。

int f[510 * 510];
void solve() {
    int n, k;cin >> n >> k;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i] >> b[i], b[i] -= k;
    int sum = 0, ans = 0;
    for (int i = 1;i <= n;i++) {
        if (b[i] <= 0)ans += a[i], sum += b[i];
    }
    sum = -sum;
    for (int i = 1;i <= n;i++) {
        if (b[i] <= 0)continue;
        for (int j = sum;j >= b[i];j--) {
            f[j] = max(f[j], f[j - b[i]] + a[i]);
        }
    }
    cout << f[sum] + ans << '\n';
}

C Cidoai 的树上方案

给定大小为 $n$ 的有标号有根树，以 1 为根，求在树外引出一个点向树内任意连边使得构成的简单图不含三元环的方案数。答案对 $998244353$ 取模。

若不选择位置，则其儿子可以选择也可以不选择

若选择当前位置，则其儿子一定是不选择的

$f_{u, 0} = Π (f_{v, 0} + f_{v, 1})$
$f_{u, 1} = Π f_{v, 0}$

#define int long long
constexpr int mod = 998244353;
void solve() {
    int n;cin >> n;
    vector<int> p(n + 1);
    for (int i = 2;i <= n;i++)cin >> p[i];
    vector<array<int, 2>> f(n + 1, {1,1});
    for (int i = n;i >= 1;i--) {
        f[p[i]][0] *= (f[i][0] + f[i][1]) % mod;f[p[i]][0] %= mod;
        f[p[i]][1] *= f[i][0];f[p[i]][1] %= mod;
    }
    cout << (f[1][0] + f[1][1])%mod << '\n';
}

等价于

#define int long long
constexpr int mod = 998244353;
void solve() {
    int n;cin >> n;
    vector<vector<int>> g(n + 1);
    for (int i = 2;i <= n;i++) {
        int x;cin >> x;
        g[x].push_back(i);
        g[i].push_back(x);
    }
    vector<array<int, 2>> f(n + 1, {1,1});
    auto dfs = [&](auto self, int u, int fa = -1) ->void {
        for (auto v : g[u]) {
            if (v == fa)continue;
            self(self, v, u);
            f[u][0] *= f[v][0] + f[v][1];f[u][0] %= mod;
            f[u][1] *= f[v][0];f[u][1] %= mod;
        }
        };
    dfs(dfs, 1);
    cout << (f[1][0] + f[1][1]) % mod << '\n';
}

D Cidoai 的字符集合

Cidoai 听到了 $n$ 首歌。每首歌都有一个旋律长度，第 $i$ 首歌的长度为 $k_{i}$ ，旋律序列为一个长度为 $k_{i}$ 的仅由小写字母组成的单词序列。

他认为这些歌中有一些是相似的。他定义两首歌 $x, y$ 相似当且仅当这两首歌中存在至少一个旋律是相同的，即至少一个单词是相同的，记作 $x \sim y$ 。

你需要为他求出这 $n$ 首歌最少可以被划分成多少个集合，使得每个集合 $S$ 都满足： $\forall u \in S, \exists v \in S, u \neq v, u \sim v$ 或 $| S | = 1$

由题意可以知道，当两个歌曲有一个单词相同就可以划分到同一个集合，(即两个歌曲满足要求就可以连一个边)，关键如何快速添加边

注：多个连通块也满足要求，只要这个连通块的大小大于等于 2 就可以合并成为一个连通块

所以最后只存在两种：若干个大小为 1 的连通块与一大个连通块，即连通块大小为 1 的个数+1

并查集

void solve() {
    int n;cin >> n;
    map<string, int>mp;
    DSU dsu(n + 1);
    for (int i = 1;i <= n;i++) {
        int k;cin >> k;
        while (k--) {
            string s;cin >> s;
            if (mp.count(s)) {
                dsu.merge(i, mp[s]);
            } else {
                mp[s] = i;
            }
        }
    }
    int ans = 1;
    for (int i = 1;i <= n;i++) {
        if (dsu.size(i) == 1)ans++;
    }
    cout << ans << '\n';
}

F: 原：P4844 LJJ爱数数 - 洛谷 | 计算机科学教育新生态