深信服笔试 - 0910

BraumAce2024年9月11日约 1933 字大约 6 分钟

深信服笔试 - 0910

第一题

题面

$x, y$ 为正整数, 求 $x$ 的 $y$ 次方的个位数是多少？

输入描述:
依次输入两个数（每行一个），第一个为 $x$ ，第二个为 $y$

输出描述:
输出个位数

示例：

输入：8
      198
输出：4

思路与代码

核心在于找出幂运算结果个位数的循环规律。对于任何正整数 $x$ ，其幂次运算的个位数都会呈现周期性变化。所以只需要计算出这个周期，然后利用模运算快速得到结果，而不需要真正计算出 $x$ 的 $y$ 次方这个可能非常大的数。

循环周期：
- 对于尾数为 $0$ 、 $1$ 、 $5$ 、 $6$ 的数，周期为 $1$
- 对于尾数为 $4$ 、 $9$ 的数，周期为 $2$
- 对于尾数为 $2$ 、 $3$ 、 $7$ 、 $8$ 的数，周期为 $4$
根据 $x$ 的个位数确定周期 $length$ 。
计算 $y \ \% \ length$ ，得到在循环中的位置。
用快速幂方法计算 $x^{y \ \% \ length}$ 的个位数，返回即可。

#include <iostream>
using namespace std;

int quickPow(int x, int y) {
    int result = 1;
    x %= 10;
    while (y > 0) {
        if (y & 1) result = (result * x) % 10;
        x = (x * x) % 10;
        y >>= 1;
    }
    return result;
}

int lastDigit(int x, int y) {
    if (y == 0) return 1;
    x %= 10;
    int length;
    if (x == 0 || x == 1 || x == 5 || x == 6) length = 1;
    else if (x == 4 || x == 9) length = 2;
    else length = 4;
    
    y = y % length;
    if (y == 0) y = length;
    
    return quickPow(x, y);
}

int main() {
    int x, y;
    cin >> x >> y;
    cout << lastDigit(x, y) << endl;
    return 0;
}

第二题

题面

给定存在 $N$ 个元组的集合，每个元组里面的值为（等级，价格），等级和价格都是非负整数。在集合中选取数量大于 $0$ 小于等于 $N$ 的元组，要求这些元组的等级差不能超过 $x$ ，并且它们的价格之和最大。最后输出最大的价格。

输入描述：
第一行包含两个整数 $N$ 和 $x (1 ≤ n ≤ 10^5,1 ≤ x ≤ 10^{10})$ ，分别是给定的元组集合的数量和等级差。
接下来的 $N$ 行是元组的具体数值，每一行为一个元组的两个值，等级和价格，数字之间用空格隔开。

输出描述：
输出选取的元组最大的价格之和

示例：

思路与代码

排序 + 滑动窗口。

核心思路是先按照等级对元组进行排序，然后使用滑动窗口来找到满足等级差不超过 $x$ 的最大连续区间，同时维护这个区间内的价格和。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Tuple {
    long long level;
    long long price;
};

int main() {
    int N;
    long long x;
    cin >> N >> x;

    vector<Tuple> tuples(N);
    for (int i = 0; i < N; ++i) {
        cin >> tuples[i].level >> tuples[i].price;
    }

    sort(tuples.begin(), tuples.end(), [](const Tuple& a, const Tuple& b) {
        return a.level < b.level;
    });

    long long maxSum = 0;
    long long currentSum = 0;
    int left = 0;

    for (int right = 0; right < N; ++right) {
        currentSum += tuples[right].price;

        while (tuples[right].level - tuples[left].level > x) {
            currentSum -= tuples[left].price;
            left++;
        }

        maxSum = max(maxSum, currentSum);
    }

    cout << maxSum << endl;

    return 0;
}

第三题

题面

公司新大楼要设计一片花坛，现购买了 $w$ 种不同的花卉品种，第 $i$ 种（ $1≤i≤w$ ）花卉的花朵数量为 $a_i$ 。为设计漂亮美观的花坛，现将花坛被划分成有 $n*m$ 个单元格组成的网格，每个单元格中最多只能有一种花卉，并且每种花卉只能种在一个单元格里。

花坛的美观度等于花坛中所有边长为 $k$ 个单元格的正方形子网格的美观度之和，而一个子网格的美观度等于种植其中花朵数量的总和。在所有可能的情况下，请选择美观度最大的种植方案。

输入描述:
第一行包含整数 $n$ 、 $m$ 、 $k (1≤n,m≤2*10^5, 1≤n*m≤2*10^5, 1≤k≤min(n,m))$ ， $n$ 、 $m$ 代表行列数， $k$ 代表子网格的边长。
第二行包含一个整数 $w (1≤w≤n*m)$ ，表示花卉品种的数量。
第三行包含 $w$ 个整数 $a_1,a_2,...,a_w (1≤ai≤10^9)$ ，表示各种花卉花朵的数量。

