2024-09-08 16:29 山东大学嵌入式软件工程师发布于山东

关注

秋招日寄|小红书笔试20240908编程题记录

第一题

进入一个充满挑战的高科技迷宫。这是一张由科技部最新研发的网格地图，每个格子都藏着秘密————它们内置了自动滑行带!

这些滑行带会让所有进入它们的机器人自动朝一个特定方向滑行。

具体来说，一张 $n×m$ 的网格地图，左上角为 $(1,1)$ ，右下角为 $(n,m)$ ，每个格子有一个滑行带，前进方向为 $L,R,U,D$ ，分别表示左右上下四个方向前进。

如果第 $t$ 时刻，机器人位于 $(i,j)$ ， $(i,j)$ 滑行带前进方向为 $L$ ，则第 $t+1$ 时刻机器人位于 $(i,j-1)$ 。

如果第 $t$ 时刻，机器人位于 $(i,j)$ ， $(i,j)$ 滑行带前进方向为 $R$ ，则第 $t+1$ 时刻机器人位于 $(i,j+1)$ 。

如果第 $t$ 时刻，机器人位于 $(i,j)$ ， $(i,j)$ 滑行带前进方向为 $U$ ，则第 $t+1$ 时刻机器人位于 $(i-1,j)$ 。

如果第 $t$ 时刻，机器人位于 $(i,j)$ ， $(i,j)$ 滑行带前进方向为 $D$ ，则第 $t+1$ 时刻机器人位于 $(i+1,j)$ 。

机器人走出地图后就会毁坏，一个格子可以容纳多个机器人。

第 $0$ 时刻，每个位置都有一个机器人，问:第 $10^8$ 时刻，地图上还剩下多少个机器人?

输入描述

第一行两个整数 $n$ $m(1≤n×m≤ 5×10^3)$ ，表示地图大小。

接下来 $n$ 行，每行一个包含 $m$ 个字符的字符串，表示每个格子滑行带的方向。

输出描述

输出一行一个整数，表示第 $10^8$ 时刻，地图上剩下机器人的数量。

样例1

输入

 2 5
 LRRLR
 UULLR

输出

答案

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

using namespace std;

typedef pair<int, int> pii;
const int N = 5e3 + 10;

int n, m;
int ans;
string str[N];
int bps[N][N];
vector<pii> temp;

pii check(int x, int y) {
    int a, b;
    if (str[x][y] == 'L')
        a = x, b = y - 1;
    else if (str[x][y] == 'R')
        a = x, b = y + 1;
    else if (str[x][y] == 'U')
        a = x - 1, b = y;
    else if (str[x][y] == 'D')
        a = x + 1, b = y;

    if (b == -1 || b == m || a == -1 || a == n) {
        for (int i = 0; i < temp.size(); i++)
            bps[temp[i].first][temp[i].second] = 2;
        return {-1, -1};
    } else if (bps[a][b] == 1) {
        for (int i = 0; i < temp.size(); i++)
            bps[temp[i].first][temp[i].second] = 1, ans++;
        return {-1, -1};
    } else if (bps[a][b] == 2) {
        for (int i = 0; i < temp.size(); i++)
            bps[temp[i].first][temp[i].second] = 2;
        return {-1, -1};
    } else if (bps[a][b] == 3) {
        for (int i = 0; i < temp.size(); i++)
            bps[temp[i].first][temp[i].second] = 1, ans++;
        return {-1, -1};
    } else
        return {a, b};
}

void dfs(int x, int y) {
    temp.clear();
    while (bps[x][y] == 0) {
        temp.push_back({x, y});
        bps[x][y] = 3;
        pii tes = check(x, y);
        if (tes.first == -1)
            break;
        else {
            x = tes.first;
            y = tes.second;
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> str[i];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (bps[i][j] == 0)
                dfs(i, j);
        }
    }
    cout << ans << endl;
    return 0;
}

第二题

有一个长度为 $n$ 的数组 $a$ ，他定义了一个函数 $f:f(l,r)=\sum^r_{k=l}a_k$ ，即 $f$ ( $l,r$ )表示数组 $a$ 在[ $l,r$ ]这一段区间的区间和。

现在有一个重新任意排列数组 $a$ 的机会，想要最小化 $\sum^n_{l=1}\sum^n_{r=l}f(l,r)$ ，即最小化所有区间对于f的值之和，请你算算最小的这个值吧。

