淘天笔试,中规中矩(0325秋招笔试真题解析)

3 3 2 5 2 7 4 3 0 0 0 0 2 5 10 1

6 80 02 3

#include <bits/stdc++.h>using namespace std;int main() {    ios::sync_with_stdio(false);    cin.tie(nullptr);    int T;    cin >> T;while (T--) {        int n;        long long k;        cin >> n >> k;        long long mn = 0, mx = 0;for (int i = 0; i < n; i++) {            long long cnt;            cin >> cnt;            mn += cnt / k;            mx += cnt / k;if (cnt % k) mx++;        }        cout << mn << ' ' << mx << '\n';    }return 0;}

第二题

在线做题链接：https://niumacode.com/

题意

给定两个长度为 n 的排列 p 和 q（均为 1∼n 的排列，元素两两不同），请在它们的公共子序列中，找到字典序最大的序列并输出。

输入描述

第一行输入一个整数 n (1≤n≤2×10^5)，表示排列的长度。 第二行输入 n 个整数 p1,p2,…,pn，表示排列 p。 第三行输入 n 个整数 q1,q2,…,qn，表示排列 q。 保证 p 与 q 都是 1∼n 的排列。

输出描述

第一行输出一个整数 k，表示答案序列的长度。 第二行输出 k 个整数，为这条字典序最大的公共子序列。

示例1：

输入：

52 5 3 1 45 2 4 3 1

输出：

25 4

说明： 两序列的公共子序列中，以 5 开头后，能够继续选择的最大元素为 4，得到 [5,4]。与 [5,1] 相比，第二个元素更大，因此 [5,4] 字典序更大。

思路与代码

因为 p 和 q 都是排列，每个数只出现一次，所以公共子序列本质上只和“相对顺序”有关。 要让字典序最大，就要优先让前面的数尽量大，因此可以从大到小枚举数值 v。如果 v 在两个排列中的位置都还在当前答案末尾之后，就可以把它加入答案。这样贪心选出来的序列就是字典序最大的公共子序列。

#include <bits/stdc++.h>using namespace std;int main() {    ios::sync_with_stdio(false);    cin.tie(nullptr);    int n;    cin >> n;    vector<int> p(n), q(n);    vector<int> pos_p(n + 1), pos_q(n + 1);for (int i = 0; i < n; i++) {        cin >> p[i];        pos_p[p[i]] = i;    }for (int i = 0; i < n; i++) {        cin >> q[i];        pos_q[q[i]] = i;    }    int last_p = -1, last_q = -1;    vector<int> ans;for (int val = n; val >= 1; val--) {if (pos_p[val] > last_p && pos_q[val] > last_q) {            ans.push_back(val);            last_p = pos_p[val];            last_q = pos_q[val];        }    }    cout << ans.size() << '\n';for (int i = 0; i < (int)ans.size(); i++) {if (i) cout << ' ';        cout << ans[i];    }    cout << '\n';return 0;}

第三题

在线做题链接：https://niumacode.com/

题意

Tk 不喜欢能被 3 整除的正整数，也不喜欢十进制表示中包含数字‘3’的正整数。现在他要将所有他喜欢的正整数按升序排成一个序列。给定正整数 k，请你找出这个序列的第 k 个数。 友情提醒：第 10¹⁸ + 1 项为 10 995 467 216 611 448 857

输入描述

第一行输入一个整数 t (1 ≤ t ≤ 10⁴)，表示测试用例的数量； 接下来 t 行，每行输入一个整数 k (1 ≤ k ≤ 10¹⁸)，表示要找的第 k 个喜欢的正整数的序号。

输出描述

对于每个测试用例，在一行上输出一个整数，表示所求的第 k 个喜欢的正整数。

示例：

输入：

512345

输出：

12457

说明： 在这个样例中，喜欢的正整数序列的前五项为 1, 2, 4, 5, 7，因此对应输出分别为 1, 2, 4, 5, 7。

思路与代码

一个数要合法，需要同时满足两件事：十进制中不含数字 3，并且 整个数不能被 3 整除。 由于 k 很大，不能一个个枚举。做法是先用数位 DP 预处理：对于“还剩多少位、当前模 3 余数是多少”，后面能接出多少个合法方案。然后按位从高到低贪心尝试当前位填什么数字，判断这一位选定后后缀还能提供多少合法数，从而一步步定位到第 k 个答案。