输出描述：
最大的美观度

示例：

思路与代码

贪心。

我们需要将花朵数量最多的花卉放在能够被最多子网格覆盖的位置，以此最大化美观度。由于每个单元格只能放置一种花卉，且每种花卉只能种在一个单元格里，我们实际上是在寻找一种最优的花卉分配方案。

先计算每个单元格被覆盖的次数
将子网格按被覆盖的次数从大到小排序
同时，将花卉按数量从大到小排序
按照排序后的顺序，将花卉依次放置到对应的单元格中，保证花朵数量最多的花卉被放置到最多覆盖的位置

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

struct Cell {
    int x, y, count;
};

int main() {
    int n, m, k, w;
    cin >> n >> m >> k >> w;

    vector<ll> flowers(w);
    for (int i = 0; i < w; i++) {
        cin >> flowers[i];
    }

    vector<vector<int>> coverage(n, vector<int>(m, 0));
    for (int i = 0; i < n - k + 1; i++) {
        for (int j = 0; j < m - k + 1; j++) {
            for (int x = i; x < i + k; x++) {
                for (int y = j; y < j + k; y++) {
                    coverage[x][y]++;
                }
            }
        }
    }

    vector<Cell> cells;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cells.push_back({i, j, coverage[i][j]});
        }
    }

    sort(cells.begin(), cells.end(), [](const Cell& a, const Cell& b) {
        return a.count > b.count;
    });

    sort(flowers.rbegin(), flowers.rend());

    vector<vector<ll>> garden(n, vector<ll>(m, 0));
    for (int i = 0; i < min(w, (int)cells.size()); i++) {
        garden[cells[i].x][cells[i].y] = flowers[i];
    }

    ll beauty = 0;
    for (int i = 0; i < n - k + 1; i++) {
        for (int j = 0; j < m - k + 1; j++) {
            ll subgrid_beauty = 0;
            for (int x = i; x < i + k; x++) {
                for (int y = j; y < j + k; y++) {
                    subgrid_beauty += garden[x][y];
                }
            }
            beauty += subgrid_beauty;
        }
    }

    cout << beauty << endl;

    return 0;
}

第四题

题面

一个游戏玩家有 $k$ 点体力，在一个 $m * n$ 的表格中，其中（ $k$ ， $m$ ， $n$ 都为正整数），玩家位于 $(0,0)$ ，需要达到终点 $(m,n)$ 。玩家只能上下左右移动，且每次只能移动 $1$ 的长度并消耗 $1$ 的体力。当体力耗尽的时候玩家无法移动。

给定 $k$ ， $m$ ， $n$ ，问玩家能否移动到终点，如能，则给出能到达终点的最短路径的走法数目。

其中：
$0 < m \leq 30$
$0 < n \leq 30$

输入描述：
依次输入三个数（每行一个），第一个为 $k$ ，第二个为 $m$ ，第三个为 $n$

输出描述：
如能达到终点，则输出所有路径的数目；如不能，则输出 $0$

示例：

输入：4
      1
      1
输出：2

思路与代码

动态规划。

由于体力限制和路径最短的要求，我们需要考虑两个维度：位置和剩余体力。

对于每个位置，我们只需要记录到达该位置时的最小体力消耗，因为这决定了是否能到达终点以及路径是否最短。

维护一个DP数组 $dp[i][j][k]$ ，表示到达位置 $(i, j)$ 时剩余体力为 $k$ 的路径数。

初始化： $dp[0][0][k] = 1$ ，表示起点有一条路径。

#include <iostream>
#include <vector>

using namespace std;

long long pathCount(int k, int m, int n) {
    vector<vector<vector<long long>>> dp(m + 1, vector<vector<long long>>(n + 1, vector<long long>(k + 1, 0)));
    
    dp[0][0][k] = 1;
    
    for (int i = 0; i <= m; ++i) {
        for (int j = 0; j <= n; ++j) {
            for (int l = 0; l <= k; ++l) {
                if (i > 0 && l < k) {
                    dp[i][j][l] += dp[i - 1][j][l + 1];
                }
                if (j > 0 && l < k) {
                    dp[i][j][l] += dp[i][j - 1][l + 1];
                }
            }
        }
    }
    
    long long total = 0;
    for (int l = 0; l <= k; ++l) {
        total += dp[m][n][l];
    }
    
    return total;
}

int main() {
    int k, m, n;
    cin >> k >> m >> n;
    
    long long result = pathCount(k, m, n);
    cout << result << endl;
    
    return 0;
}