美团9.6开发笔试（C++，全AC）
1. 给出A，B两国想要的土地，输出只有A国想要的土地数，只有B国想要的土地数，两个国家都想要的土地数。
思路：简单的求交集大小，甚至不用给出交集，先遍历A，用set存下来，再遍历B，遇到set中有的就cnt++，最后输出A-cnt, B-cnt, cnt
int n, p, q;
set<int> a;
void solve() {
cin >> n >> p >> q;
for (int i = 0; i < p; i++) {
int x;
cin >> x;
a.insert(x);
}
int cnt = 0;
for (int i = 0; i < q; i++) {
int x;
cin >> x;
if (a.count(x)) cnt++;
}
cout<<p - cnt<<" "<<q - cnt<<" "<<cnt<<endl;
} 2. 给一串偶数个字符，只有大小写字母，求修改多少个字母可以让大小写数量相同。 思路：求出大小写个数，相减除以二即可。用islower判断大小写。
int n;
void solve() {
char c;
int l = 0, u = 0;
while (cin >> c) {
if (islower(c)) {
l++;
} else {
u++;
}
}
cout<<abs(l - u) / 2<<endl;
} 3. 给数组A，定义数组B为 思路：观察到异或的两个性质：1. 可交换 2. 任何数异或自身为零。观察到mod的一个性质：循环。因此我们可以竖着求，而不是横着求。也就是我们遍历j去求，而不是i。
举例：n=5时，我们要求的一串异或是：
| i\j | | 1 | 2 | 3 | 4 | 5 |
| b1= | a1 | 0 | 1 | 1 | 1 | 1 |
| b2= | a2 | 0 | 0 | 2 | 2 | 2 |
| b3= | a3 | 0 | 1 | 0 | 3 | 3 |
| b4= | a4 | 0 | 0 | 1 | 0 | 4 |
| b5= | a5 | 0 | 1 | 2 | 1 | 0 |
我们可以用前缀和pre数组来保存0到j的异或和，然后对每个j，如果n/j是偶数，那么互相抵消掉，不需要计算，如果为奇数次，则ans异或一次pre[j-1]。另外需要加上剩下的pre[n%j]。
最后加上异或a1到an即可。
int n;
int pre[100001];
void solve() {
cin >> n;
pre[0] = 0;
for (int i = 1; i <= n; i++) {
pre[i] = pre[i - 1] ^ i;
}
int ans = 0;
for (int i = 1; i <= n; i++) {
ans ^= pre[n % i];
if ((n / i) % 2) {
ans ^= pre[i - 1];
}
}
for (int i = 0; i < n; i++) {
int x;
cin >> x;
ans ^= x;
}
cout << ans << endl;
} 4. 给出一串子树的节点个数（包含自身），求是否能构成合法树，要求每个非叶节点至少有两个子节点。 思路：n=24明显提示我们是dfs+剪枝，先把输入从大到小排序。
首先预检查：1. arr[0]必须等于n 2. arr[i]不能等于2
然后dfs：
1. arr[i]表示i剩下多少总子节点未分配。child[i]表示i目前分配了多少子节点。set<int> can （candidate）存有子节点未分配的节点（即arr[i]大于1的所有i）。
2. 从x=1开始dfs，每轮dfs去找can中的节点i，如果arr[i] > arr[x]，（且不满足（arr[i] - arr[x] == 1 && child[i]==0)，不然i就只能分配x一个子节点，这是不超时的关键。），则把x当成i的字节点，然后去试dfs(x+1).
3. 直到x=n，检查是否所有arr[i]==1 && child[i] != 1，arr[i]=1因为最后只剩下自己没分配出去。
int n;
int arr[25];
int child[25];
bool dfs(int x, set<int>& can) {
if (x == n) {
for (int i = 0; i < n; i++) {
if (arr[i] != 1 || child[i] == 1) return false;
}
return true;
}
set<int> new_can = can;
if (arr[x] != 1) new_can.insert(x);
for (int i : can) {
if (arr[i] > arr[x]) {
if (arr[i] == arr[x] + 1 && child[i] == 0) continue;
arr[i] -= arr[x];
child[i]++;
if (arr[i] == 1) new_can.erase(i);
if (dfs(x + 1, new_can)) return true;
if (arr[i] == 1) new_can.insert(i);
arr[i] += arr[x];
child[i]--;
}
}
return false;
}
void solve() {
bool flag = true;
REP(i, n) {
cin >> arr[i];
if (arr[i] == 2) {
flag = false;
}
}
if (!flag) {
cout << "NO" << endl;
return;
}
sort(arr, arr + n, greater<int>());
if (arr[0] != n) {
cout << "NO" << endl;
return;
}
set<int> can;
can.insert(0);
memset(child, 0, sizeof(child));
if (dfs(1, can)) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
} 5. 还有个后台开发的专项：点名：点到谁就把谁放到队列最前
思路：倒着数即可，某个数出现的最后一次是他的实际排序，前面的点名完全被覆盖掉，没卵用。用一个unordered_set存一下出现过的数，出现过就直接跳过，没出现过就print出来。
int n;
int arr[100001];
unordered_set<int> st;
void solve() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
for (int i = n - 1; i >= 0; i--) {
if (st.count(arr[i])) continue;
cout<<arr[i]<<endl;
st.insert(arr[i]);
}
} 另外给大家分享一下让cin，cout更快的技巧防止被卡io，在main里加上：
ios::sync_with_stdio(0); cin.tie(0);这两行，然后尽量用"\n"而不是endl（我发帖之前把我的\n都改成endl因为看起来好看）。这样保证是所有语言，所有写法最快的io，如果还不过就是算法的问题了。
阿里云成长空间 743人发布
投递小天才等公司10个岗位