#include <bits/stdc++.h>using namespace std;using i64 = long long;const i64 INF = (i64)4e18;i64 add(i64 a, i64 b) {if (a >= INF - b) return INF;return a + b;}int main() {    ios::sync_with_stdio(false);    cin.tie(nullptr);    int T;    cin >> T;    vector<i64> query(T);    i64 max_k = 0;for (int i = 0; i < T; i++) {        cin >> query[i];        max_k = max(max_k, query[i]);    }    vector<int> digit = {0, 1, 2, 4, 5, 6, 7, 8, 9};    vector<int> first_digit = {1, 2, 4, 5, 6, 7, 8, 9};    vector<array<i64, 3>> f;    f.push_back({1, 0, 0});    vector<i64> sum;    sum.push_back(0);while (sum.back() < max_k) {        array<i64, 3> nxt = {0, 0, 0};        auto pre = f.back();for (int mod = 0; mod < 3; mod++) {for (int x : digit) {                int nmod = (mod + x) % 3;                nxt[nmod] = add(nxt[nmod], pre[mod]);            }        }        f.push_back(nxt);        int len = (int)f.size() - 1;        i64 cnt = 0;for (int x : first_digit) {            int head_mod = x % 3;for (int tail_mod = 0; tail_mod < 3; tail_mod++) {if ((head_mod + tail_mod) % 3 != 0) {                    cnt = add(cnt, f[len - 1][tail_mod]);                }            }        }        sum.push_back(add(sum.back(), cnt));    }    int max_len = (int)f.size() - 1;    vector<array<i64, 3>> g(max_len + 1);for (int len = 0; len <= max_len; len++) {for (int mod = 0; mod < 3; mod++) {            i64 cnt = 0;for (int tail_mod = 0; tail_mod < 3; tail_mod++) {if ((mod + tail_mod) % 3 != 0) {                    cnt = add(cnt, f[len][tail_mod]);                }            }            g[len][mod] = cnt;        }    }for (i64 k : query) {        int left = 1, right = max_len;while (left < right) {            int mid = (left + right) >> 1;if (sum[mid] >= k) right = mid;else left = mid + 1;        }        int len = left;        k -= sum[len - 1];        int cur_mod = 0;        string ans;for (int pos = 1; pos <= len; pos++) {            int rest = len - pos;            const vector<int>& cand = (pos == 1 ? first_digit : digit);for (int x : cand) {                int nmod = (cur_mod + x) % 3;                i64 cnt = g[rest][nmod];if (k > cnt) {                    k -= cnt;                } else {                    ans.push_back(char('0' + x));                    cur_mod = nmod;break;                }            }        }        cout << ans << '\n';    }return 0;}

前言

文末给大家推荐一下我们的活动，针对校招笔面试全覆盖的全程真一对一的提高，参加活动前会给你安排一个全面的摸底，摸底后会针对你的情况进行分析和对于参加活动的介绍，然后你再决定是否参加!

在线做题链接：https://niumacode.com/

这套笔试题目设计的还是比较合理的，难度逐级递增，这样的形式大家就还是比较有参与感。

• 第一题（糖果分配极值）：利用贪心与整除取余思想，洞察到在“差值不超过1”的限制下，每种糖果对个体的极值贡献是固定的。直接将基础份额（下取整）与余数分配（上取整）分别累加，即可在  时间内锁定最小与最大糖果总数。
• 第二题（最大字典序公共子序列）：巧妙利用“排列无重复元素”的特性，将问题转化为基于坐标单调性的贪心选择。从大到小逆向枚举所有数值，只要其在双数组中的下标均严格落后于当前序列末尾，即可无脑压入答案，绝对保证字典序最大。
• 第三题（第k个喜欢数）：采用数位 DP 与前缀和预处理，按“剩余长度”与“模3余数”统计出所有不含‘3’且不被3整除的合法方案数。面对高达  的  值，通过“从高位到低位贪心试填”并动态扣减非目标区间的方案数，精准定位出第  个解。

第一题

在线做题链接：https://niumacode.com/

题意

圣诞老人有 n 种糖果，第 i 种糖果有 cᵢ个。他要把这些糖果分给 k 个小朋友。分配规则如下： 每一种糖果必须全部分完； 对于任意一种糖果，任意两个小朋友所分得的该种糖果的数量之差不超过 1。 在所有合法分配中，任选一个小朋友，统计其最终得到的糖果总数；求该数值在所有合法分配中可能达到的最小值与最大值。 换句话说，求在所有合法分配方案中，任意一个小朋友所能获得的糖果总数的最小值与最大值。

输入描述

