20230617 信息学期末测试 B 组题解

讨论

题解

士兵占领

第一题：字符串排序

定位是签到题，抬走，下一题

第二题：鸢尾花数

从枚举到 , 对每个数字进行数位分解，同时数位分解的过程中查看差值是否为一个定制

参考代码

#include <iostream>
#include <cstdio>

using namespace std;

int main() {
    int a, b, get, dif = 0, last;
    int s = 0;
    cin >> a >> b;
    for (int i = a; i <= b; i++) {
        int x = i, f = 0;
        last = 0;
        while (x) {
            get = x % 10;
            x /= 10;
            if (f == 1)
                dif = get - last;
            if (f != 0)
                if (dif != get - last) {
                    f = -1;
                    break;
                }
            last = get;
            f++;
        }
        //	printf("%d : %d %d\n",i,dif,f);
        if (f != -1) {
            cout << i << " ";
            s = 1;
        }
    }
    if (s == 0)
        cout << -1;
    return 0;
}

第三题：安排司机

考察点：简单贪心

我们对下午时间和晚上时间进行排序，让小的下午时间和大的晚上时间分配给同一个司机即可，然后计算一下加班费

参考代码：

sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1);
int ans = 0;
for (int i = 1; i <= n; i++) ans += max(a[i] + b[n - i + 1] - d, 0) * r;
printf("%d\n", ans);

第四题：日记

的分数爆搜即可，非常暴力的那种

以下是 csy 的 50 分做法：

#include <iostream>
using namespace std;

int n, t, c = 0;

void dfs(int x, int y, int deep) {
    if (deep > n) {
        return;
    }

    if (x == 0 && y == 0 && deep == n) {
        c++;  // c++!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
        c %= 1997;
        return;
    }

    dfs(x + 1, y, deep + 1);
    dfs(x - 1, y, deep + 1);
    dfs(x, y + 1, deep + 1);
    dfs(x, y - 1, deep + 1);
}

int main() {
    cin >> t;
    while (t--) {
        cin >> n;

        if (n % 2 == 1) {
            cout << "0\n";
            continue;
        }

        c = 0;
        dfs(0, 0, 0);
        cout << c << endl;
    }
}

的分数，我们需要先用计算杨辉三角的方式求出组合数

void pre() {
    for (int i = 0; i < N; i++) {
        c[i][0] = 1;
        for (int j = 1; j < i; j++) c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % Mod;
        c[i][i] = 1;
    }
    return;
}

接下来需要用到一些数学知识, 本质是一个网格游走路线计算问题, 因为左右走和上下走的步数是对称相等，那么我们可以枚举上下走了步, 左右走了步，最后的计算为：

int m = n / 2;

int ans = 0;
for (int i = 0; i <= m; i++) {
    (ans += c[m][i] * c[m][i] % Mod) %= Mod;
}
(ans *= c[n][m]) %= Mod;
cout << ans << endl;

第五题：物品分组

本题考察的是背包问题中的差值背包问题

表示前个物品能否组成差值绝对值为的情况，能就是 true ，不能就是 false

转移的时候考虑绝对是继续变大还是缩小，即考虑放到哪个组里，

参考代码

for (int i = 1; i <= n; ++i) {
        scanf("%d", &w[i]);
        sum += w[i];
    }
    f[0] = true;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= sum; ++j)
            if (f[j]) {
                g[j + w[i]] = true;
                g[abs(j - w[i])] = true;
            }

        for (int j = 0; j <= sum; ++j) f[j] |= g[j];
    }

本题也可以转换成 01 背包问题去做，转换思想如下

由于一个物品选择可以起到加法和减法的作用，那么我们可以把一个重量为的物品分成一个重量为的物品和一个重量为的物品。然后用这个物品跑一下01背包即可。具体的，我们设表示前 i个物品，是否能凑成质量j，显然有

由于物品有负数，所以注意下标需要有一个偏移

第六题：士兵占领

考察点：记忆化搜索

原题：CF382D

枚举每个 # 作为两颗棋子最后的终点，反向向回推，采用记忆化搜素的方式，维护每个点出发的最大值，以及全局的最大值和次大值，如果全局最大值和次大值相等，答案就是二倍的最大值，否则答案是最大值 * 2 – 1，即放两个相邻的棋子，走到最后。

heyucheng

2023-06-23 18:51:57

666

liujunhao

2023-06-17 19:08:26

20230617 信息学期末测试 B 组 题解