B.Boxes

题意
给你 $n$ 个装有白球或者黑球的盒子，其中盒子里是白球的概率为 $\frac{1}{2}$ 。打开第 $i$ 个盒子的代价是 $w_i$ ，在你没有打开盒子之前你无法知道盒子中的球的颜色。而你最多有一次机会可以使用 $C$ 代价来知道剩余的盒子里面还有多少黑球。问你最小成本的数学期望是多少？
解题思路
我们如果不使用 $C$ ，我们无法知道盒子中黑球白球的分布，那么只能打开所有的盒子，代价为 $\sum w_i$ 。那么如果我们使用了 $C$ ，我们就可以预知我们要开多少个黑球盒子，这样就相当于 $01$ 序列贪心开即可。
AC代码

/**
  *@filename:B
  *@author: pursuit
  *@created: 2021-08-06 10:14
**/
#include <bits/stdc++.h>
#define debug(a) cout << "debug : " << (#a)<< " = " << a << endl;

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 1e5 + 10;
const int P = 1e9 + 7;
const int INF = 0x3f3f3f3f;

double ans,sum;
int n;
double c,w[N];
void solve(){
    sort(w + 1, w + 1 + n);
    double f = 1.0;
    for(int i = n; i; -- i){
        ans += (1.0 - f) * w[i];
        f /= 2;
    }
    //要么全开。要么在最开始花一次，然后相当于一个01序列一样开过去即可。
    printf("%.8lf\n", min(sum,c + ans));
}
int main(){	
    scanf("%d%lf", &n, &c);
    for(int i = 1; i <= n; ++ i){
        scanf("%lf", &w[i]);
        sum += w[i];
    }
    solve();
    return 0;
}

D.Double Strings

题意
题意有点绕，多读几遍即可。大意就是求解一段相同的前缀 + 一个不同的字符（且该字符需要比第二个小） + 任意长度的后缀的子字符串数量。
解题思路
对于求解一段相同的前缀，这个我想大家应该清楚，即是求公共子序列的原型，那么组合出来的即是相同前缀，而一个不同的字符，这个我们可以看作是分割点，因为知道了这个，对于任意长度的后缀计算就是任意选择了，即组合数学。
1. A,B两个字符串所具有的相同的前缀的个数。 $d p [i] [0] = d p [0] [j] = 1$ ; $d p [i] [j] = d p [i ? 1] [j] + d p [i] [j ? 1] ? d p [i ? 1] [j ? 1]$ ;减去 $d p [i ? 1] [j ? 1]$ 是因为多计算了一次。 $i f (a [i] = = b [j]) d p [i] [j] + = d p [i ? 1] [j ? 1];$
2. 对于 $a_i<b_j$ ，我们可以把它看作分割点，即出现了一次就计算一次。
3. 任意长度相同的后缀的个数。对于剩余长度x，y。不妨令x <= y。 $\sum_{i=0}^{x}C_{x}^i\times C_{y}^i=\sum_{i=0}^{x}C_{x}^{x-i}\times C_{y}^i=C_{x+y}^x$ 。则取任意后缀的方案数为： $C_x^{x+y}$ ;这个由于要取模，我们需要通过逆元来实现。
AC代码