每个测试文件均包含多组测试数据，第一行输入一个整数 T (1 ≤ T ≤ 2×10⁵) 代表数据组数，每组测试数据描述如下： 第一行输入两个整数 n, k (1 ≤ n ≤ 2×10⁵, 1 ≤ k ≤ 10⁹)； 第二行输入 n 个整数 c₁,…,cₙ (0 ≤ cᵢ ≤ 10⁹)。 除此之外，保证单个测试文件的 n 之和不超过 5×10⁵。

输出描述

对于每组测试数据，输出两个整数：在所有合法分配中，单个小朋友可能得到的糖果总数的最小值与最大值。

示例1：

输入：

3 3 2 5 2 7 4 3 0 0 0 0 2 5 10 1

输出：

6 80 02 3

解释： 分割最终区间为 [1, 3], [4, 5] 可以得到最大值54

思路与代码

对某一种糖果，设数量为 cnt。因为要求任意两个小朋友分到的该种糖果数量差不超过 1，所以每个人拿到的数量只可能是 cnt / k 或 cnt / k + 1。 因此，对某个固定小朋友来说，这一类糖果贡献的最小值是 cnt / k，最大值是 cnt / k + (cnt % k != 0)。把所有种类逐个累加即可。

#include <bits/stdc++.h>using namespace std;int main() {    ios::sync_with_stdio(false);    cin.tie(nullptr);    int T;    cin >> T;while (T--) {        int n;        long long k;        cin >> n >> k;        long long mn = 0, mx = 0;for (int i = 0; i < n; i++) {            long long cnt;            cin >> cnt;            mn += cnt / k;            mx += cnt / k;if (cnt % k) mx++;        }        cout << mn << ' ' << mx << '\n';    }return 0;}

第二题

在线做题链接：https://niumacode.com/

题意

给定两个长度为 n 的排列 p 和 q（均为 1∼n 的排列，元素两两不同），请在它们的公共子序列中，找到字典序最大的序列并输出。

输入描述

第一行输入一个整数 n (1≤n≤2×10^5)，表示排列的长度。 第二行输入 n 个整数 p1,p2,…,pn，表示排列 p。 第三行输入 n 个整数 q1,q2,…,qn，表示排列 q。 保证 p 与 q 都是 1∼n 的排列。

输出描述

第一行输出一个整数 k，表示答案序列的长度。 第二行输出 k 个整数，为这条字典序最大的公共子序列。

示例1：

输入：

52 5 3 1 45 2 4 3 1

输出：

25 4

说明： 两序列的公共子序列中，以 5 开头后，能够继续选择的最大元素为 4，得到 [5,4]。与 [5,1] 相比，第二个元素更大，因此 [5,4] 字典序更大。

思路与代码

因为 p 和 q 都是排列，每个数只出现一次，所以公共子序列本质上只和“相对顺序”有关。 要让字典序最大，就要优先让前面的数尽量大，因此可以从大到小枚举数值 v。如果 v 在两个排列中的位置都还在当前答案末尾之后，就可以把它加入答案。这样贪心选出来的序列就是字典序最大的公共子序列。

#include <bits/stdc++.h>using namespace std;int main() {    ios::sync_with_stdio(false);    cin.tie(nullptr);    int n;    cin >> n;    vector<int> p(n), q(n);    vector<int> pos_p(n + 1), pos_q(n + 1);for (int i = 0; i < n; i++) {        cin >> p[i];        pos_p[p[i]] = i;    }for (int i = 0; i < n; i++) {        cin >> q[i];        pos_q[q[i]] = i;    }    int last_p = -1, last_q = -1;    vector<int> ans;for (int val = n; val >= 1; val--) {if (pos_p[val] > last_p && pos_q[val] > last_q) {            ans.push_back(val);            last_p = pos_p[val];            last_q = pos_q[val];        }    }    cout << ans.size() << '\n';for (int i = 0; i < (int)ans.size(); i++) {if (i) cout << ' ';        cout << ans[i];    }    cout << '\n';return 0;}

第三题

在线做题链接：https://niumacode.com/

题意

Tk 不喜欢能被 3 整除的正整数，也不喜欢十进制表示中包含数字‘3’的正整数。现在他要将所有他喜欢的正整数按升序排成一个序列。给定正整数 k，请你找出这个序列的第 k 个数。 友情提醒：第 10¹⁸ + 1 项为 10 995 467 216 611 448 857

输入描述

第一行输入一个整数 t (1 ≤ t ≤ 10⁴)，表示测试用例的数量； 接下来 t 行，每行输入一个整数 k (1 ≤ k ≤ 10¹⁸)，表示要找的第 k 个喜欢的正整数的序号。

输出描述