输入描述

第一行输入一个正整数 $n$ ( $1≤n≤2×10^5$ )代表数组中元素的个数。

第二行输入 $n$ 个整数 $a_1,a_2,......,a_n$ ( $1≤a_i≤10^5$ )代表数组中的元素。

输出描述

在一行上输出一个整数，表示题中所求答案。

样例1

输入

3 
1 2 3

输出

说明

重新排列为{ $1,2,3$ },此时全部区间为[ $2$ ]、[ $1$ ]、[ $3$ ]、[ $2,1$ ]、[ $1,3$ ]和[ $2,1,3$ ]总和恰好为 $19$ ，可以证明这是最小的。

样例2

输入

6
1 1 4 5 1 4

输出

答案

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

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    sort(arr.begin(), arr.end());

    long long sum1 = 0;
    for (int i = 0; i < n; i++) {
        long long contrib = (i + 1) * (long long)(n - i);
        sum1 += contrib * arr[n - i - 1];
    }

    cout << sum1 << endl;
    return 0;
}

第三题

定义 $f$ ( $x$ )为x在二进制表示下的 $1$ 个数，例如 $f(7)=3$ , $f(8)=1$ , $f(9)=2$ 。

定义 $g(x)$ 为第一个比 $x$ 大的数字 $y$ ,使得 $f(x)=f(y)$ ,例如 $g(1)=2,g(2)=4,g(3)=5$ 。

在首页有 $n$ 篇笔记，第 $i$ 篇笔记的点赞数量为 $a_i$ ，我们希望从中挑选出一些笔记，构造一个长度为 $m$ 的精选队列 $b_1,b_2,......,b_m$ 。在这里，精选队列满足：对于所有的 $j∈[2,m]$ ，都有 $b_j=g(b_{j-1})$ 。

输入描述

第一行输入一个整数 $n$ ( $1≤n≤10^5$ )。

第二行输入 $n$ 个整数 $a_1$ ( $1≤a_1,a_2,......,a_n≤10^9$ )。

输出描述

在一行上输出一个整数，代表最长的精选队列的长度。

样例1

输入

5
1 4 2 5 3

输出

说明

可以构成几种精选队列，分别为：

$[1,2,4],[2,4],[3,5],[1],[2],[3],[4],[5]$ 其中最长的为 $[1,2,4]$ ,长度为 $3$

样例2

输入

6
1 1 4 5 1 4

输出

答案

#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
#include <set>
using namespace std;

int g(int x) {
    string s = bitset<32>(x).to_string();

    int firstOne = s.find('1');
    if (firstOne == string::npos) return 0; 

    int firstZero = s.rfind('0', firstOne);
    if (firstZero == string::npos) firstZero = -1; 

    int onesToMove = firstOne - firstZero - 1;

    string newS = string(32, '0'); 
    newS[firstZero + 1] = '1'; 

    fill(newS.end() - onesToMove, newS.end(), '1');

    return bitset<32>(newS).to_ulong();
}

int solve(vector<int>& a) {
    sort(a.begin(), a.end());
    set<int> st(a.begin(), a.end()); 

    int ans = 0;

    for (int x : st) {
        int cnt = 0;
        while (st.count(x)) {
            cnt++;
            st.erase(x);
            x = g(x);
        }

        ans = max(ans, cnt);
    }

    return ans;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    cout << solve(a) << endl;
    return 0;
}

#通信硬件人笔面经互助#

SAGIMA笔面经整理文章被收录于专栏

本人在秋招过程中的一些笔试和面经，尽可能的结构化、系统化的整理了，有些细节可能记不太清，大家可以随便提问，肯定知无不言言无不尽！

全部评论

推荐最新楼层

菜鸡今天学习了吗

山东大学 C++

校友, 第二题思路和你一样, 但我的写法只 27%, 能帮忙看看吗 ```cpp const int maxn = 2e5 + 10; unsigned long long n, a[maxn], ans = 0, cnt[maxn]; int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; cnt[i] = (n - i + 1) * i; } sort(cnt + 1, cnt + n + 1, greater<int>()); sort(a + 1, a + n + 1); for (int i = 1; i <= n; i++) ans += cnt[i] * a[i]; cout << ans << endl; return 0; } ```</int>

点赞回复分享

发布于 2024-09-08 16:40 北京