牛客周赛 Round 40（A~F）（动态规划/背包/数论/数学期望）

小红拿宝箱

https://ac.nowcoder.com/acm/contest/80259/F

没有佬发题解，班门弄斧，写一个吧

知乎版本

竞赛地址

A. 小红进地下城

在这里插入图片描述

void solve() {
    string s1, s2;
    cin >> s1 >> s2;
    cout << (s1 == s2 ? "Yes" : "No") << endl;
}

B. 小红打怪

在这里插入图片描述

const int maxn = 1010;

int n, m;
char s[maxn][maxn];
int x, y;
char s2[] = "WSAD";
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
bool check(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}
void solve() {
    cin >> n >> m;
    
    for (int i = 0; i < n; ++i) {
        cin >> s[i];
        for (int j = 0; j < m; ++j) {
            if (s[i][j] != '.' && s[i][j] != '*') {
                x = i;
                y = j;
            }
        }
    }
    int p;
    for (int i = 0; i < 4; ++i) {
        if (s2[i] == s[x][y]) {
            p = i;
        }
    }
    int res = 0;
    while(check(x, y)) {
        if (s[x][y] == '*') {
            ++res;
        }
        x += dx[p];
        y += dy[p];
    }
    cout << res << endl;
}

C. 小红的排列构造

在这里插入图片描述

const int maxn = 100010;

int n, m;
int p[maxn], q[maxn];
int mp[maxn];
int a[maxn], b[maxn];
int x, y;

void solve() {
    scanf("%d", &n);
    bool ok = 1;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &x);
        if (!ok || ++mp[x] > 2) {
            ok = 0;
            continue;
        }
        if (mp[x] == 1) {
            a[x] = 1;
            p[i] = x;
        } else {
            b[x] = 1;
            q[i] = x;
        }
    }
    if (!ok) {
        printf("-1\n");
        return;
    }
    vector<int> v;
    for (int i = 1; i <= n; ++i) {
        if (!a[i]) {
            v.push_back(i);
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (!p[i]) {
            p[i] = v.back();
            v.pop_back();
        }
    }
    
    for (int i = 1; i <= n; ++i) {
        if (!b[i]) {
            v.push_back(i);
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (!q[i]) {
            q[i] = v.back();
            v.pop_back();
        }
    }
    
    for (int i = 1; i <= n; ++i) {
        printf("%d ", p[i]);
    }
    printf("\n");
    for (int i = 1; i <= n; ++i) {
        printf("%d ", q[i]);
    }
    printf("\n");
}

D. 小红升装备（01背包）

在这里插入图片描述 01背包变形， dp[i][j][k]维护取前i个物品，容量为j，且第i个物品升k级时的最大战力。

转移方程为

dp[i][j][k] = max(max(dp[i-1][j][k1]), max(dp[i-1][j-p[i]-k*c[i]][k2])); // k1,k2取任意值

利用01背包的特点，从后往前遍历容量，进行空间优化

dp[j][k] = max(max(dp[j][k1]), max(dp[j-p[i]-k*c[i]][k2])); // k1,k2取任意值

里边的max值，我们可以维护一个容量为j时的mx数组mx[j]，进一步简化

dp[j][k] = max(mx[j], mx[j-p[i]-k*c[i]] + a[i] + 1LL * u[i] * k);

完整代码

const int maxn = 310;

int n, m;
int a[maxn], p[maxn], c[maxn], u[maxn], l[maxn];
ll dp[maxn][maxn];
ll mx[maxn];
void solve() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d%d%d%d", &a[i], &p[i], &c[i], &u[i], &l[i]);
    }
    
    // 01背包 
	for (int i = 1; i <= n; ++i) {
		for (int j = m; j >= p[i]; --j) {
            int limit = min(l[i], (j - p[i]) / c[i]);
            for (int k = 0; k <= limit; ++k) {
                dp[j][k] = max(mx[j], mx[j-p[i]-k*c[i]] + a[i] + 1LL * u[i] * k);
            }
			
		}
        for (int j = m; j >= p[i]; --j) {
            int limit = min(l[i], (j - p[i]) / c[i]);
            for (int k = 0; k <= limit; ++k) {
                mx[j] = max(mx[j], dp[j][k]);
            }
        }
	}
    
    printf("%lld\n", mx[m]);

}

