[补档]noip2019集训测试赛（十二）

浅浅的花香味﹌ 2023-08-17 16:58 24阅读 0赞

## Problem A: 记忆（memory） ##

#### Time Limit: 1000 ms Memory Limit: 512 MB ####

### Description ###

你在跟朋友玩一个记忆游戏。

朋友首先给你看了n个长度相同的串，然后从中等概率随机选择了一个串。

每一轮你可以询问一个位置上的正确字符，如果能够凭借已有的信息确定出朋友所选的串，那么游戏就结束了，你的成绩就是所用的轮数。

由于你实在太笨，不会任何策略，因此你采用一种方法，每次等概率随机询问一个未询问过的位置的字符。

现在你想知道，在这种情况下，你猜出结果所需的期望次数。

### Input ###

第1行包含一个整数 n，表示串的个数。

第 2 ~ n+1行每行包含一个长度相等的字符串，仅包含小写字母和大写字母。

### Output ###

输出1行一个小数，表示猜出结果所需的期望次数，保留10位小数。

Sample Input
    
    3
    aaA
    aBa
    Caa
    
    Sample Output
    
    1.6666666667

### HINT ###

设串长为l

对于20%的数据， n，l≤10

对于30%的数据， n，l≤15

对于60%的数据， n，l≤20

对于100%的数据， n≤50，l≤20

## Solution ##

期望DP

考虑状压，a\[i\]\[j\]表示在第i位上为字符j的个数，这个个数用一个二进制状态表示，第k位是1即表示k串第i位是字符j。

设b\[i\]\[j\]代表在询问状态为j且答案为i的情况下，还有b\[i\]\[j\]个字符串满足要求，同样以二进制状态储存。

设num\[i\]，表示在询问状态为i的情况下，有num\[i\]个满足条件的字符串。

设i代表答案为第i个字符串，j代表当前询问状态，不难得到转移方程：

\$设k=j \\bigoplus lowbit(j),pos为lowbit的位置\$

$ b\[i\]\[j\] = b\[i\]\[k\]　and　a\[pos\]\[s\[i\]\[pos\]\] $

\$num\[j\]+=\[b\[i\]\[j\]!=lowbit(b\[i\]\[j\])\]\$

第二条含义：如果pos位置上等于s\[i\]\[pos\]的字符串同时也满足询问k的条件，显然它在询问j状态下也是满足的

第三条含义：如果有不确定的情况，那么num\[j\]++

接下来我们用cnt\[i\]表示二进制下i的1的个数，f\[i\]表示转移到状态i的概率

设\$tmp=f\[i \\bigoplus (1<<j)\]/(m-cnt\[i \\bigoplus (1<<j)\])\$，这代表了从\$i \\bigoplus (1<<j)\$转移到i的概率（即1/上一状态的0的个数）

所以有\$f\[i\]+=tmp\$

接下来，我们有\$ans+=cnt\[i\]\*(tmp\*(num\[i \\bigoplus (1<<j)\]-num\[i\]))\$，这是什么意思呢？

首先cnt\[i\]是转移到i状态的操作个数（就是1的个数）

后面的tmp乘上的那一坨玩意儿就意味着你可以从\$num\[i \\bigoplus (1<<j)\]-num\[i\]\$这些从不确定转为确定状态的串中任意一个进行转移

于是最后统计出来的ans就是所有串被猜中的期望操作次数总和

除以n就是最后答案了

#include<bits/stdc++.h>
    using namespace std;
    int n,m,M;
    const int N=1<<20;
    int num[N],cnt[N],s[50][20];
    long long a[50][52],b[50][N];
    long double f[N],ans;
    char str[20];
    int main(){
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%s",str);
            m=strlen(str),M=1<<m;
            for(int j=0;j<m;j++){
                s[i][j]=('a'<=str[j]&&str[j]<='z')?str[j]-'a':str[j]-'A'+26;
                a[j][s[i][j]]|=(1ll<<i);
            }
        }
        num[0]=n;
        for(int i=0;i<n;i++){
            b[i][0]=(1LL<<n)-1LL;
            for(int j=1;j<M;j++){
                int k=j^(j&-j);
                int pos=__builtin_ctz(j);
                b[i][j]=b[i][k]&a[pos][s[i][pos]];
                if(b[i][j]!=(b[i][j]&-b[i][j])) num[j]++;
            } 
        }
        for(int i=1;i<M;i++)
        cnt[i]=cnt[i>>1]+(i&1);
        f[0]=1;
        for(int i=1;i<M;i++)
        for(int j=0;j<m;j++)
        if((i>>j)&1){
            long double tmp=f[i^(1<<j)]/(m-cnt[i^(1<<j)]); 
            ans+=cnt[i]*(tmp*(num[i^(1<<j)]-num[i]));
            f[i]+=tmp;
        }
        printf("%.10Lf",ans/n);
    }

