2022 上海市赛SHCPC I题

2023/11/23 算法竞赛 C++ 2022 上海市赛 记忆化搜索 期望dp

一道期望dp的题，推了好久的式子一直算不清楚，最后发现是我对排列数的理解有偏差😥

题面

题目大意： 初始情况为只有n个点的无向图，每一次随机两个点(可能相同)，如果这两个点连上边之后满足下列条件就连边，不然图不变。条件： - 无重边自环 - 每个点的度数小于等于2

不能继续操作就终止，求终止的期望步数

思路

  • 可以看出是有重叠的子问题的，在某种情况下开始的期望步数是定的，可以想到用dp
  • 每个点的度数小于等于2，那么2度点不能继续连边，0度点不和2度点连边，1度点有一点特殊。考虑1度点的连边情况，有可能1度点和1度点连，这个时候形成长度为2的链，另一种情况是1度点2度点连边，可以发现这两种情况需要分别分析。所以状态比较明显了： dp[i][j][k] 表示当前有 i 个0度点， j 个1度点，这 j 个1度点中有 k 条长为2的链，所需要达到终止条件的期望步数
  • 状态转移：
  1. 0度和0度： i * (i−1)
  2. 0度和1度(不在长为2的链上)： i * (j−2*k) * 2 //一开始没乘后面的2怎么算也算不对🤡
  3. 0度和1度(在长为2的链上)： i * 2 * k * 2
  4. 1度(不在长为2的链上)和1度(不在长为2的链上)： (j−2*k) * (j−2*k−1)
  5. 1度(不在长为2的链上)和1度(在长为2的链上)： (j−2*k) * 2 * k * 2
  6. 1度(在长为2的链上)和1度(在长为2的链上)： 2 * k * (2*k−2)

这是所有合法转移，用记忆化搜索的方式写很方便

最终状态 dp[0][0][0] = 0

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=205;
double dp[N][N][N];
bool vis[N][N][N];
int n;
double dfs(int i,int j,int k){
    if(i<0||j<0||k<0||i+j>n)
        return 0;
    if(vis[i][j][k])
        return dp[i][j][k];
    double ans=0;
    int sz=i*(i-1)+i*(j-2*k)*2+i*2*k*2+(j-2*k)*(j-2*k-1)+(j-2*k)*2*k*2+2*k*(2*k-2);
    if(sz!=0)
        ans+=(dfs(i,j-2,k)*(j-2*k)*(j-2*k-1)+dfs(i,j-2,k-1)*(j-2*k)*2*k*2+dfs(i,j-2,k-2)*2*k*(2*k-2)\
        +dfs(i-2,j+2,k+1)*i*(i-1)+dfs(i-1,j,k)*i*(j-2*k)*2+dfs(i-1,j,k-1)*i*2*k*2+n*n)/(sz);
    vis[i][j][k]=true;
    return dp[i][j][k]=ans;
}
signed main() {
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n;
    vis[0][0][0]=true;
    dp[0][0][0]=0;
    double ans=dfs(n,0,0);
    printf("%.9lf\n",ans);
    return 0;
}

另一种状态的设计方法

设 dp[i][j][k] 为现在有 i 个0度点， j 条长为2的链， k 条长大于2的链，要达到最终状态所需要的期望步数

状态转移
  • 0度和0度： i * (i−1)
  • 0度和短链： i * 2 * j * 2
  • 0度和长链： i * 2 * k * 2
  • 短链和短链： 2 * j * (2*j−2)
  • 短链和长链： 2 * j * 2 * k * 2
  • 长链和长链(成环)： 2 * k
  • 长链和长链(成链)： 2 * k * (2*k−2)

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=205;
double dp[N][N][N];
bool vis[N][N][N];
int n;
double dfs(int i,int j,int k){
    if(i<0||j<0||k<0||i+2*j+3*k>n||(k==0&&i+j<=1))
        return 0;
    if(vis[i][j][k])
        return dp[i][j][k];
    int sz=i*(i-1)+i*2*j*2+i*2*k*2+2*j*(2*j-2)+2*j*2*k*2+2*k+2*k*(2*k-2);
    dp[i][j][k]=(dfs(i-2,j+1,k)*i*(i-1)+dfs(i-1,j-1,k+1)*i*2*j*2+dfs(i-1,j,k)*i*2*k*2+\
    dfs(i,j-2,k+1)*2*j*(2*j-2)+dfs(i,j-1,k)*2*j*2*k*2+dfs(i,j,k-1)*2*k+\
    dfs(i,j,k-1)*2*k*(2*k-2)+n*n)/sz;
    vis[i][j][k]=true;
    return dp[i][j][k];
}
signed main() {
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n;
    vis[0][0][0]=true;
    dp[0][0][0]=0;
    double ans=dfs(n,0,0);
    printf("%.9lf\n",ans);
    return 0;
}
img_show