P3211:[HNOI2011]XOR和路径题解

主要思路

首先,这道题是概率和期望分开算的,进行 DP 时实质上是对概率进行 DP。考虑拆位,设\(dp_b [u]\)为从\(u \to n\)在第\(b\)位为\(1\)的概率,那么显然:

\[ dp_b[u] = \frac{1}{deg[u]}( \sum_{weight(u, v) !\& b} dp_b[v] \sum_{weight(u, v) \& b} (1 – dp_b[v]) ) \]

其中,\((1 – dp_b[v])\)为\(v\)为\(0\)的概率,最后答案消元完就是\(\sum_{i = 1} ans[i] 2^i\)。

继续阅读P3211:[HNOI2011]XOR和路径题解

[Fortuna OJ]Aug 4th – Group A 解题报告

今天被各路神仙吊打,顺利 gg。

A – Forging 锻造

在考场上我推了个有后效性的 DP,还以为是高斯消元,然后看到数据范围就 GG 了。这道题主要是把一些东西给转换掉了。

首先,对一个概率为\(p\)的事件,它的期望次数是\(\frac{1}{p}\)(参见这里)。然后,考虑一个状态\(dp[i]\)代表合成第\(i\)级武器的期望花费。显然\(dp[0] = a\)。

考虑\(dp[1]\)的求法,首先需要两个级别为\(0\)的武器,然后发现无论失败与否都可以保证至少又一个\(0\)级武器,所以我们只需要注意另外一个武器的花费就可以了:

\[ dp[1] = dp[0] + dp[1] \times \frac{1}{p} \]

继续阅读[Fortuna OJ]Aug 4th – Group A 解题报告

Codeforces Round #551 (Div. 2) 解题报告 (CF1153)

C – Serval and Parenthesis Sequence

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

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

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

继续阅读Codeforces Round #551 (Div. 2) 解题报告 (CF1153)

Educational DP Contest : J – Sushi 题解

主要思路

啊呀,我太菜了。

因为每盘的寿司数量最多为3,所以我们可以三个参数分别代表寿司数量为\(i\)的盘数。然后我们可以得出这样的方程:

\[ tot = A + B + C, dp(A,B,C) = \frac{n}{tot} + \frac{A}{tot}*dp(A-1,B,C) + \frac{B}{tot}*dp(A+1,B-1,C) + \frac{C}{tot}*dp(A,B+1,C-1) \]

因为没有固定的顺序进行 DP,所以我们进行记忆化搜索即可。

代码

// J.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 330;
int n, ai[MAX_N], sushi[4];
double dp[MAX_N][MAX_N][MAX_N];
double dfs(int a, int b, int c)
{
    if (a == 0 && b == 0 && c == 0)
        return 0;
    if (dp[a][b][c] >= 0)
        return dp[a][b][c];
    double d = a + b + c, ans = n / d;
    if (a)
        ans += dfs(a - 1, b, c) * a / d;
    if (b)
        ans += dfs(a + 1, b - 1, c) * b / d;
    if (c)
        ans += dfs(a, b + 1, c - 1) * c / d;
    return dp[a][b][c] = ans;
}
int main()
{
    memset(dp, -1, sizeof(dp));
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]), sushi[ai[i]]++;
    printf("%.10lf", dfs(sushi[1], sushi[2], sushi[3]));
    return 0;
}