「笔试练习」2021 拼多多笔试题目

提前感受一下笔试难度~

A

https://www.nowcoder.com/questionTerminal/3d6b53e097ea41bda049d111f30db28e

和最大为 45，大于 45 直接输出 -1。

然后优先位数更少，所以竟可能的放更大的数字，例如 9,8,7这些。

而更大的数字优先往后面放，所以就有了如下做法：

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    if (n > 45) {
        cout << -1 << "\n";
        return 0;
    }
    string res = "";
    for (int i = 9; i >= 1; i--) {
        if (n > i) {
            res += '0' + i;
            n -= i;
        } else {
            res += '0' + n;
            break;
        }
    }
    reverse(res.begin(), res.end());
    cout << res << endl;
}

B

https://www.nowcoder.com/questionTerminal/78255f37c7dc4f749ceafc8c58206a43

两个字符串相同的部分不需要消费代价。而不同的部分，要贪心的去匹配修改。

例如 a 中的 f, z 要替换到 b 中的 g，h。那么我们的做法是 f->g, z->h。即排序后更近的去匹配。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;
    sort(s.begin(), s.end());
    sort(t.begin(), t.end());
    int res = 0;
    for (int i = 0; i < s.size(); i++) {
        res += abs(s[i] - t[i]);
    }
    cout << res << "\n";
    return 0;
}

C

https://www.nowcoder.com/questionTerminal/877c520f935c4d67a4614dc4bce84a1a

维护一个前缀和模 M 的结果，如果两个前缀模 M 的结果相同，则它们中间的子数组模 M 是 0，是和谐的。

因此，用哈希维护每一个前缀和的数量即可，过程中直接做统计。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n, m, pre = 0;
    cin >> n >> m;
    vector<int> a(n);
    unordered_map<int, int> mp;
    mp[0] = 1;
    long long res = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        pre = (pre + a[i]) % m;
        res += mp[pre];
        mp[pre]++;
    }
    cout << res << endl;
    return 0;
}

D

https://www.nowcoder.com/questionTerminal/27086d759f01413b94a1a30a53e4a333

枚举，因为骰子只有 4 种旋转方法，所以每获得一个新的骰子，就 BFS 一下，把所有可能都遍历到（最多可能 24 种？），然后后面如果在遇到一样的，就可以直接判断它属于哪一种了。

记录每一种的数量，最后输出答案即可。

#include <bits/stdc++.h>
#include <cstdio>
#include <functional>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;
struct sieve{
    int up, down, left, right, front, back;
    string to_string() {
        static char t[15];
        // cout << up << ' ' << down << ' ' << left << ' ' << right << ' ' << front << ' ' << back << endl;
        sprintf(t, "%d%d%d%d%d%d", up, down, left, right, front, back);
        return string(t);
    }
};
sieve toUp(sieve s) {
    tie(s.front, s.down, s.back, s.up) = make_tuple(s.down, s.back, s.up, s.front);
    return s;
}
sieve toDown(sieve s) {
    tie(s.front, s.down, s.back, s.up) = make_tuple(s.up, s.front, s.down, s.back);
    return s;
}
sieve toLeft(sieve s) {
    tie(s.front, s.right, s.back, s.left) = make_tuple(s.right, s.back, s.left, s.front);
    return s;
}
sieve toRight(sieve s) {
    tie(s.front, s.right, s.back, s.left) = make_tuple(s.left, s.front, s.right, s.back);
    return s;
}
int main() {
    int n;
    cin >> n;
    // 筛子序列化 -> 种类编号
    unordered_map<string, int> mp;
    vector<int> cnt(n);
    for (int i = 0; i < n; i++) {
        sieve s;
        cin >> s.up >> s.down >> s.left >> s.right >> s.front >> s.back;
        // cout << s.to_string() << endl;
        if (mp.count(s.to_string())) {
            cnt[mp[s.to_string()]]++;
            continue;
        }
        // 种类命名为 i
        cnt[i]++;
        queue<sieve> q;
        q.push(s);
        // cout << "s: " << s.to_string() << endl;
        while (q.size()) {
            auto x = q.front(); q.pop();
            // cout << x.to_string() << endl;
            for (auto &y : vector<sieve>{toUp(x), toDown(x), toLeft(x), toDown(x)}) {
                if (mp.count(y.to_string())) continue;
                mp[y.to_string()] = i;
                q.push(y);
            }
        }
    }
    vector<int> res;
    for (int i = 0; i < n; i++) {
        if (cnt[i] > 0) res.push_back(cnt[i]);
    }
    sort(res.begin(), res.end(), greater<int>());
    cout << res.size() << endl;
    for (auto x : res) {
        cout << x << " ";
    }
}