P13794 [SWERC 2023] Metro quiz 题解

· · 题解

好耶我是这题目的第八个 AC！好前！qp！

额扯远了，来讲题吧。

题目就是说，给定 m 条地铁线路和 n 个地铁站以及每条地铁线路包含了哪些地铁站，然后有两个人 A 和 B。A 随机选择一条地铁线路并记住它的编号，然后 B 随机询问这条线路是否经过地铁站 i（显然 B 不会问重复的），A 会如实回答。问在纯随机的情况下 B 要猜出 A 所想的地铁线路编号所需的次数的期望，如果存在某种情况使得 B 无法猜出 A 所想的地铁线路编号那么输出 not possible。

首先考虑在哪种情况下会输出 not possible。显然，如果每个地铁站都问过的话，其实等同于是确定了的，但如果存在两条地铁线路经过的站点编号一模一样的话就可能猜不出来了，所以这个时候输出 not possible 就没毛病了。可以在输入后 O(m^2) 判断一下，如果存在的话输出并 return 0; 防止进入之后的操作。

那么接下来考虑定义 DP 状态。设 dp_{s,t} 表示当前问了 s 这些站点（用二进制压缩表示，如为 1 则表示问额，反过来为 0 则表示没问），并且回答为 t（同样用二进制压缩表示，为 1 表示包含，为 0 表示不包含）的情况下，还需要多少步才能猜出具体是哪条线路。

首先计算一下在这种情况下是不是已经可以确定了。具体的，定义 cnt 且初值为 0，然后枚举每条线路并判断其状态是否完全包含 t，如果完全包含的话，我们就让 cnt \to cnt + 1。判断一下，如果 cnt = 1 那么说明可以 100\% 确定了，这个时候用不着转移直接 dp_{s,t} = 0 就 OK 了。

但是如果 cnt>1 的话就需要考虑转移了。枚举接下来想要询问的位置 k，可以求出 s^{\prime} 和 t^{\prime} 表示 s 和 t 把这个 k 加入集合后的结果，那么转移式就一目了然了——

dp_{s,t} = \min( dp_{s,t} , cnt + dp_{s^{\prime},t} + dp_{s^{\prime} , t^{\prime}})

得出这个转移式之后咱就可以痛痛快快 DP 啦！

但是这题结束了吗？没有哦，因为会爆炸。先不管时间复杂度，单空间复杂度就已经 O(4^n) 了这接受不了啊！

必须优化。由于 t 在 s 为 0 的那些位上是无意义的，也就是说 t 肯定是 s 的子集。那么可以优化到 O(3^n) 的空间复杂度。但还是不行。

由于真正涉及转移的，即，cnt > 0 的 (s,t) 二元组并不多，只有当 t 的情况为某条线路的时候才会发生，那么 t 这一维度就可以大幅降低了，因为线路数量 m 最多也只有 50 条。

那么 dp_{s,t} 这个状态就稍微改变一下定义了——本来是问状态 s 答状态 t，现在是问状态 s 答线路编号 t。

最终答案就是 dp_{0,0} \div m，因为题目要求你计算的是期望嘛。

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define fr first
#define se second
#define pb push_back
using namespace std;
const int N = 20 , M = 55;
const int K = (1<<20) + 5;
int n,m,a[M],dp[K][M],flag[N];LD Ans;
int read(){
    int su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int t=read();
        while(t--)a[i]|=(1<<read());
    }for(int i=1;i<m;i++)for(int j=i+1;j<=m;j++)
        if(a[i]==a[j]){cout<<"not possible\n";return 0;}
    memset(dp,0x3f,sizeof(dp));
    for(int s=(1<<n+1)-1;s>=0;s--)for(int i=1;i<=m;i++){
        int cnt=0;for(int j=0;j<n;j++)flag[j]=0;
        for(int j=1;j<=m;j++)if((s&a[i])==(s&a[j])){cnt++;
            for(int k=0;k<n;k++)if((a[i]&(1<<k))!=(a[j]&(1<<k)))flag[k]=j;
        }if(cnt<=1){dp[s][i]=0;continue;}
        for(int j=0;j<n;j++)if(flag[j])
            dp[s][i]=min(dp[s][i],cnt+dp[s|(1<<j)][i]+dp[s|(1<<j)][flag[j]]);
    }
    Ans=1.00*dp[0][1]/m;printf("%.10Lf\n",Ans);
    return 0;
}

花絮，思路小诗。

如果自信能看懂我猎奇的表达方式可以选择先看下面这个神秘的东西。

dp[s][t] 表示问 s 答 t
t 可以用 1~m 中的数代表每个线路
毕竟真正有效的是正确线路的值
嗯对然后 "not possible" 的情况就
当且仅当存在两条线路经过的站点完全一样
这样就猜不出来了所以没可能
这个可以输入的时候特判一下
然后初始化 dp 值为 inf
接下来先枚举 s 和 i
但是记着 s 得倒着枚举才行
s 不用说就是所谓问
i 表示当前猜测到线路是 i
即问 s 后回复的是 i 线路对应的集合
弄一个临时的 flag 标记最开始先清空
然后再用 j 枚举每个线路
看看是否满足与 s 与 i 完美贴合
具体的判断是否满足 s&a[i]=s&a[j]
满足的话 cnt++
然后枚举每一位看是否重合
不重合就用 flag 记录下 j 等会更新要用
出来后先判断 cnt 是否 <=1
是的的话不用转移直接 dp[s][i]=0
否则枚举每一位 j
然后判断 flag[j] 有没有值有就转移
具体的话转移式长这样
dp[s][i]=cnt+dp[s|(1<<j)][i]+dp[s|(1<<j)][flag[j]]
有点长但是记得取 min 哦不然白费功夫
最后直接输出 dp[0][1] 就好啦
显然还要换成小数并除以 m 哟
然后本题就结束啦是不是很简单哒