10.16 字节笔试编程题题解
国庆前做过一次字节笔试，没约我面试。十天后又给我发了个国庆结束的笔试，我没做，前几天又给我发了这场的笔试。真是服了，不知道字节在搞什么鬼。
做的两次都AK了。
// 老规矩，笔试时间结束发题解。
1. 某游戏，每一局需要多个玩家参与。若发现有两玩家同时参与过至少两局游戏，即认为这两个玩家互为队友。
现已知若干玩家(玩家id, int)、若干局游戏（游戏id, int)的历史记录，求某一个指定玩家的所有队友。
第0行输入指定玩家。
第1行输入玩家/游戏记录条数: n (0 <n < 1000000)。
第2 - n+2行输入玩家游戏记录，格式为“玩家id 游戏id”。两个id中间用空格分隔,id 取值范围均为1-10000000。
德州扑克不包含大小王，一共13*4=52张牌，其中A > K > Q > J > 10 > ... > 2。
给你一组牌，让你从其中选出最大的葫芦。
输入一组取值范围为1-13的数，1代表A，11代表J，12代表Q，13代表K
输出最大的牌型，如果找不到输出0，0
数组长度 <= 300，值 <= 1e9。
初始状态给出每个文件夹内部所拥有的文件夹。然后给出一些剪切操作:形如move a b，指将a文件夹移动到b文件夹下(从原所属文件夹中删除)。
题目保证，b文件夹—定不是a文件夹的一个子集。
特殊的，如果b字符串为"."，则代表移动至根目录下。
当所有操作结束后，你需要输出每个文件夹内部的文件夹数量，按文件夹名字字典序排序输出。
输入描述:
第一行输入一个正整数n，代表空文件夹的数量
接下来的n行，每行输入一个字符串,代表每个空文件夹的绝对路径。第n＋1行，输入一个正整数q，代表操作次数。
接下来的q行，每行输入一个形如"move a b"的字符串，代表一次剪切操作。
保证每个文件夹的名字都是长度不超过10的、仅由小写字母组成的字符串。每个文件夹的名字是独一无二的。
保证所有输入的形式都是合法的。
剪切操作保证b文件夹一定不是a文件夹内部的子文件夹。所有文件夹数量不超过10000，操作次数不超过10000。
输出描述:
第一行输出一个正整数m，代表文件夹的总数。
接下来的m行，每行输出一个字符串和一个整数，代表文件夹的名字和其内部文件夹的数量。请保证文件夹的输出顺序是按照名字字典序排序的。
请保证文件夹的输出顺序是按照名字字典序排序的。
#字节跳动笔试##字节笔试#现已知若干玩家(玩家id, int)、若干局游戏（游戏id, int)的历史记录，求某一个指定玩家的所有队友。
第0行输入指定玩家。
第1行输入玩家/游戏记录条数: n (0 <n < 1000000)。
第2 - n+2行输入玩家游戏记录，格式为“玩家id 游戏id”。两个id中间用空格分隔,id 取值范围均为1-10000000。
#include <bits/stdc++.h>
using namespace std;
int main() {
int x; cin >> x;
int n; cin >> n;
// 记录每个人都参加了哪些游戏
unordered_map<int, set<int>> pls; // players
int a, b;
for (int i = 0; i < n; i++) {
cin >> a >> b;
pls[a].insert(b);
}
set<int> ans;
for (auto &p : pls) {
if (p.first == x) continue;
auto it1 = pls[x].begin(), it2 = p.second.begin();
int cnt = 0;
while (it1 != pls[x].end() && it2 != p.second.end()) {
if (*it1 < *it2) it1 ++;
else if (*it1 > *it2) it2 ++;
else {
it1 ++;
it2 ++;
if (++ cnt == 2) {
break;
}
}
}
if (cnt == 2) {
ans.insert(p.first);
}
}
for (auto a : ans) {
printf("%d ", a);
}
return 0;
} 2. 德州扑克里面有一种牌型叫做葫芦，该牌型由5张牌组成，包含3张相同的牌a和两张相同的牌b。德州扑克不包含大小王，一共13*4=52张牌，其中A > K > Q > J > 10 > ... > 2。
给你一组牌，让你从其中选出最大的葫芦。
输入一组取值范围为1-13的数，1代表A，11代表J，12代表Q，13代表K
输出最大的牌型，如果找不到输出0，0
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m; cin >> n >> m;
vector<int> v(n);
for (int i = 0; i < n; i++) cin >> v[i];
vector<int> cnt(14);
for (int x: v) cnt[x] ++;
// a 记录牌数超过 3 张的面值，b 记录牌数为 2 的面值。
// 答案要不都从 a 中取，要不从 a 和 b 中取
vector<int> a, b;
for (int i = 1; i <= 13; i++) {
if (cnt[i] >= 3) a.push_back(i);
else if (cnt[i] == 2) b.push_back(i);
}
// 因为 A > K > Q > J > 10 > .... > 2，将 A 映射成 14 即可直接比较
auto toVal = [] (int x) -> int {
return x == 1 ? 14 : x;
};
// 比较 3张a1 2张a2 和 3张b1 2张b2 哪个牌型大
auto cmp = [&] (int a1, int a2, int b1, int b2) -> bool {
return toVal(a1) > toVal(b1) || (toVal(a1) == toVal(b1) && toVal(a2) > toVal(b2));
};
int ans1 = 0, ans2 = 0;
for (auto x: a) {
for (auto y: a) {
if (x == y) continue;
if (x*3 + y*2 <= m) {
if (!ans1 || cmp(x, y, ans1, ans2)) {
ans1 = x;
ans2 = y;
}
}
}
for (auto y: b) {
if (x*3 + y*2 <= m) {
if (!ans1 || cmp(x, y, ans1, ans2)) {
ans1 = x;
ans2 = y;
}
}
}
}
cout << ans1 << " " << ans2 << endl;
return 0;
} 3. 给你一个整数数组，求能从该数组中选出的最长等差数列的长度。数组长度 <= 300，值 <= 1e9。
#include <bits/stdc++.h>
using namespace std;
// 动态规划
int main() {
int n; cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++) cin >> v[i];
sort(v.begin(), v.end());
vector<vector<int>> f(n, vector<int>(n, 2));
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
for (int k = j+1; k < n; k++) {
if (v[k] - v[j] == v[j] - v[i]) {
f[j][k] = max(f[j][k], f[i][j]+1);
}
}
}
}
int ans = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
ans = max(ans, f[i][j]);
}
}
cout << ans << endl;
return 0;
} 4. 请你实现—个文件移动系统，进行如下操作:初始状态给出每个文件夹内部所拥有的文件夹。然后给出一些剪切操作:形如move a b，指将a文件夹移动到b文件夹下(从原所属文件夹中删除)。
题目保证，b文件夹—定不是a文件夹的一个子集。
特殊的，如果b字符串为"."，则代表移动至根目录下。
当所有操作结束后，你需要输出每个文件夹内部的文件夹数量，按文件夹名字字典序排序输出。
输入描述:
第一行输入一个正整数n，代表空文件夹的数量
接下来的n行，每行输入一个字符串,代表每个空文件夹的绝对路径。第n＋1行，输入一个正整数q，代表操作次数。
接下来的q行，每行输入一个形如"move a b"的字符串，代表一次剪切操作。
保证每个文件夹的名字都是长度不超过10的、仅由小写字母组成的字符串。每个文件夹的名字是独一无二的。
保证所有输入的形式都是合法的。
剪切操作保证b文件夹一定不是a文件夹内部的子文件夹。所有文件夹数量不超过10000，操作次数不超过10000。
输出描述:
第一行输出一个正整数m，代表文件夹的总数。
接下来的m行，每行输出一个字符串和一个整数，代表文件夹的名字和其内部文件夹的数量。请保证文件夹的输出顺序是按照名字字典序排序的。
请保证文件夹的输出顺序是按照名字字典序排序的。
#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
string name;
TreeNode *fa;
unordered_set<TreeNode*> son;
TreeNode(string s): name(s), fa(nullptr) {}
TreeNode(string s, TreeNode *fa): name(s), fa(fa) {}
void addSon(TreeNode *node) {
son.insert(node);
node->fa->son.erase(node);
node->fa = this;
}
};
map<string, int> ans;
int calSon(TreeNode *root) {
int total = root->son.size();
for (auto s: root->son) {
total += calSon(s);
}
ans[root->name] = total;
return total;
}
int main() {
int n; cin >> n;
string s, t, pre;
unordered_map<string, TreeNode*> mp;
for (int i = 0; i < n; i++) {
cin >> s;
t.clear();
pre.clear();
for (int j = 0, jend = s.length(); j <= jend; j ++) {
if (j == jend || s[j] == '/') {
if (!mp.count(t)) {
mp[t] = new TreeNode(t, pre.empty() ? nullptr : mp[pre]);
if (!pre.empty()) {
mp[pre]->son.insert(mp[t]);
}
}
pre = t;
t.clear();
} else {
t += s[j];
}
}
}
int q; cin >> q;
string a, b, _;
while (q --) {
cin >> _ >> a >> b;
mp[b]->addSon(mp[a]);
}
_ = calSon(mp["."]);
cout << ans.size()-1 << endl;
for (auto &p : ans) {
if (p.first == ".") continue;
cout << p.first << " " << p.second << endl;
}
return 0;
} 
不过现在还叫我笔试，也不知道啥意思
