C – Serval and Parenthesis Sequence

这道题主要是运用贪心。首先我们可以确定以下几种情况是肯定无解的：

• 第一个字符是 ‘)’，最后一个字符是 ‘(‘。
• 字符串长度为奇数。

我们发现整个字符串\(s[1 \dots n]\)中，第一个和最后一个字符一定要是 ‘(‘ 和 ‘)’。所以我们只用关心\(s[2 \dots n-1]\)就好。统计需要补充的括号个数：也就是\((n-2)\)减去现已确定的括号个数，分\(remL\)为左括号需要补充的个数、\(remR\)为右括号需要补充的个数。

之后可以考虑贪心替换，优先更换左括号，再更换右括号。最后验一遍即可。

// C.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 3e5 + 2000;
int len, n;
char str[MAX_N];
void goFuck()
{
    printf(":("), exit(0);
}
int main()
{
    scanf("%d", &len), scanf("%s", str), n = len;
    int remL = 0, remR = 0;
    if ((len & 1) || ((len - 2) & 1) || str[0] == ')' || str[len - 1] == '(')
        goFuck();
    str[0] = '(', str[len - 1] = ')';
    len -= 2;
    for (int i = 1; i < n - 1; i++)
        if (str[i] == '(')
            remL++;
        else if (str[i] == ')')
            remR++;
    remL = len / 2 - remL, remR = len / 2 - remR;
    for (int i = 1; i < n - 1; i++)
        if (str[i] == '?' && remL)
            str[i] = '(', remL--;
        else if (str[i] == '?' && remR)
            str[i] = ')', remR--;
    if (remL || remR)
        goFuck();
    int tot = 0;
    for (int i = 0; i < n; i++)
    {
        if (str[i] == '(')
            tot++;
        else
            tot--;
        if (tot == 0 && i != n - 1)
            goFuck();
    }
    if (tot != 0)
        goFuck();
    cout << str;
    return 0;
}

D – Serval and Rooted Tree

一道比较有思维难度的好题。

这其实就是一颗决策树，让你填数字进去实现决策最优。我们可以考虑贪心地进行树形 DP，设\(dp[i]\)为答案的贡献，意义为「比答案大的个数」。这样我们可以进行 DP：

\[ dp[u] = \begin{cases} \sum_{i \in son} dp[i], u \in min \\ min_{i \in son} dp[i] \end{cases}, u \in max \]

当然，额外的，叶子节点的值统统为一。最后的答案是 \(k – dp[1] + 1\)。

// D.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 3e5 + 2000;
int head[MAX_N], current, n, k, fa[MAX_N], deg[MAX_N], dp[MAX_N];
bool mark[MAX_N];
struct edge
{
    int to, nxt;
} edges[MAX_N << 1];
void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}
void dfs(int u)
{
    if (u != 1 && deg[u] == 1)
    {
        k++, dp[u] = 1;
        return;
    }
    if (mark[u])
        dp[u] = 0x3f3f3f3f;
    else
        dp[u] = 0;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        dfs(edges[i].to);
        if (mark[u])
            dp[u] = min(dp[u], dp[edges[i].to]);
        else
            dp[u] += dp[edges[i].to];
    }
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &mark[i]);
    for (int i = 2; i <= n; i++)
        scanf("%d", &fa[i]), addpath(fa[i], i), deg[fa[i]]++, deg[i]++;
    dfs(1);
    printf("%d", k - dp[1] + 1);
    return 0;
}

F – Serval and Bonus Problem

这道题好神仙啊。

我们枚举\(2n-1\)个区间，每一段区间的期望长度是\(\frac{l}{2n+1}\)。我们可以在期望意义下认为这些区间长度相等。枚举时，我们可以记 A 为左边点的个数，B 为右边点的个数：

我们考虑这一段区间是没有点的。我们现在要算这种情况的概率。这种情况的条件：

1. 左边有 A 个点，右边有 B 个点。
2. A 个点中选 k 或更多的点与 B 个点中选 k 或更多的点的配对。
3. A 中剩下的点自行配对，B 也是如此。

我们可以开始推式子了。注意到段内配对出现较多，我们定义\(f(x)\)为「\(x\)个点中自行配对的方案数」：

\[ f(x) = \begin{cases} \prod_{i = 1}^\frac{x}{2} (x – (2i-1)), \text{x为偶数} \\ 0, \text{x为奇数} \end{cases} \]

现在推概率，概率就是上面描述的三种情况，除掉\(f(2n)\)即可：

\[ P(A, B, k) = \frac{ {A \choose k } {B \choose k} k! f(A) f(B) }{f(2n)} \]

其中\(k!\)为这些选中的\(2k\)个点的配对个数。现在推期望：

\[ E(A, B, k) = len * \sum_{i = k}^{min(A,B)} P(A,B,i) \\ E(A, B, k) = \frac{l}{2n+1} * \sum_{i = k}^{min(A,B)} \frac{ {A \choose i } {B \choose i} i! f(A) f(B) }{f(2n)} \]

推完了，求和即可。

// F.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 5100, mod = 998244353;

ll n, k, l, f[MAX_N << 1], level[MAX_N], level_rev[MAX_N];

ll quick_pow(ll bas, ll tim)
{
    ll ans = 1;
    while (tim)
    {
        if (tim & 1)
            ans = ans * bas % mod;
        bas = bas * bas % mod;
        tim >>= 1;
    }
    return ans;
}

ll comb(ll x, ll y)
{
    return level[x] * level_rev[x - y] % mod * level_rev[y] % mod;
}

int main()
{
    scanf("%d%d%d", &n, &k, &l);
    // Get Ready for the f;
    f[0] = 1;
    for (int i = 1; i <= n; i++)
        f[2 * i] = f[2 * (i - 1)] * (2 * i - 1) % mod;

    // Get ready for the levels;
    level[1] = level[0] = level_rev[1] = level_rev[0] = 1;
    for (int i = 2; i < MAX_N; i++)
        level[i] = level[i - 1] * i % mod;
    level_rev[MAX_N - 1] = quick_pow(level[MAX_N - 1], mod - 2);
    for (int i = MAX_N - 1; i >= 3; i--)
        level_rev[i - 1] = level_rev[i] * i % mod;

    ll answer = 0;

    for (int h = 2; h <= 2 * n; h++)
    {
        int A = h - 1, B = 2 * n - h + 1;
        for (int i = k; i <= min(A, B); i++)
        {
            ll all = comb(A, i) * comb(B, i) % mod * level[i] % mod * f[A - i] % mod * f[B - i] % mod;
            answer = (answer + all) % mod;
        }
    }
    answer = answer * quick_pow(2 * n + 1, mod - 2) % mod * quick_pow(f[2 * n], mod - 2) % mod * l % mod;
    printf("%lld", answer);
    return 0;
}