E. 小红的矩阵划分

在这里插入图片描述分类讨论，

如果x/3 <= y/4，则全部取y
否则，尽量取x

ll n, x, y;
void solve() {
    scanf("%lld%lld%lld", &n, &x, &y);
    if (4 * x <= 3 * y) { // x/3 <= y/4
        n /= 2;
        printf("%lld\n", n * n * y);
        return;
    }

    ll ans = (n * n) / 6 * (2 * x);
    ans += ((n * n) % 6) / 4 * max(x, y); // 可以不填满，取  max(x, y)
    printf("%lld\n", ans);

}

F. 小红拿宝箱

在这里插入图片描述

由于总共就2轮，我们可以枚举第一轮抽到的元素，单独计算它们的期望值。最后累加即可。注意，第一轮，抽到小于平均值的元素时，不一定需要直接弃用。计算出来的期望值可能会大于默认期望值。

比赛时没想到这个点。

详见代码注释。

const int maxn = 100010;

int n;
double a[maxn];
double suf[maxn];
double x;
void solve() {
    scanf("%d", &n);
    double sum = 0;
    for (int i = 1; i <= n; ++i) {
        scanf("%lf", &a[i]);
        sum += a[i];
    }
    sort(a + 1, a + n + 1); // 排序
    
    suf[n+1] = 0; // 预处理 后缀和
    for (int i = n; i >= 1; --i) {
        suf[i] = suf[i+1] + a[i];
    }
    
    if (n <= 2) { // 特判
        printf("%f\n", sum);
        return;
    }
    double ori = sum * 2 / n; // 任意取2个的期望值
    int p = 0; // 第一个>=平均值sum/n的下标
    while (p + 1 <= n && a[p+1] * n < sum) {
        ++p;
    }

    double ans = 0;
    for (int i = 1; i <= p; ++i) { // 枚举小于 平均值的情况
        // remove a[i]
        sum -= a[i];
        
        double res = 0;
        // 此时去除a[i]后，新的平均值会变大，>= 新的平均值 的下标在区间[p+1, n]获取
        int pos = lower_bound(a + p + 1, a + n + 1, sum / (n - 1)) - a - 1; // 求出 最大的 < 新平均值 的下标
        // 1. (pos - 1) / (n - 1)的概率拿到小于 平均值的，此时 用掉机会，再抽一次，此时 取n-1个元素平均值 sum / (n - 1)
        // 注意a[i]包含在[1, pos]中，需要去除，因此是 pos - 1个元素
        res = sum * (pos - 1) / (n - 1) * 1 / (n - 1); 
        // 2. (n - pos) / (n - 1)的概率拿到大于 平均值的，此时直接使用，(a[pos] + ... + a[n]) / (n - pos)
        // res += ((n - pos) / (n - 1)) * (suf[pos+1] / (n - pos));
        res += suf[pos+1] / (n - 1);
        ans += max(res + a[i], ori); // 取两者最大值
        
        // re add a[i]
        sum += a[i];
    }
    
    for (int i = p + 1; i <= n; ++i) { // 枚举>= 平均值的情况
        
        // remove a[i]
        sum -= a[i];
        
        double res = 0;
        // 此时去除a[i]后，新的平均值会变小，>= 新的平均值 的下标在区间[1, p]获取
        int pos = lower_bound(a + 1, a + p + 1, sum / (n - 1)) - a - 1; // 求出 最大的 < 新平均值 的下标
        // 1. pos / (n - 1)的概率拿到小于 平均值的，此时 用掉机会，再抽一次，此时 取n-1个元素平均值 sum / (n - 1)
        res = sum * pos / (n - 1) * 1 / (n - 1);
        // 2. (n - pos - 1) / (n - 1)的概率拿到大于 平均值的，此时直接使用，(a[pos] + ... + a[n]) / (n - pos)
        // 注意a[i]包含在[pos+1, n]中，需要额外去除
        // res += ((n - 1 - pos) / (n - 1)) * ((suf[pos+1] - a[i]) / (n - 1 - pos));
        res += (suf[pos+1] - a[i]) / (n - 1);
        ans += max(res + a[i], ori); // 取两者最大值
        
        // re add a[i]
        sum += a[i];
    }
    
    printf("%.10f", ans / n);

}