牛客多校5

B題：

我們隻需要比較 詢問後的數學期望和全部打開盒子的花費輸出最小值就好

因為黑球和白球是等價的，是以有i個黑球和有i個白球的可能性相同

當我們不需要開盒子時：

全為黑（白）球，2/(2 ^ n) = 2^(n-1)

開一個就可以停下來的機率：隻有一個黑（白）球，而且第一次就被我們開到了(1代表黑球，0代表白球）

10000…

01111…

2/(2 ^ n)=2^(1-n)

開兩個停下來的機率2^2/(2 ^ n)

01000…(1個黑）

110000…（2個黑

10111…（1白

0011111…（2白

開三個的機率2^3/(2 ^ n)

00100000…（1黑

10100000…（2黑

01100000…（2黑

11100000…（3黑

…

我們發現了一個規律，而且每一次的情況枚舉就是如果預言有k個黑球，第k個球一定是在我們開的最後一個箱子取到，而前面可以任意取 是以開黑球 在第i個位置開球後停止的機率為2^(i-1)/(2 ^ n)

白球同理 是以是2^(i-1)*2/(2 ^ n)= 2 ^(i-n)=(1/2) ^ (n-i)這個代表的是第i個位置開哦

#include<bits/stdc++.h>
#define ll long long
#define speed(x) ios::sync_with_stdio(false), cin.tie(x), cout.tie(x)
#define bug(x) cout << #x << " == " << x << '\n';
const ll int MAX_N = 2e5 + 100;
using namespace std;
double cost[MAX_N] = { 0 };
double sum[MAX_N] = { 0 };
int main()
{
    int n;
    double c;
    cin>>n>>c;
    for(int i=1;i<=n;i++)
    {
        scanf("%lf",&cost[i]);
    }
    sort(cost+1,cost+1+n);///肯定是先開便宜箱子啦
    for(int i=1;i<=n;i++)
    {
        sum[i]=cost[i]+sum[i-1];
    }
    double ans = c;
    for(int i=1;i<n;i++)
    {
        ans+=sum[i]*pow(0.5,n-i);
        ///bug(pow(0.5,n-i));
    }
   printf("%.8lf\n",min(ans,sum[n]));
}

           

D題：

題目大意:就是找了兩個等長的子序列字元串 aa,bb

aa<bb

一個字元串大于另一個字元串

兩種情況：首字母a[1]<b[1]

前面幾個字母都相同：然後第i個字母a[i]<b[i]

是以我們隻需要比較每一個字母

a[i]<b[j]的時候

www為計算 a[1~i-1]和b[1-j-1]有多少相等子序列（通過dp求）

ans為a[i+1 ~ a.length()]與b[j+1 ~b.length()]可以組合出多少相同長度子序列

設n=a.length( )-(i+1),m=b.length()-(j+1);

就是C(0,n)*C(0,m)+C(1,n)*C(1,m)+…+C(min(n,m),n)*C((min(n,m),m).

第一種辦法：不妨設n<=m

x從0到n—> C(x,n)*C(x,m)=C(n-x,n)*C(x,m)=C(n,n+m)

通過逆元求組合數就好

第二種辦法：（dp yyds,感謝WWWW同學的好辦法）

我們之前通過dp計算兩個字元串有多少相同子序列

而求n長度的字元串和m長度的字元串可以有多少相同長度的子序列 我們可以想象成後面的字母都是相同的 可以任意取 也可以通過dp來求出

現在：解釋dp[i][j]代表了字元串a的前i個字母的子字元串aa和字元串b的前j個字母的子字元串bb的相同子序列個數

dp[ 0 ][ j ] 相當于aa取得子字元串為空，當bb也為空的時候相同，是以是1，dp[ i ][0]同理！

①sum1=dp[i][j-1]-dp[i-1][j-1]代表了相同子序列中 aa的子序列一定取a[i]和bb的相同子序列的個數

②同理:sum2=dp[i-1][j]-dp[i-1][j-1]代表了相同子序列中 bb的子序列一定取b[j]和aa的相同子序列的個數

③sum3=dp[i-1][j-1]代表了a[i]和b[j]都不取的相同子序列個數

當a[i]!=b[j] dp[i][j]=sum1+sum2+sum3;

當a[i]==b[j] 還可以加上一個sum4代表了 a[i],b[j]都取得相同子序列個數 就是sum3中的每一對相同子序列都在末尾分别加上a[i]，b[j],是以sum4 = sum3;

#include<bits/stdc++.h>
#define ll long long
#define speed(x) ios::sync_with_stdio(false), cin.tie(x), cout.tie(x)
#define bug(x) cout << #x << " == " << x << '\n';
const ll int MAX_N = 5e3 + 100;
using namespace std;
ll mod=1e9+7;
ll jc[3*MAX_N] = { 0 };
ll njc[3*MAX_N] = { 0 };
int dp[MAX_N][MAX_N] = { 0 };
ll ccc(int n,int m)
{
    return jc[n+m]*njc[m]%mod*njc[n]%mod;
}
ll epow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1)ans *= a;
        a *= a;
        a %= mod;
        ans %= mod;
        b >>= 1;
    }
    return ans;
}
int main()
{
    string a,b;
    cin>>a>>b;
    int len1=a.length();
    int len2=b.length();
    a = ' ' + a;
    b = ' ' + b;
    jc[0] = 1;
    for(int i=1;i<=2*MAX_N;i++)
    {
        jc[i] = (ll)i*jc[i-1];
        jc[i] %= mod;
    }
    njc[2*MAX_N-1]=epow(jc[2*MAX_N-1],mod-2)%mod;
    for(int i=2*MAX_N-1;i>=1;i--)
    {
        njc[i-1]=njc[i]*(ll)i%mod;
    }
    ll sum=0;
    for(int i=0;i<=len1;i++)dp[i][0]=1;
    for(int j=1;j<=len2;j++)dp[0][j]=1;
    for(int i=1;i<=len1;i++)
    {
        for(int j=1;j<=len2;j++)
        {
            if(a[i]!=b[j])
            {
                dp[i][j]=(dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+mod)%mod;
            }
            else
            {
                 dp[i][j]=(dp[i-1][j]+dp[i][j-1]+mod)%mod;
            }
        }
    }
    for(int i=1; i<=len1; i++)
    {
        for(int j=1; j<=len2; j++)
        {
            if(a[i]<b[j])
            {
                ll ans=ccc(len1-i,len2-j)%mod;
                ll www = dp[i-1][j-1]%mod;
                sum+=www*ans%mod;
                sum%=mod;
            }
        }
    }
    printf("%lld\n",sum%mod);
}