对于每个测试用例，在一行上输出一个整数，表示所求的第 k 个喜欢的正整数。

示例：

输入：

512345

输出：

12457

说明： 在这个样例中，喜欢的正整数序列的前五项为 1, 2, 4, 5, 7，因此对应输出分别为 1, 2, 4, 5, 7。

思路与代码

一个数要合法，需要同时满足两件事：十进制中不含数字 3，并且 整个数不能被 3 整除。 由于 k 很大，不能一个个枚举。做法是先用数位 DP 预处理：对于“还剩多少位、当前模 3 余数是多少”，后面能接出多少个合法方案。然后按位从高到低贪心尝试当前位填什么数字，判断这一位选定后后缀还能提供多少合法数，从而一步步定位到第 k 个答案。

#include <bits/stdc++.h>using namespace std;using i64 = long long;const i64 INF = (i64)4e18;i64 add(i64 a, i64 b) {if (a >= INF - b) return INF;return a + b;}int main() {    ios::sync_with_stdio(false);    cin.tie(nullptr);    int T;    cin >> T;    vector<i64> query(T);    i64 max_k = 0;for (int i = 0; i < T; i++) {        cin >> query[i];        max_k = max(max_k, query[i]);    }    vector<int> digit = {0, 1, 2, 4, 5, 6, 7, 8, 9};    vector<int> first_digit = {1, 2, 4, 5, 6, 7, 8, 9};    vector<array<i64, 3>> f;    f.push_back({1, 0, 0});    vector<i64> sum;    sum.push_back(0);while (sum.back() < max_k) {        array<i64, 3> nxt = {0, 0, 0};        auto pre = f.back();for (int mod = 0; mod < 3; mod++) {for (int x : digit) {                int nmod = (mod + x) % 3;                nxt[nmod] = add(nxt[nmod], pre[mod]);            }        }        f.push_back(nxt);        int len = (int)f.size() - 1;        i64 cnt = 0;for (int x : first_digit) {            int head_mod = x % 3;for (int tail_mod = 0; tail_mod < 3; tail_mod++) {if ((head_mod + tail_mod) % 3 != 0) {                    cnt = add(cnt, f[len - 1][tail_mod]);                }            }        }        sum.push_back(add(sum.back(), cnt));    }    int max_len = (int)f.size() - 1;    vector<array<i64, 3>> g(max_len + 1);for (int len = 0; len <= max_len; len++) {for (int mod = 0; mod < 3; mod++) {            i64 cnt = 0;for (int tail_mod = 0; tail_mod < 3; tail_mod++) {if ((mod + tail_mod) % 3 != 0) {                    cnt = add(cnt, f[len][tail_mod]);                }            }            g[len][mod] = cnt;        }    }for (i64 k : query) {        int left = 1, right = max_len;while (left < right) {            int mid = (left + right) >> 1;if (sum[mid] >= k) right = mid;else left = mid + 1;        }        int len = left;        k -= sum[len - 1];        int cur_mod = 0;        string ans;for (int pos = 1; pos <= len; pos++) {            int rest = len - pos;            const vector<int>& cand = (pos == 1 ? first_digit : digit);for (int x : cand) {                int nmod = (cur_mod + x) % 3;                i64 cnt = g[rest][nmod];if (k > cnt) {                    k -= cnt;                } else {                    ans.push_back(char('0' + x));                    cur_mod = nmod;break;                }            }        }        cout << ans << '\n';    }return 0;}

我们是一个针对技术岗（前后端开发、测试、测开、大数据开发、大模型、ai等相关岗位）校招一对一进阶提高的工作室。我们从2020年2月份开始，迄今整整六年的时间，带领900+学员斩获4000+中大厂offer，参加活动的同学人均5个中大厂offer以上，以下是我们活动内容的介绍！

万诺coding

我们主要是针对有一定基础的同学提供全程一对一笔试、面试辅导，针对每个同学不同的情况定制内容，包括但不限于“笔试及面试算法”/“基础八股/“项目及实习梳理”/“面试技巧”/“面试复盘”等内容。

摸底测试：如果有兴趣深入了解我们的活动，需要先参加我们的“摸底测试”（类似面试），方便我们了解你的具体情况（主要是code能力和计算机素养），定制出相应的辅导计划。摸底测试后，我们会定制化一个针对性的提高计划。然后你再考虑是否参加我们的活动。 

承诺保offer：通过摸底测试后，我们会针对每个同学的情况给定一个“保offer”计划。然后同学可以根据自己的实际情况考虑参不参加我们的活动。

有兴趣的同学可以扫码添加我们的微信（whynotlab）