/**
  *@filename:D
  *@author: pursuit
  *@created: 2021-08-06 16:53
**/
#include <bits/stdc++.h>
#define debug(a) cout << "debug : " << (#a)<< " = " << a << endl;

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 5e3 + 10;
const int P = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int fac[N << 1],inv[N << 1];
//求解一段相同的前缀 + 一个不同的字符（且该字符需要比第二个小） + 任意长度的后缀
int dp[N][N];//dp[i][j]表示第一个字符串前i个位置和第二个字符串前j个位置所具有的相同的子序列。
char a[N],b[N];
int qsm(int n,int q){
    int ans = 1;
    while(q){
        if(q & 1)ans = 1LL * ans * n % P;
        n = 1LL * n * n % P;
        q >>= 1;
    }
    return ans;
}
void init(){
    fac[0] = fac[1] = 1;
    for(int i = 2; i < N * 2; ++ i){
        fac[i] = 1LL * fac[i - 1] * i % P;
    }
    inv[N * 2 - 1] = qsm(fac[N * 2 - 1],P - 2);
    for(int i = N * 2 - 2; i >= 0; -- i){
        inv[i] = 1LL * inv[i + 1] * (i + 1) % P;
    }
}
int C(int n,int m){
    return 1LL * fac[n] * inv[m] % P * inv[n - m] % P;
}
void solve(){
    int n = strlen(a + 1), m = strlen(b + 1);
    for(int i = 0; i <= n; ++ i)dp[i][0] = 1;
    for(int j = 0; j <= m; ++ j)dp[0][j] = 1;
    int ans = 0;
    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= m; ++ j){
            //不考虑a[i]和b[j]关系的状态转移，此时由于前i-1，前j个和前i，前j-1个都包含了i-1，j-1，故需要减去。
            dp[i][j] = ((dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]) % P + P) % P;
            if(a[i] == b[j])dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % P;
            else if(a[i] < b[j]){
                //说明我们找到了分割点。
                ans = (ans + 1LL * dp[i - 1][j - 1] * C(n - i + m - j, n - i) % P) % P;
            }
        }
    }
    printf("%d\n", (ans + P) % P);
}
int main(){	
    init();
    scanf("%s%s", a + 1, b + 1);
    solve();
    return 0;
}

H.Holding Two

题意
需要你构造一个矩阵，使得不存在 $3$ 个独立的点 $a_{i_1j_1},a_{i_2j_2},a_{i_3j_3}$ 满足 $a_{i_1j_1}=a_{i_2j_2}=a_{i_3j_3}$ ， $|i_1-i_2|\leq 1,|i_2-i_3|\leq 1,|j_1-j_2|\leq 1,|j_2-j_3|\leq 1$ 。
解题思路
构造可得
$001100...\\110011...\\001100..\\...$
这种方案一定可行。
AC代码

/**
  *@filename:H
  *@author: pursuit
  *@csdn:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-07-31 12:04
**/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 1000 + 5;
const int P = 1e9+7;

int n,m;
void solve(){
    for(int i = 1; i <= n; ++ i){
        int op;
        if(i & 1)op = 1;
        else op = 0;
        for(int j = 1; j <= m; ++ j){
            cout << char(op + '0');
            if(j % 2 == 0){
                op ^= 1;
            }
        }
        cout << endl;
    }
}
int main(){
    cin >> n >> m;
    solve();
    return 0;
}

J.Jewels

题意
有 $n$ 颗宝石，其坐标为 $x_i,y_i,z_i)$ ，同时有一个参数 $v_i$ 。你的位置在 $(0, 0, 0)$ ，当你需要取宝石 $i$ 时，设当前时刻为 $t$ ，那么代价为 $x_i^2+y_i^2+(z_i+tv_i)^2$ 。求取完所有宝石的代价，时刻从 $0$ 开始，一刻只能取一个宝石。
解题思路
我们知道，宝石一定会在 $n ? 1$ 时刻内取完，即每个时刻对应一颗宝石，所以我们可以将宝石和时刻看成是二部图，其权值则为对应时刻的代价，那么实际上我们需要求的就是最小权匹配。直接使用 $K M$ 算法。注：网上好多假的 $K M$ 算法，即超时代码，连 $k b$ 模板的也超时了，还好现场学习了一波别人的玄学KM算法。
AC代码

/**
  *@filename:J
  *@author: pursuit
  *@created: 2021-08-06 14:54
**/
#include <bits/stdc++.h>
#define debug(a) cout << "debug : " << (#a)<< " = " << a << endl;

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 300 + 10;
const int P = 1e9 + 7;
const ll INF = 1e16;

