B

题意：N个装有黑白球的盒子(每个盒子一定有且只有一个球),你需要知道所有盒子里面都是什么球，为此你需要开盒子，打开第i个盒子需要花费 $w_{i}$ 的代价,同时你可以花费C的代价先知道里面有多少个黑球，现在问你期望花费。
思路：只有两种策略
第一种，直接全开了 $求和公式$
第二种，先知道有多少个黑球(同时你也知道有多少白球了)，然后对花费进行排序，从小到大开，能不再开后面盒的情况有且只有两种未开盒子数目等于目前剩余黑球数目或者未开盒子数目等于目前剩余白球数目。而这个概率恰为 $图片说明$ (m 为未开数量)。
设当前准备开第i个盒子（m=n-i+1)化简得到 $1/2^{n-i}$ 。
为了简便运算，i从n开始枚举。
输出这两种情况的最小值就好。

//author: TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll maxn=1e5+7;
using namespace std;
int _,n,m;
double w[maxn];
double c;
double yi=1;
double tot;
int main()
{
    cin>>n;
    cin>>c; 
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
        tot+=w[i];
    }
    sort(w+1,w+1+n);
    // n-i+1 
    for(int i=n;i>=1;i--)
    {
        c+=w[i]*(1-yi);//在知道黑白球数量的情况下，什么人会开最后一个盒？ 
        yi/=2;
    }
    printf("%0.7lf\n",min(tot,c));
     return 0;
}

D

题意：给定字符串A，B,从A,B中取各取一个子序列记为a,b。问有多少对子序列满足如下三个条件：
1，长度相等
2，字典序: a < b 相同前缀+一个不一样的字符+任意长度相等的后缀
思路：看条件2知道这道题可以枚举这个不一样的字符，然后计算前缀与后缀的数量的乘积即可。
我们先讲后缀，设|A|=la，|B|=lb,若 $A_{i}<B_{j}$ 则，后缀的数量是 $图片说明$ ,这里要是看的麻烦，可以把la-i 和 lb - j换成n和m ，同时假设n<=m。由组合数性质知道上面的公式恰好等于 $图片说明$ 。
组合数的计算，先进行逆元的预处理(板子不错，我收下了)。
至于前缀，我们可以用dp[i][j]表示A中1到i 和 B中1到j 的公共子序列个数。转移方法是：
在不考虑A[i]和B[j]的时候，dp[i][j]=dp[i-1][j]+dp[i][j-1],但是dp[i-1][j-1]在dp[i-1][j]和dp[i][j-1]都已经被加进去了，所以需要减去一个它，故所以dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]。又考虑上A[i]和B[j]，当他们相等的时候，我们在额外加上dp[i-1][j-1]，同时由于这里相等，所以dp[i][j]需要加一。
对于每个A[i]<B[j],它们能产生的满足题意的子序列数量就是(1+dp[i-1][j-1])*C(la-i+lb-j-2,la-i-1)有关这个式子的细节看代码。

//author: TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1e9+7;
const ll maxn=5000+7;
using namespace std;
int _,n,m,la,lb;
string a,b;
int dp[maxn][maxn]; //dp[i][j]表示 A 1到i 和 B 1到j 的子序列个数 
ll ans;
int Fac[maxn*2],Inv[maxn*2];

void Prepare(int n)
{
    Fac[0] = 1;
    for (int i = 1; i <= n; i ++)
        Fac[i] = 1ll * Fac[i - 1] * i % mod;
    Inv[0] = Inv[1] = 1;
    for (int i = 2; i <= n; i ++)
        Inv[i] = mod - 1ll * (mod / i) * Inv[mod % i] % mod;
    for (int i = 2; i <= n; i ++)
        Inv[i] = 1ll * Inv[i - 1] * Inv[i] % mod;
}

inline int C(int u, int v)
{
    if (u < 0 || v < 0 || u < v)
        return 0;
    return 1ll * Fac[u] * Inv[v] % mod * Inv[u - v] % mod;
}
int main()
{
    ios::sync_with_stdio(false);

    cin>>a>>b;
    a=" "+a;
    b=" "+b;
    la=n=a.length();
    lb=m=b.length();
    Prepare(5002*2);
    for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
      if (a[i] == b[j]) {
        dp[i][j] += dp[i - 1][j - 1] + 1;
      }
//存在减法，可能会出现负数。
      if (dp[i][j] < 0) {
        dp[i][j] += mod;
      }
      if (dp[i][j] >= mod) {
        dp[i][j] %= mod;
      }
    }
  }
    ans=0;
    for(int i=1;i<=la;i++)
    {
        for(int j=1;j<=lb;j++)
        {
            if(a[i]<b[j])
            {
                //C 里面减1是因为我们的长度比实际长度大1，就是最前面的空格 
                //减2同理 
                ans+=1ll*(1+dp[i-1][j-1])*C(la-i+lb-j-2,la-i-1);
                if(ans>=mod)
                {
                    ans%=mod;
                }
            }
        }
    }
    cout<<ans<<endl;
     return 0;
}

K

题意：给定一个序列，问有多少个区间使得极差大于K。
思路：令 $图片说明$ 表示当l=i的时候，极差大于K的最小r。可以证明 $图片说明$ ,这个很容易证明，如果我有读者并且正好不能理解这里的话。可以分别假设a[i+1]>=a[i] 和a[i+1]<a[i]，去模拟一下就明白了。这么一来问题就变成了单调队列的问题了。

//author: TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll maxn=1e5+7;
using namespace std; 
//https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48370676
ll _,n,m,k;
ll a[maxn];
ll ans=0;
int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    //freopen("7.in","r",stdin);
    //freopen("mine.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    while(m--)
    {
        cin>>k;
        ans=0;//这个是不满足条件的数量
        // mx 是递减序列， 队首最大
        // mi 是递增序列， 队首最小 
        deque<int > mx,mi; // 维护区间[l, i]的最大值最小值，按顺序入队
        int l=1;
        for(int i=1;i<=n;i++)
        {
            while(mx.size() && a[ mx.back() ]<a[i]  )
                mx.pop_back();
            mx.push_back(i);
            while(mi.size() && a[ mi.back() ]>a[i]  )
                mi.pop_back();
            mi.push_back(i);
            while(mx.size()&&mi.size() && a[mx.front()] - a[ mi.front()] > k ) 
            {
                // mi, mx 中 最前端一定至少有一个是L
                //由于是递增/递减的，内部所有元素的并集一定恰好是l , l+1 …… i 
                // 弹掉当前位l 
                if(mi.front()==l)
                {
                    mi.pop_front();
                }
                if(mx.front()==l)
                {
                    mx.pop_front();
                }
                l++;
            }    
            //这里 k==0 的时候，l会比i大。 又不能加负数，所以补一 
            //a[l ... i]是满足不了极差大于K的
            ans+=i-l+1;//如果a[l ... i]满足条件，其(i - l + 1)个子数组都满足条件
        }    
        cout<<(n*(n+1)/2)-ans<<endl;
    } 
     return 0;
}

Kur1su,我的超人！

2021牛客暑期多校训练营5

B

D

K