## Problem B: 神经元（neuron） ##

#### Time Limit: 1000 ms Memory Limit: 512 MB ####

### Description ###

你培育出了一些新型的神经元，它们可以有很多的轴突。

具体来说，对于第i个神经元，它有1~di条轴突，因此可以与1~di个神经元相连，可以将轴突看成无向图的边，假定每个神经元都是不同的。

现在你想知道，有多少种方案使得其中恰好k个神经元相连通，这里的连通需要保证任意两个神经元间有且仅有一条路径，方案数可能很大，你只需要对10^9+7取模输出。

两个方案是不同的当且仅当选择的神经元集合不同或其中有至少一条轴突（u，v）出现在一个方案但不出现在另一个方案。

### Input ###

第1行包含一个整数n，表示神经元的个数。

第2行包含n个整数di，表示第i个神经元最多的轴突数量（1<=di<n）。

### Output ###

输出1行，包含n个整数，第i个整数表示其中恰好有i个神经元连通的方案数模 10^9+7后的值。

Sample Input
    
    3
    2 2 1 
    
    Sample Output
    
    3 3 2

### HINT ###

对于10%的数据，n<=8

对于另外10%的数据，di=n-1

对于20%的数据，n<=15

对于30%的数据，n<=20

对于40%的数据，n<=50

对于60%的数据，n<=70

对于100%的数据，n<=100

## Solution ##

不知道哪儿来那么多部分分

prufer序列上的dp

prufer序列：无根树所对应的一种序列，任何一种无根树形态都对应着一个prufer序列，没有重复者。一棵无根树的长度是点数-2。可以百度了解一下。

设dp\[i\]\[j\]\[k\]表示前i个点，选择了j个点来构成这棵树，prufer长度为k的情况（显然出现环时prufer序列就不会是n-2那么长了）

分两类讨论：

1、不选这个点 \$dp\[i+1\]\[j\]\[k\]+=dp\[i\]\[j\]\[k\]\$

2、选择这个点 我们枚举这个点伸出来的边数l

可以得到\$dp\[i+1\]\[j+1\]\[k+l\]+=dp\[i\]\[j\]\[k\]\*C\[k+l\]\[l\]\$，其中C数组代表组合

即他可以选择在k+l长度的prufer序列中，任意选择l个位置让自己出现（因为每一种prufer序列都对应着不同的树的形态，所以显然prufer序列种数就是树构成的方案树）

最后输出的就是dp\[n\]\[i\]\[i-2\]了。

#include<bits/stdc++.h>
    using namespace std;
    #define int long long
    #define mod (int)(1e9+7)
    int C[201][201];
    void pre(){
        for(int i=0;i<=200;++i){
            C[i][0]=1;
            for(int j=1;j<=i;++j){
                C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
            }
        }
    }
    int a[201];
    int dp[201][201][201];
    signed main(){
        pre();
        int n;
        scanf("%lld",&n);
        for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
        dp[0][0][0]=1;
        for(int i=0;i<n;++i){
            for(int j=0;j<=i;++j){
                for(int k=0;k<=n-2;++k){
                    if(!dp[i][j][k])continue;
                    dp[i+1][j][k]=(dp[i+1][j][k]+dp[i][j][k])%mod;
                    for(int l=0;l<a[i+1]&&k+l<=n-2;++l){
                        dp[i+1][j+1][k+l]=(dp[i+1][j+1][k+l]+dp[i][j][k]*C[k+l][l])%mod;
                    }
                }
            }
        }
        printf("%lld ",n);
        for(int i=2;i<=n;++i){
            printf("%lld ",dp[n][i][i-2]);
        }
    }

转载于:https://www.cnblogs.com/youddjxd/p/11434297.html