小黑盒笔试 - 0907

BraumAce2024年9月15日约 1608 字大约 5 分钟

小黑盒笔试 - 0907

第一题

题面

有一条街，街里有 $n$ 个房子，房子的编号按顺序为 $0, ..., n-1$

你需要寻找这里的有且仅有一个的网吧。你在这条街里询问每一个房子询问"哪个房子是网吧"，每次询问时房子的主人都会回答 “网吧离我距离为 $x$ ”

输入为一个整型数组 house[]，数组长度为 $n$ ，数组元素为每个房子的主人回答的数字 $x$ ，
如果 house[i] == -1 表示这个房子的主人不想回答问题，否则 house[i] 是非负整数，表示第 $i$ 个房间的主人回答的数字 $x$ 。

假设所有的房主回答都是正确的情况下，返回一个整型数组 int[]，包含所有可能是网吧的房间的编号集合。(按数字递增排序返回)

示例：

输入：[-1,-1,-1,-1,-1]
输出：[0,1,2,3,4,5]
说明：因为所有房主都没有回答，所以所有房间都可能为网吧

思路与代码

模拟。遍历每个房子，根据房主的回答来验证每个可能的网吧位置是否符合已知的距离信息。

使用一个 bool 数组 st[] 作为标记，初始化全为 $true$ ，表示所有位置都可能是网吧。
遍历，如果 house[i] != -1，说明房主提供了有效信息：
- 计算可能的网吧距离 $|i - j|$ ，如果这个距离不等于 house[i]，将 st[i] 置为 $false$
最后将遍历后的 st[] 数组中结果为 $true$ 的索引 $i$ 加入到结果数组中即可。

class Solution {
public:
    vector<int> findPossibleCafe(vector<int>& house) {
        int n = house.size();
        vector<bool> possibleCafe(n, true);
        
        for (int i = 0; i < n; i++) {
            if (house[i] != -1) {
                for (int j = 0; j < n; j++) {
                    if (abs(i - j) != house[i]) {
                        possibleCafe[j] = false;
                    }
                }
            }
        }
        
        vector<int> res;
        for (int i = 0; i < n; i++) {
            if (possibleCafe[i]) {
                res.push_back(i);
            }
        }
        
        return res;
    }
};

第二题

题面

你喜欢的一个商店开始了促销活动。
每次你在商店里花费了 $S$ 元，你就能够获得一个随机的优惠券。比如， $S=10$ 时如果你在商店里花费了 $27$ 元，你可以获得 $2$ 个优惠券（ $10+10+7$ ，最后的 $7$ 不到 $8$ 所以被当作无效）。

现在给你列出一个商品的价格集合 prices[]，你需要购买这里的所有商品且每个只买一份。你可以同时购买其中若干子集（根据价格之和），并获得一次对应的优惠券，然后在剩下的商品里再购买若干子集，获得优惠券，依此不断的做，直到所有的商品都购买为止。

请返回一个数组，数组大小为 $2$ ，
第一个数字为 $A$ ，表示你采取最优策略的情况下获得的最多的优惠券个数，
第二个数字为 $B$ ，表示你采取最优策略的情况下获得的最少的优惠券个数。

示例：

输入: 7
      [10, 21, 98, 19]
输出: [21,20]
说明: 先购买第二个商品价格为21，获得3个优惠券
      然后购买剩下的3个商品价格为(10+98+19) = 127，127/7 = 18，获得18个优惠券，
      这种情况下最多能获得21个优惠券

思路与代码

动态规划：计算出所有可能的子集购买方案，找出能获得最多和最少优惠券的方案。

定义商品的选择状态，1表示选中，0表示未选中。
创建两个DP数组：dp_max 和 dp_min，分别用于存储最大和最少优惠券数。
对于每个状态，将其拆分为两个子状态，计算分别购买这两部分能获得的优惠券总数。
更新 dp_max 和 dp_min 数组，记录每个状态下的最优解。
最终返回全选状态下的最大和最小优惠券数。

代码不完全正确，只通过了 60%

class Solution {
public:
    vector<int> calc(int S, vector<int>& prices) {
        int n = prices.size();
        int total = 1 << n;
        vector<int> sum(total, 0);
        vector<int> dp_max(total, 0);
        vector<int> dp_min(total, INT_MAX);
        
        for (int i = 1; i < total; i++) {
            for (int j = 0; j < n; j++) {
                if (i & (1 << j)) {
                    sum[i] = sum[i - (1 << j)] + prices[j];
                    break;
                }
            }
            dp_min[i] = sum[i] / S;
        }
        
        for (int i = 1; i < total; i++) {
            for (int j = i; j > 0; j = (j - 1) & i) {
                int coupons = dp_max[j] + dp_max[i - j];
                dp_max[i] = max(dp_max[i], coupons);
                dp_min[i] = min(dp_min[i], dp_min[j] + dp_min[i - j]);
            }
        }
        
        return {dp_max[total - 1], dp_min[total - 1]};
    }
};

第三题

题面

你在玩一个横版游戏。

横版游戏由 $N+1$ 个连续的格子组成。编号 $0$ 的格子为起始点，编号 $N$ 的格子为终点。

从起点开始, 每次你最多可以往右移动 $x$ 步（ $1$ ～ $x$ 任意步都可以）。比如你在位置 $1$ , 如果往右移动 $x$ 步，下一个位置为 $x+1$ 。当你每次移动到某个格子的时候, 会收到伤害为 $T_i$

请计算从格子 $0$ 走到 $N$ ，能够受到的最少总伤害。

T[i] 的计算方式如下：

T[0] = 0
state = seed
for i = 1 to N:
    state = (state * 1103515245 + 12345) % 2^31
    T[i] = 1 + (state % M)

补充说明，参数取值范围:
$1 \le N \le 500000$
$1 \le x \le 500000$
$0 \le seed \le 2^{31}-1$
$1 \le M \le 10^9$

思路与代码

动态规划：需要找到从起点到中电的路径，使得受到的总伤害最小。

先根据给定的公式计算出所有位置的伤害值 T[i]。
定义DP数组，dp[i] 表示到达位置i时的最小总伤害。
初始化 dp[0] = 0，因为起点不受伤害。
对于每个位置 $i$ （从 $1$ 到 $N$ ），考虑从 $i-x$ 到 $i-1$ 的所有可能的前一个位置，选择使得总伤害最小的那个。
得到状态转移方程：dp[i] = min(dp[k] + T[i])，其中 $k$ 范围是 $max(0, i-x)$ 到 $i-1$ 。最后 dp[N] 即为所求。

#include <iostream>
#include <vector>
#include <deque>
#include <climits>
#define ll long long
using namespace std;
const int MOD = 1 << 31;

int main() {
    int N, x, M;
    ll seed;
    cin >> N >> x >> seed >> M;

    vector<int> T(N + 1);
    T[0] = 0;
    ll state = seed;
    for (int i = 1; i <= N; ++i) {
        state = (state * 1103515245 + 12345) % MOD;
        T[i] = 1 + (state % M);
    }

    vector<ll> dp(N + 1, LLONG_MAX);
    dp[0] = 0;

    deque<int> dq;
    dq.push_back(0);

    for (int i = 1; i <= N; ++i) {
        if (!dq.empty() && dq.front() < i - x) {
            dq.pop_front();
        }

        dp[i] = dp[dq.front()] + T[i];

        while (!dq.empty() && dp[dq.back()] >= dp[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
    }

    cout << dp[N] << endl;

    return 0;
}