ll g[N][N],lx[N],ly[N];//二部图，x部是宝石，y部是时刻,其中lx和ly分别为x和y的顶标。
int n,linker[N];//linker数组表示y部的配对状态。
bool visX[N],visY[N];//访问标记，是否在交错树上。
ll slack[N];
int last[N];//上一个点。
void bfs(int x){
    //x部的点。
    int y = 0,y1;//y记录交错树中最后加入的Y点。y1直接记录最小值对应的y点。
    for(int i = 1; i <= n; ++ i){
        last[i] = 0,slack[i] = INF;
    }
    linker[y] = x;
    do{
        int i = linker[y];
        ll d = INF;
        visY[y] = true;
        for(int j = 1; j <= n; ++ j){
            if(!visY[j]){
                //不在交错树上的Y点。
                if(slack[j] > lx[i] + ly[j] - g[i][j]){
                    slack[j] = lx[i] + ly[j] - g[i][j];
                    last[j] = y;//y是最新加入交错树中的点。
                }
                if(slack[j] < d){
                    d = slack[j];
                    y1 = j;
                }
            }
        }
        for(int j = 0; j <= n; ++ j){
            if(visY[j]){
                //交错树上的点。
                lx[linker[j]] -= d,ly[j] += d;
            }
            else{
                slack[j] -= d;
            }
        }
        y = y1;//更新y。
    }while(linker[y]);//如果y没有匹配则找到了增广路。
    while(y) linker[y] = linker[last[y]],y = last[y];//增广路取反。
}
ll KM(){
    for(int i = 0; i <= n; ++ i){
        linker[i] = lx[i] = ly[i] = 0;
    }
    for(int i = 1; i <= n; ++ i){
        //对每个点求一次匹配。
        for(int j = 0; j <= n; ++ j)visY[j] = false;//重新建立增广路。
        bfs(i);
    }
    ll ans = 0;
    for(int j = 1; j <= n; ++ j){
        if(linker[j])ans += g[linker[j]][j];
    }
    return ans;
}
void solve(){
    printf("%lld\n", -KM());
}
int main(){	
    scanf("%d", &n);
    int x,y,z,v;
    for(int i = 1; i <= n; ++ i){
        //i代表宝石
        scanf("%d%d%d%d", &x, &y, &z, &v);
        for(int j = 0; j < n; ++ j){
            //y代表时刻。
            g[i][j + 1] = -(x * x + y * y + 1LL * (z + j * v) * (z + j * v));
        }
    }
    solve();
    return 0;
}

K.King of Range

题意
给你一个序列 $a$ ，有 $m$ 次询问，每次询问给出一个 $k$ ，需要你计算有多少区间 $[l, r]$ 满足其中区间的 $m a x ? m i n > k$ 。
解题思路
首先，我们需要知道，如果我们找到一个右端点为满足极差大于 $k$ 的最小的 $r$ ，那么说明有 $r$ 个区间是符合的，我们可以利用两个单调队列来维护最大值和最小值，这样就可以得到极差了，然后每次弹出队列元素知道极差小于等于 $k$ ,这样即可求解出 $r$ 了。
AC代码

/**
  *@filename:K
  *@author: pursuit
  *@csdn:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-07-31 12:40
**/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 100000 + 5;
const int P = 1e9+7;

int n,m,k,a[N];
int q1[N],q2[N];//维护一个递增队列和一个递减队列。
int s1,e1,s2,e2;
ll ans;
void solve(){
    while(m -- ){
        scanf("%d", &k);
        ans = 0;
        s1 = s2 = 1,e1 = e2 = 0;
        int r = 0;
        for(int i = 1; i <= n; ++ i){
            //维护单调递增和单调递减队列。
            while(s1 <= e1 && a[q1[e1]] >= a[i])e1 --;
            while(s2 <= e2 && a[q2[e2]] <= a[i])e2 --;
            q1[++e1] = i, q2[++e2] = i;
            //直到极差小于等于k。
            //当退出循环的时候我们已经找到了那个最小的r，很明显，[1,r]的都符合。所以区间个数有r个。
            while(s1 <= e1 && s2 <= e2 && a[q2[s2]] - a[q1[s1]] > k){
                //cout << a[q2[s2]] << " " << a[q1[s1]] << endl;
                if(s1 <= e1 && (s2 > e2 || q1[s1] < q2[s2])){
                    //如果最大值队列为空或者该队首元素靠前。。
                    r = q1[s1 ++];//记录下标。
                }
                else{
                    r = q2[s2 ++];
                }
            }
            //cout << i << " " << r << endl;
            ans += r;
        }
        printf("%lld\n", ans);
    }
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++ i){
        scanf("%d", &a[i]);
    }
    solve();
    return 0;
}