首页 > 美团9.6开发笔试(C++,全AC)
头像
js8544
编辑于 2020-09-06 12:22
+ 关注

美团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
我们如果竖着看,就发现对于某个j,它这列是循环的0到j-1,完整循环了n/j次,剩余n%j个没求。
我们可以用前缀和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,如果还不过就是算法的问题了。








全部评论

(29) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