2021牛客暑期多校训练营5

Boxes

如果用hint，必定在开局使用，因为信息没有衰减，早用一定比晚用好。也就是说，我先hint出来，那我一边开盒子一边算，一样可以达到后面再开的效果。

那么考虑每一种分布，分别统计期望即可

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
ld sum[N], a[N], c;
signed main() {
    int n;
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> c;
    rep(i, 1, n) cin >> a[i];
    sort(a + 1, a + n + 1);
    rep(i, 1, n) sum[i] = a[i] + sum[i - 1];
    ld ans = c;
    rep(i, 1, n-1) ans += sum[i] / pow(2.0, n - i);
    ans = min(ans, sum[n]);
    cout << fixed << setprecision(10) << ans;
    return 0;
}

Double Strings

用dp转移相同子序列数量，用组合数计算两串选出等长串，能选多少种

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 5007;
const int mod = 1e9 + 7;
int fac[N * 2] = {1, 1}, inv[N * 2] = {1, 1};
int dp[N][N];  // dp[i][j]表示 在A串前i个字符 B串前j个字符 有多少子序列相同
char a[N], b[N];
inline void init() {
    for (int i = 2; i < N * 2; ++i) {
        fac[i] = (ll)fac[i - 1] * i % mod;
        inv[i] = (ll)(mod - mod / i) % mod * inv[mod % i] % mod;
    }
    for (int i = 1; i < N * 2; ++i) inv[i] = (ll)inv[i] * inv[i - 1] % mod;
}
inline int C(int n, int m) {
    if (n < m) return 0;
    if (n == m) return 1;
    return (ll)fac[n] * inv[m] % mod * inv[n - m] % mod;
}
signed main() {
    init();
    scanf("%s%s", a + 1, b + 1);
    int n = strlen(a + 1), m = strlen(b + 1);
    rep(i, 1, n) rep(j, 1, m) {
        dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]) % mod;
        // 考虑不在两串中同时加入本字符的情况，那么就要么从a串尾缀，要么从b串尾缀，容斥处理一下即可
        if (a[i] == b[j]) dp[i][j] = (dp[i][j] + dp[i - 1][j - 1] + 1) % mod;
        // 如果a[i] == b[j] 即考虑同时在两串中加入本字符的情况
        // dp[i][j]可以自dp[i-1][j-1]转移（即尾缀本字符）
        // 也可以重新开始（+1） 即从本位开始
        if (dp[i][j] < 0) dp[i][j] += mod;
    }
    ll ans = 0;
    rep(i, 1, n) rep(j, 1, m) 
        if (b[j] > a[i]) 
            // 前面相同（加一个空串），后面随便选
            ans = (ans + (ll)(dp[i - 1][j - 1] + 1) * C(n - i + m - j, n - i)) % mod;
    pr(ans);
    return 0;
}

Holding Two

签到构造

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 1e3 + 7;
const int mod = 1e9 + 7;
char a[N][N];
int n, m;
bool chk(int x, int y) {
    for (int i = 1; i * 2 + x <= n; ++i)
        for (int j = 1; j * 2 + y <= m; ++j) {
            if (a[x][y] == a[x + i][y + j] and
                a[x][y] == a[i * 2 + x][j * 2 + y]) {
                cerr << x << ' ' << y << ' ' << x + i << ' ' << y + j << endl;
                return 0;
            }
        }
    return 1;
}
int main() {
    cin >> n >> m;
    rep(i, 1, n) rep(j, 1, m) {
        if (((i - 1) / 2) % 2 == 0)
            a[i][j] = (j & 1) + '0';
        else
            a[i][j] = '0' + !(j & 1);
    }
    rep(i, 1, n) puts(a[i] + 1);
    // rep(i, 1, n) rep(j, 1, m) {
    //     if (!chk(i, j)) cout << i << ' ' << j << '\n';
    // }
    return 0;
}
/*
10101010
10101010
01010101
01010101
*/

King of Range

题意是求满足极值大于k的区间有多少个。

思路是st表预处理区间极大值和极小值，然后跑双指针

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
int a[N], f[N][35], g[N][35], pw[35], lg[N];
inline int query(int l, int r) {
    int k = lg[r - l + 1];
    return max(f[l][k], f[r - pw[k] + 1][k]) -
           min(g[l][k], g[r - pw[k] + 1][k]);
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    pw[0] = 1;
    for (int i = 1; i <= 30; ++i) pw[i] = pw[i - 1] * 2;
    memset(g, 0x3f, sizeof g);
    int n, m, k, t;
    cin >> n >> m;
    rep(i, 1, n) {
        cin >> a[i];
        f[i][0] = g[i][0] = a[i];
        lg[i] = log2(i);
    }
    t = lg[n] + 1;
    for (int j = 1, tot; j < t; ++j) {
        tot = n - pw[j] + 1;
        for (int i = 1; i <= tot; ++i) {
            f[i][j] = max(f[i][j - 1], f[i + pw[j - 1]][j - 1]);
            g[i][j] = min(g[i][j - 1], g[i + pw[j - 1]][j - 1]);
        }
    }
    while (m--) {
        ll ans(0);
        cin >> k;
        for (int R = 1, L = 1; R <= n; ++R) {  // 对于每个R
            while (L <= R && query(L, R) > k) ++L;
            ans += L - 1;  // 1到L-1都满足
        }
        cout << ans << '\n';
    }
    return 0;
}