牛客周赛40

A 小红进地下城

void solve() {
    string s1, s2;cin >> s1 >> s2;
    if (s1 == s2) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

B 小红打怪

小红来到了地下城的一个房间，房间被分成 n 行 m 列的格子，小红站在其中一个格子上，她可以向一个方向攻击整条直线的所有格子（小红不能改变自己的位置和朝向）。

小红想知道，自己可以攻击到多少只怪物？

char s[1010][1010];
void solve() {
    int n, m;cin >> n >> m;
    int sx = 0, sy = 0;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> s[i][j];
            if (s[i][j] == 'W' || s[i][j] == 'S' || s[i][j] == 'A' || s[i][j] == 'D') {
                sx = i, sy = j;
            }
        }
    }
    int cnt = 0;
    if (s[sx][sy] == 'W') {
        for (int i = 1;i <= sx;i++) {
            if (s[i][sy] == '*')cnt++;
        }
    } else if (s[sx][sy] == 'S') {
        for (int i = sx;i <= n;i++) {
            if (s[i][sy] == '*')cnt++;
        }
    } else if (s[sx][sy] == 'A') {
        for (int i = 1;i <= sy;i++) {
            if (s[sx][i] == '*')cnt++;
        }
    } else if (s[sx][sy] == 'D') {
        for (int i = sy;i <= n;i++) {
            if (s[sx][i] == '*')cnt++;
        }
    }
    cout << cnt << '\n';
}

C 小红的排列构造

小红拿到了一个长度为 n 的数组 a，她希望你构造两个排列 p 和 q，满足对于 i∈[1,n], ai 为 pi 或 qi 二选一。你能帮帮她吗？

当某个数出现的次数大于 2 时一定不存在这样的排列。

按照标记来，将 p1,p2 排列的部分位置数确定，再补全排列即可。

有点代码细节的。此题目用 set 更方便。

void solve() {
    int n;cin >> n;vector<int> a(n + 1), t(n + 1), p1(n + 1), p2(n + 1), vis(n + 1);
    for (int i = 1;i <= n;i++) cin >> a[i], t[a[i]]++;
    for (int i = 1;i <= n;i++) {
        if (t[i] > 2) {
            cout << "-1\n";return;
        }
    }
    for (int i = 1;i <= n;i++) {
        if (!vis[a[i]]) {
            p1[i] = a[i];vis[a[i]] = 1;
        } else {
            p2[i] = a[i];
        }
    }
    vector<int> vp1(n + 1), vp2(n + 1);
    for (int i = 1;i <= n;i++) {
        if (p1[i]) {
            vp1[p1[i]] = 1;
        }
        if (p2[i]) {
            vp2[p2[i]] = 1;
        }
    }
    vector<int> n1, n2;

    for (int i = 1;i <= n;i++) {
        if (!vp1[i])n1.push_back(i);
        if (!vp2[i])n2.push_back(i);
    }
    for (int i = 1;i <= n;i++) {
        if (!p1[i]) {
            p1[i] = n1.back();n1.pop_back();
        }
        if (!p2[i]) {
            p2[i] = n2.back();n2.pop_back();
        }
    }

    for (int i = 1;i <= n;i++)cout << p1[i] << " \n"[i == n];
    for (int i = 1;i <= n;i++)cout << p2[i] << " \n"[i == n];
}

D 小红升装备

给定 n 个装备的信息和金币总数。

每行给定装备初始战力，购买该装备需要的金币、升 1 级花费的金币、升 1 级提升的战力、最高可以提升的等级。

求能达到的最大战力。

Solution

分组背包/多重背包

分组：共 n 组背包，每组背包有 0−LVmax 级，每一级相当于这组中的一个物品。

每组物品中只能选择一个。知道了每一组每个物品物品的花费和战力。

求最大战力(每组最多取一个)。

#define int long long
int f[310];
void solve() {
    int n, x;cin >> n >> x;
    vector<array<int, 5>> a(n + 1);
    for (int i = 1;i <= n;i++) {
        int ini, price, cost, upini, LVmax;cin >> ini >> price >> cost >> upini >> LVmax;
        a[i] = {ini, price, cost, upini, LVmax};
    }
    for (int i = 1;i <= n;i++) {
        for (int j = x;j >= 0;j--) {
            for (int k = 0;k <= a[i][4];k++) {
                if (j >= a[i][1] + k * a[i][2]) {
                    f[j] = max(f[j], f[j - (a[i][1] + k * a[i][2])] + a[i][0] + k * a[i][3]);
                } else {
                    break;
                }
            }
        }
    }
    cout << f[x] << '\n';
}

牛客竞赛代码：(还可以用滚动数组优化)

#include<bits/stdc++.h>
using namespace std;
long long dp[303][303];        //dp[i][j]代表 前i个物品，花费总金币为j的最大战斗力
int main() {
    int n, i, j, x, k;
    cin >> n >> x;
    memset(dp, -0x3f, sizeof(dp));
    dp[0][0] = 0;
    long long res = 0;
    for (i = 1;i <= n;i++) {
        long long a, b, c, d, e;
        cin >> a >> b >> c >> d >> e;
        for (j = 0;j <= x;j++)dp[i][j] = dp[i - 1][j];    //啥都不干
        for (k = 0;k <= x;k++) {
            for (j = 0;j <= e;j++) {
                //初始花费为b，每升1级额外花c
                if (b + c * j > k) {
                    break;
                }
                dp[i][k] = max(dp[i][k], dp[i - 1][k - (b + c * j)] + a + j * d);
                res = max(res, dp[i][k]);
            }
        }

    }
    cout << res;

}

E 小红的矩阵划分

小红拿到了一个 n×n 的方格矩阵。她准备划分成若干个大小为 3 的'L'型连通块和若干个大小为 4 的 2×2 连通块。

已知个'L'型连通块可以获得 x 分，每个 2×2 的连通块可以获得 y 分。

小红想知道自己最多可以得到多少分？

int res = n * n / 4 * y;
for (int i = 0;i <= n && i * 4 <= n * n;i++) {
	res = max(res, i * y + ((n * n - i * 4) / 3) * x);
}
cout << res << '\n';

if (n % 6 == 0) {
	cout << max(n * n / 4 * y, n * n / 3 * x) << '\n';
} else {
	cout << max({n * n / 3 * x, n * n / 3 * x - x + y, n * n / 4 * y});
}

F 小红拿宝箱

小红击杀了一些怪物后，爆出了几个宝箱。她打算拿出几个宝箱里的钱币，但是，当小红拿到了 2 个宝箱的钱币后，其他宝箱就会消失。
现在小红每次可以随机打开一个宝箱查看里面的钱币，然后小红可以选择拿或者不拿。但是，小红只有最多一次“不拿”的机会。当小红选择“不拿”以后，这个宝箱会混入所有未抽取的宝箱。如果小红选择了“拿”，则获得这个宝箱的钱币，同时这个宝箱消失。
现在小红想知道，自己若采用最优策略（即最大化最终获取钱币的期望），能得到钱币数量的期望是多少？
请注意，小红在开箱之前，已经通过大预言术得知了每个箱子里的钱币数量。只是由于箱子被打乱了，小红在打开之前，不知道具体哪一个箱子有多少钱币。

Solution

期望

(待更 …)