最近都在学些科技，做些板子题。现在搜集一些个人觉得比较好的题目作为12月的第一个杂题集吧。

子集

首先，我们先考虑奇数长度段的情况（\(\{a_n\}\)已经排序）：确定中位数为\(a_{mid}\)，则我们发现答案为 左侧所有减去中位数的和 和 右侧所有减去中位数的和 的和，并除以元素个数。欲使价值最大，那么显然右侧需要靠近右端点进行选择， 而左侧需要靠近中位数进行选择。这个时候我们可以考虑使用二分答案来进行优化：简化对长度的枚举复杂度。

为什么这个判定有二分性呢？由于\(\forall a_i, a_i \geq 0\)，所以我们记\(suf_i^n = \sum_{j = i}^n a_j, suf_i^{mid} = \sum_{j = i}^{mid} a_j\)。可以确定的是，当\(i\)越小，这两个后缀和的大小都在单调不降；且，记\(\Delta_i^{mid} = suf_i^{mid} – suf_{i + 1}^{mid}, \Delta_i^n = suf_i^n – suf_{i + 1}^n\)，有\(\Delta_i^{mid} < \Delta_j^n, i \leq mid < j \leq n\)。所以，我们发现进行\(check(mid)\)且中位数为\(a_i\)时，如果\(suf_{n – mid + 1}^n – suf_{i – mid}^{i}\)的数值比上一次小，那么就没有伸展的必要了。

偶数段情况和奇数段一致，如果需要补充说明请在评论区提醒我。

// YBT-OJ1679.cpp
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAX_N = 2e5 + 200;

int n, seq[MAX_N];
ll prefix[MAX_N];

double calc(int pos, int len) { return double(prefix[n] - prefix[n - len] + prefix[pos] - prefix[pos - len - 1]) / double((len << 1) | 1); }

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &seq[i]);
    sort(seq + 1, seq + 1 + n);
    for (int i = 1; i <= n; i++)
        prefix[i] = 1LL * prefix[i - 1] + seq[i];
    // odd one;
    double gans = 0;
    for (int i = 2; i <= n - 1; i++)
    {
        int l = 1, r = min(n - i, i - 1);
        double pans = seq[i];
        while (l <= r)
        {
            int len = (l + r) >> 1;
            double tmp = calc(i, len);
            double cp = calc(i, len - 1);
            if (tmp - cp > -double(1e-8))
                pans = tmp, l = len + 1;
            else
                r = len - 1;
        }
        gans = max(gans, pans - seq[i]);
    }
    printf("%.5lf\n", gans);
    return 0;
}

CF1257E – The Contest

这道题还行吧，大概能用值域排列来搞前缀和进行最小值取值：某一个值若存在被移至前端的必要性，那么小于此值的都有被移动的必要性。前缀和即可。

// CF1257E.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5 + 2000;

int k[4], n, prefix[4][MAX_N], seq[4][MAX_N], min_val[MAX_N];

int main()
{
    scanf("%d%d%d", &k[1], &k[2], &k[3]), n = k[1] + k[2] + k[3];
    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= k[i]; j++)
            scanf("%d", &seq[i][j]), prefix[i][seq[i][j]]++;
    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= n; j++)
            prefix[i][j] += prefix[i][j - 1];
    for (int i = 0; i <= n; i++)
        min_val[i] = prefix[3][i] - prefix[2][i];
    for (int i = n - 1; i >= 0; i--)
        min_val[i] = min(min_val[i + 1], min_val[i]);
    int ans = 0x3f3f3f3f;
    for (int i = 0; i <= n; i++)
        ans = min(ans, prefix[2][i] - prefix[1][i] + min_val[i] + prefix[1][n] + prefix[2][n]);
    printf("%d\n", ans);
    return 0;
}

CF1151F – Sonya and Informatics

我觉得这题挺好的。

如何刻画一个这样的01串？我们扫一遍计算出有\(c\)个\(0\)，然后我们可以用\(dp[i][j]\)来记录：前\(i\)次操作后前\(c\)个数位中有\(j\)个\(0\)。我们发现这样的状态可以基本上定下计数规律：我们不需要具体的序列形状，因为交换并不涉及到具体的形状，只会影响某一段的\(01\)个数，所以计算这个就可以完美刻画状态。

具体的方程式见注释，并且需要用矩阵乘法来加速递推。

// CF1151F.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 110, mod = 1e9 + 7;

int n, k, seq[MAX_N], c;

struct matrix
{
    int mat[101][101];

    void clear() { memset(mat, 0, sizeof(mat)); }

    matrix operator*(const matrix &rhs)
    {
        matrix ret;
        ret.clear();
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= n; j++)
                for (int k = 0; k <= n; k++)
                    ret.mat[i][j] = (1LL * ret.mat[i][j] + 1LL * mat[i][k] * rhs.mat[k][j] % mod) % mod;
        return ret;
    }

    matrix operator^(const int &ti)
    {
        int tim = ti;
        matrix ret, bas = *this;
        ret.clear();
        for (int i = 0; i <= n; i++)
            ret.mat[i][i] = 1;
        while (tim)
        {
            if (tim & 1)
                ret = ret * bas;
            bas = bas * bas;
            tim >>= 1;
        }
        return ret;
    }
} A, B;

int quick_pow(int bas, int tim)
{
    int ret = 1;
    while (tim)
    {
        if (tim & 1)
            ret = 1LL * ret * bas % mod;
        bas = 1LL * bas * bas % mod;
        tim >>= 1;
    }
    return ret;
}

int main()
{
    const int inv2 = quick_pow(2, mod - 2);
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &seq[i]), c += (seq[i] == 0);
    // dp[i][j] = dp[i - 1][j] * (j * (c - j) + (c - j) * (n - 2 * c + j) + (c * (c - 1) >> 1) + ((n - c) * (n - c - 1) >> 1))
    //         += dp[i - 1][j - 1] * (c - j + 1) * (c - j + 1)
    //         += dp[i - 1][j + 1] * (j + 1)* (n - 2 * c + j + 1);
    int preZero = 0;
    for (int i = 1; i <= c; i++)
        preZero += (seq[i] == 0);
    for (int j = 0; j <= c; j++)
    {
        if (j != 0)
            B.mat[j - 1][j] = 1LL * (c - j + 1) * (c - j + 1) % mod;
        B.mat[j][j] = (1LL * j * (c - j) % mod + 1LL * (c - j) * (n - 2 * c + j) % mod + 1LL * (1LL * c * (c - 1) % mod * inv2 % mod) + (1LL * (n - c) * (n - c - 1) % mod * inv2 % mod)) % mod;
        if (j != c)
            B.mat[j + 1][j] = 1LL * (j + 1) * (n - 2 * c + j + 1) % mod;
    }
    A.mat[0][preZero] = 1;
    B = B ^ k, A = A * B;
    int ans = A.mat[0][c], tot = 0;
    for (int i = 0; i <= c; i++)
        tot = (1LL * tot + A.mat[0][i]) % mod;
    printf("%lld\n", 1LL * ans * quick_pow(tot, mod - 2) % mod);
    return 0;
}