感觉前面几题难度貌似不是那么难（-V-），不过 $D$ 虽然 $ac$ ，都没意识到假了。。

A. Cidoai的幂次序列

思路

对于序列 $[n-1,1]$ ， $a_0^{a_1}$ + $a_1^{a_0} =$ $(n-1)^1$ + $1^{n-1} =n$ ，是满足条件的。

复杂度

时间复杂度和空间复杂度均为 $O(1)$

代码实现

// Problem: Cidoai的幂次序列
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/88880/A
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
    int n, k;
    cin >> n >> k;
    cout << 2 << '\n';
    cout << n - 1 << ' ' << 1 << '\n';
}

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

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

B. Cidoai的平均数对

思路

令选择出的下标序列为 $p$ ，序列的长度为 $m$ ，若该下标序列满足 $b_i$ 的平均数不超过 $k$ ，那么 $(b_{p_1}-k) (b_{p_2}-k) ... (b_{p_m}-k) \le 0$ 。

此时的问题则可以转换为，选出一个下标序列，下标序列每一项对应的 $b_i-k$ 之和不超过 $0$ 的情况下，能取到对应 $a_i$ 之和的最大值。

可以用背包 $dp$ 解决这个问题，令 $f(i,j)$ 为在前 $i$ 对数中选，满足 $b_i - k$ 之和为 $j$ 的序列对应的 $a_i$ 之和最大值。

初始化时，设置 $f(0,-k) = 0$ ，表示还未取数对的情况，其他设置为 $-\infty$ 。

此时 $f(i,j) = max(f(i-1,j),f(i-1,j-(b_i-k)) a_i)$ ， $f(i-1,j)$ 为不选 $(a_i,b_i)$ 的情况， $f(i-1,j-(b_i-k) a_i)$ 为选择 $(a_i,b_i)$ 的情况。

因为 $0 \le b_i,k \le 500$ ，所以 $j$ 的取值范围最大为 $[-500^2,500^2]$ ，计算状态时枚举这个范围的 $j$ 即可。

因为第二维的 $j$ 涉及到负数，所以在代码实现的时候可以加上一个偏移量 $M = 500^2$ ，使得数组下标不越界。

直接按上面的状态表示定义数组，数组大小最大为 $500^3$ ，会超过空间限制，所以需要滚动优化，每次只保留上一层状态，计算时第一维对应的上一层则从 $i-1$ 变为 $1-(i \bmod 2)$ ，用相邻下标奇偶性相反的性质表示上一层。

复杂度

时间复杂度为 $O(n*max(b_i,k)^2)$ ,空间复杂度为 $O(max(b_i,k)^2)$

代码实现

// Problem: Cidoai的平均数对
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/88880/B
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 501, M = N * N;

int n, k;
int f[2][2 * M + N];
// 因为 bi - k 可能为负数，所以需要加一些空间防止越界

void solve()
{
    cin >> n >> k;
    memset(f, -0x3f, sizeof(f));
    f[0][M - k] = 0;
    for (int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b;
        b -= k;
        int op = i % 2;
        for (int j = 0; j < 2 * M; j++) {
            f[op][j] = f[op ^ 1][j];
            if (j >= b) {
                f[op][j] = max(f[op][j], f[op ^ 1][j - b] + a);
            }
        }
    }
    int ans = 0;
    for (int i = 0; i <= M - k; i++) {
        ans = max(ans, f[n % 2][i]);
    }
    cout << ans;
}

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

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

C. Cidoai的树上方案

思路

令 $f(u,0)$ 为以节点 $u$ 不与树外点连边，以该节点为根的子树与树外点连若干条边不含三元环的方案数， $f(u,1)$ 同理，表示的是节点 $u$ 与树外点连边的情况。

树外一点要连接树上的点构成三元环，那么肯定是选树上相邻的两个点进行连边。

因此，若父节点不与树外点连边，那么子节点和树外点可以连边也可以不连边，否则，子节点必然不能与树外点连边。

那么对于非叶子节点 $u$ ， $f(u,0) = \prod_v (f(v,0) f(v,1))$ ， $f(u,1) = \prod_v f(v,0)$ ( $v$ 为 $u$ 的子节点)。

对于叶子节点 $u$ ，与树外点相连和不连都是一种情况，所以 $f(u,0)= f(u,1)=1$ 。

复杂度

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。

代码实现

// Problem: Cidoai的树上方案
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/88880/C
// Memory Limit: 524288 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 2e6 + 5, mod = 998244353;

int n;
int f[N][2];
vector<int> h[N];

void dfs(int u)
{
    f[u][0] = f[u][1] = 1;
    for (int v : h[u]) {
        dfs(v);
        f[u][0] *= (f[v][0] + f[v][1]) % mod;
        f[u][0] %= mod;
        f[u][1] *= f[v][0];
        f[u][1] %= mod;
    }
}

void solve()
{
    cin >> n;
    for (int i = 2; i <= n; i++) {
        int j;
        cin >> j;
        h[j].push_back(i);
    }
    dfs(1);
    int ans = (f[1][0] + f[1][1]) % mod;
    cout << ans;
}

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

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

题解 | #牛客练习赛128#

A. Cidoai的幂次序列

思路

复杂度

代码实现

B. Cidoai的平均数对

思路

复杂度

代码实现

C. Cidoai的树上方案

思路

复杂度

代码实现