2020.08.02 拼多多算法工程师 笔试题解

第一题（100%）按题意模拟，注意第N次到的话特判，否则只能过96%

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

int k, n;
int x;

signed main() {
  // freopen("in", "r", stdin);
  // freopen("out", "w", stdout);
  while (~scanf("%d%d", &k, &n)) {
    int cur = 0, cnt = 0;
    int ok = 0;
    for (int i = 1; i <= n; i++) {
      scanf("%d", &x);
      if (ok) continue;
      if (cur + x == k) {
        if(n != i) ok = 1;
        cur += x;
      } else if (cur + x > k) {
        cnt++;
        cur = k - (cur + x - k);
      } else {
        cur += x;
      }
    }
    if (ok || k == 0) {
      printf("paradox\n");
    } else {
      printf("%d %d\n", k - cur, cnt);
    }
  }
  return 0;
}

第二题（100%）我是枚举了24种同构+并查集做的，一定有聪明的小朋友写出了预处理。

#include <bits/stdc++.h>

using namespace std;
using LL = long long;
#define A 1
#define B 2
#define C 3
#define D 4
#define E 5
#define F 6

const int maxn = 1010;
int n;
int dice[maxn][7];
int pre[maxn];

int find(int x) {
  return x == pre[x] ? x : pre[x] = find(pre[x]);
}

void unite(int x, int y) {
  x = find(x); y = find(y);
  pre[x] = y;
}

int check(int x, int y) {
  if (dice[x][1]==dice[y][A]&&dice[x][2]==dice[y][B]&&dice[x][3]==dice[y][C]&&dice[x][4]==dice[y][D]&&dice[x][5]==dice[y][E]&&dice[x][6]==dice[y][F]) return 1;
  if (dice[x][1]==dice[y][C]&&dice[x][2]==dice[y][D]&&dice[x][3]==dice[y][B]&&dice[x][4]==dice[y][A]&&dice[x][5]==dice[y][E]&&dice[x][6]==dice[y][F]) return 1;
  if (dice[x][1]==dice[y][B]&&dice[x][2]==dice[y][A]&&dice[x][3]==dice[y][D]&&dice[x][4]==dice[y][C]&&dice[x][5]==dice[y][E]&&dice[x][6]==dice[y][F]) return 1;
  if (dice[x][1]==dice[y][D]&&dice[x][2]==dice[y][C]&&dice[x][3]==dice[y][A]&&dice[x][4]==dice[y][B]&&dice[x][5]==dice[y][E]&&dice[x][6]==dice[y][F]) return 1;

  if (dice[x][1]==dice[y][A]&&dice[x][2]==dice[y][B]&&dice[x][3]==dice[y][D]&&dice[x][4]==dice[y][C]&&dice[x][5]==dice[y][F]&&dice[x][6]==dice[y][E]) return 1;
  if (dice[x][1]==dice[y][C]&&dice[x][2]==dice[y][D]&&dice[x][3]==dice[y][A]&&dice[x][4]==dice[y][B]&&dice[x][5]==dice[y][F]&&dice[x][6]==dice[y][E]) return 1;
  if (dice[x][1]==dice[y][B]&&dice[x][2]==dice[y][A]&&dice[x][3]==dice[y][C]&&dice[x][4]==dice[y][D]&&dice[x][5]==dice[y][F]&&dice[x][6]==dice[y][E]) return 1;
  if (dice[x][1]==dice[y][D]&&dice[x][2]==dice[y][C]&&dice[x][3]==dice[y][B]&&dice[x][4]==dice[y][A]&&dice[x][5]==dice[y][F]&&dice[x][6]==dice[y][E]) return 1;

  if (dice[x][1]==dice[y][A]&&dice[x][2]==dice[y][B]&&dice[x][3]==dice[y][F]&&dice[x][4]==dice[y][E]&&dice[x][5]==dice[y][C]&&dice[x][6]==dice[y][D]) return 1;
  if (dice[x][1]==dice[y][F]&&dice[x][2]==dice[y][E]&&dice[x][3]==dice[y][B]&&dice[x][4]==dice[y][A]&&dice[x][5]==dice[y][C]&&dice[x][6]==dice[y][D]) return 1;
  if (dice[x][1]==dice[y][B]&&dice[x][2]==dice[y][A]&&dice[x][3]==dice[y][E]&&dice[x][4]==dice[y][F]&&dice[x][5]==dice[y][C]&&dice[x][6]==dice[y][D]) return 1;
  if (dice[x][1]==dice[y][E]&&dice[x][2]==dice[y][F]&&dice[x][3]==dice[y][A]&&dice[x][4]==dice[y][B]&&dice[x][5]==dice[y][C]&&dice[x][6]==dice[y][D]) return 1;

  if (dice[x][1]==dice[y][A]&&dice[x][2]==dice[y][B]&&dice[x][3]==dice[y][E]&&dice[x][4]==dice[y][F]&&dice[x][5]==dice[y][D]&&dice[x][6]==dice[y][C]) return 1;
  if (dice[x][1]==dice[y][E]&&dice[x][2]==dice[y][F]&&dice[x][3]==dice[y][B]&&dice[x][4]==dice[y][A]&&dice[x][5]==dice[y][D]&&dice[x][6]==dice[y][C]) return 1;
  if (dice[x][1]==dice[y][B]&&dice[x][2]==dice[y][A]&&dice[x][3]==dice[y][F]&&dice[x][4]==dice[y][E]&&dice[x][5]==dice[y][D]&&dice[x][6]==dice[y][C]) return 1;
  if (dice[x][1]==dice[y][F]&&dice[x][2]==dice[y][E]&&dice[x][3]==dice[y][A]&&dice[x][4]==dice[y][B]&&dice[x][5]==dice[y][D]&&dice[x][6]==dice[y][C]) return 1;

  if (dice[x][1]==dice[y][F]&&dice[x][2]==dice[y][E]&&dice[x][3]==dice[y][C]&&dice[x][4]==dice[y][D]&&dice[x][5]==dice[y][A]&&dice[x][6]==dice[y][B]) return 1;
  if (dice[x][1]==dice[y][C]&&dice[x][2]==dice[y][D]&&dice[x][3]==dice[y][E]&&dice[x][4]==dice[y][F]&&dice[x][5]==dice[y][A]&&dice[x][6]==dice[y][B]) return 1;
  if (dice[x][1]==dice[y][E]&&dice[x][2]==dice[y][F]&&dice[x][3]==dice[y][D]&&dice[x][4]==dice[y][C]&&dice[x][5]==dice[y][A]&&dice[x][6]==dice[y][B]) return 1;
  if (dice[x][1]==dice[y][D]&&dice[x][2]==dice[y][C]&&dice[x][3]==dice[y][F]&&dice[x][4]==dice[y][E]&&dice[x][5]==dice[y][A]&&dice[x][6]==dice[y][B]) return 1;

  if (dice[x][1]==dice[y][E]&&dice[x][2]==dice[y][F]&&dice[x][3]==dice[y][C]&&dice[x][4]==dice[y][D]&&dice[x][5]==dice[y][B]&&dice[x][6]==dice[y][A]) return 1;
  if (dice[x][1]==dice[y][D]&&dice[x][2]==dice[y][C]&&dice[x][3]==dice[y][E]&&dice[x][4]==dice[y][F]&&dice[x][5]==dice[y][B]&&dice[x][6]==dice[y][A]) return 1;
  if (dice[x][1]==dice[y][F]&&dice[x][2]==dice[y][E]&&dice[x][3]==dice[y][D]&&dice[x][4]==dice[y][C]&&dice[x][5]==dice[y][B]&&dice[x][6]==dice[y][A]) return 1;
  if (dice[x][1]==dice[y][C]&&dice[x][2]==dice[y][D]&&dice[x][3]==dice[y][F]&&dice[x][4]==dice[y][E]&&dice[x][5]==dice[y][B]&&dice[x][6]==dice[y][A]) return 1;

  return 0;
}

signed main() {
  // freopen("in", "r", stdin);
  // freopen("out", "w", stdout);
  while (~scanf("%d", &n)) {
    for (int i = 1; i <= n; i++) {
      pre[i] = i;
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= 6; j++) {
        scanf("%d", &dice[i][j]);
      }
    }
    for (int i = 1; i <= n; i++) {
      for (int j = i + 1; j <= n; j++) {
        if (check(i, j)) unite(i, j);
      }
    }
    int ret1 = 0;
    for (int i = 1; i <= n; i++) {
      if (i == find(i)) ret1++;
    }
    printf("%d\n", ret1);
    map<int, int> vis;
    for (int i = 1; i <= n; i++) {
      vis[find(i)]++;
    }
    vector<int> ret2;
    for (const auto &x : vis) {
      ret2.emplace_back(x.second);
    }
    sort(ret2.begin(), ret2.end(), greater<int>());
    for (int i = 0; i < ret2.size(); i++) {
      printf("%d%c", ret2[i], " \n"[i == ret2.size() - 1]);
    }
  }
  return 0;
}

贴一下枚举的图吧。。
图片说明

第三题（100%）按美味程度、能量数的顺序从小到大排序，然后枚举lunch，二分dinner的美味程度，更新答案。记得单独讨论只吃一顿或者一顿都不吃的情况。

#include <bits/stdc++.h>

using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int maxn = 100100;
int n, m, t;
pii lunch[maxn], dinner[maxn];
int suf[maxn];

signed main() {
  // freopen("in", "r", stdin);
  // freopen("out", "w", stdout);
  while (~scanf("%d%d%d",&n,&m,&t)) {
    for (int i = 1; i <= n; i++) {
      scanf("%d%d",&lunch[i].second, &lunch[i].first);
    }
    for (int i = 1; i <= m; i++) {
      scanf("%d%d",&dinner[i].second, &dinner[i].first);
    }
    if (t == 0) {
      printf("0\n");
      continue;
    }
    sort(lunch + 1, lunch + n + 1);
    sort(dinner + 1, dinner + m + 1);
    int ret = INT_MAX;
    for (int i = 1; i <= n; i++) {
      if (lunch[i].first >= t) ret = min(ret, lunch[i].second);
    }
    for (int i = 1; i <= m; i++) {
      if (dinner[i].first >= t) ret = min(ret, dinner[i].second);
      suf[i] = dinner[i].second;
    }
    for (int i = m - 1; i >= 1; i--) {
      suf[i] = min(suf[i + 1], suf[i]);
    }
    for (int i = 1; i <= n; i++) {
      if (lunch[i].first >= t) continue;
      int require = t - lunch[i].first;
      if (dinner[m].first < require) continue;
      int lo = 1, hi = m;
      while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        if (dinner[mid].first >= require) {
          ret = min(ret, suf[mid] + lunch[i].second);
          hi = mid - 1;
        } else {
          lo = mid + 1;
        }
      }
    }
    printf("%d\n", ret == INT_MAX ? -1 : ret);
  }
  return 0;
}

第四题（20%）我读错题了，我以为就6个'#'. 所以我写了个预处理暴力。正解插头DP

#include <bits/stdc++.h>

using namespace std;
using LL = long long;
using pii = pair<int, int>;

const LL mod = 1E9 + 9;
const int dx[5] = {0, 0, 1, -1};
const int dy[5] = {1, -1, 0, 0};
const int maxn = 7;
char s[maxn][maxn];
vector<pii> pos;
int n = 6, m = 6;
LL ret;

vector<vector<int>> status;
vector<int> tmp;

void pre(int cnt, int cap) {
  if (cnt == min((int)pos.size() + 1, 7)) {
    status.emplace_back(tmp);
    return;
  }
  for (int i = 1; i <= 6; i++) {
    // if (i == cap) continue;
    tmp.emplace_back(i);
    pre(cnt + 1, i);
    tmp.pop_back();
  }
}

int check(int x, int y) {
  return x >= 1 && x <= 6 && y >= 1 && y <= 6;
}

int ok() {
  for (int i = 1; i <= 6; i++) {
    for (int j = 1; j <= 6; j++) {
      for (int k = 0; k < 4; k++) {
        int x = i + dx[k];
        int y = j + dy[k];
        if (!check(x, y)) continue;
        if (s[i][j] == '*') continue;
        if (s[x][y] == s[i][j]) return 0;
      }
    }
  }
  return 1;
}

signed main() {
  // freopen("in", "r", stdin);
  // freopen("out", "w", stdout);
  pos.clear();
  for (int i = 1; i <= 6; i++) {
    scanf("%s", s[i] + 1);
    for (int j = 1; j <= 6; j++) {
      if (s[i][j] == '#') pos.emplace_back(i, j);
    }
  }

  tmp.clear();
  status.clear();
  pre(1, -1);

  for (int i = 0; i < status.size(); i++) {
    for (int j = 0; j < pos.size(); j++) {
      int x = pos[j].first, y = pos[j].second;
      s[x][y] = status[i][j] + '0';
    }
    if (ok()) {
      ret++;
      if (ret >= mod) ret %= mod;
    }
    for (int j = 0; j < pos.size(); j++) {
      int x = pos[j].first, y = pos[j].second;
      s[x][y] = '#';
    }
  }
  printf("%lld\n", ret);
  return 0;
}
#笔试题目##校招##拼多多#
全部评论
2我用的也是并查集,但是只要预处理两种旋转变换就行了,相当于只要720个点和1440条边.
1 回复 分享
发布于 2020-08-02 23:11
这个确实太厉害了
点赞 回复 分享
发布于 2020-08-20 21:28
强
点赞 回复 分享
发布于 2020-08-02 21:12
第三题思路一样。为什么一直20
点赞 回复 分享
发布于 2020-08-02 21:10
蛤 第二题 只有六个情况呀 需要我贴代码吗
点赞 回复 分享
发布于 2020-08-02 21:09
第二个我用旋转做的，让1始终在上面，正前面是侧面四个的最大的，然后map计数😂
点赞 回复 分享
发布于 2020-08-02 21:05
24种情况全列出来是真滴牛批🤣
点赞 回复 分享
发布于 2020-08-02 21:04
哇 厉害了！
点赞 回复 分享
发布于 2020-08-02 21:03
枚举同构这个可太6了😅
点赞 回复 分享
发布于 2020-08-02 21:03
吐了，只AC了两道，我是服务端的，过两道能有面试机会吗...
点赞 回复 分享
发布于 2020-08-02 21:02
大佬啊😂
点赞 回复 分享
发布于 2020-08-02 21:02
第三题我O(N)做的 不用二分
点赞 回复 分享
发布于 2020-08-02 21:02

相关推荐

01-13 20:19
清华大学 机械设计/制造
机械考研的五大误区
大家好，今天给你们分享一些机械考研误区。1、985、211名校比机械专业强的双非院校更好，名校有利于就业。你们可以对比企业对待不同院校给的薪资不一样就能感受到，另外还有一个面试的机会名校更多。2、机械考研后不一定更好就业，可能大家也听过，某些企业三年前以本科身份能进去，三年后需要985、211研究生的身份进去。3、大部分人读研后会发现并不是自己不想读博，而是发现自己不适合科研。4、机械读研前会认为：读研期间会学到很多前沿高端的技术，或者攻克什么难的科研课题。机械读研后的感受：课程跟大学一样，上课玩手机，没几个人听。对于毕业论文很多都是通过排列组合式的创新，比如已有a算法优化b算法，那我用c算法...
实习的你做了哪些离谱的工...
点赞 评论 收藏
分享
昨天 15:12
叮咚买菜_咚力生（管理方向）(准入职员工)
shein内推，shein内推码
业务一面--30mim自我介绍在安克创新的产品运营主要做了什么?未来的职业规划方向？产品经理和产品运营的区别?两者重叠的核心部分是什么？为什么想做产品运营？为什么实习都不超过半年？这次实习的预期时长与到岗时间？需求收集与过滤占比较高，能接受吗？（其余为面试官讲解岗位内容）二面-25min自我介绍未来希望做产品运营还是产品经理？对该产品的哪条业务线感兴趣？B端产品和C端产品的区别?为什么想做B端产品？（过往为电商运营经验）一周出勤时间？英语听说读写水平？英语自我介绍英语问答：能否接受跨国会议的时差？全球超级独角兽SHEIN26届校招网申开启【关于Shein】全球领先的跨境电商，服务于150+个国...
点赞 评论 收藏
分享
01-03 18:14
商洛学院 算法工程师
找寒假实习，薪资没有要求，想学习经验
牛至超人：您好，京东物流岗了解一下吗？负责精加工食品的端到端传输
点赞 评论 收藏
分享
2025-12-09 23:27
商丘学院 嵌入式软件工程师
双非0&nbsp;offer，26应届学校11月底才放人，没投多少家，感觉都招满了我现在应该找实习吗，简历还应该怎么改求大佬指教
程序员花海：实习和校招简历正确格式应该是教育背景+实习+项目经历+个人评价 其中项目经历注意要体现业务 实习经历里面的业务更是要自圆其说 简历模板尽可能保持干净整洁 不要太花哨的
点赞 评论 收藏
分享
01-10 15:49
门头沟学院 嵌入式软件工程师
嵌入式八股文准备技巧
在嵌入式岗位面试中，“八股文”几乎不可避免。无论是&nbsp;C&nbsp;语言、操作系统、RTOS，还是中断、内存、并发，这些问题往往反复出现。然而，真正拉开差距的并不是“会不会背”，而是是否能把八股文转化为工程思维和实践经验。本文从嵌入式面试的真实考察逻辑出发，探讨高效且有深度的八股文准备方法。一、先理解“为什么问”，而不是“怎么答”嵌入式八股文表面上是概念题，本质上是在验证三个能力：底层认知是否正确：是否理解硬件、编译器、操作系统之间的关系工程风险意识：是否知道错误使用会带来什么后果可迁移能力：能否将概念迁移到不同平台或项目中例如，“volatile&nbsp;的作用是什么”并不是想听定义，而是在判断你是否理解编译器...
点赞 评论 收藏
分享
评论
7
18
分享

招聘动态

查看更多

牛客网申助手重磅发布

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 实习的你做了哪些离谱的工作 #
6929次浏览 101人参与
# 小厂实习有必要去吗 #
77570次浏览 368人参与
# MiniMax求职进展汇总 #
1647次浏览 26人参与
# 简历第一个项目做什么 #
5516次浏览 89人参与
# Prompt分享 #
1101次浏览 36人参与
# 为了入行xx岗，我学了__ #
4230次浏览 71人参与
# 被说“做题家”，你的反应是_____？ #
669次浏览 24人参与
# 听到哪句话代表面试稳了OR挂了？ #
124291次浏览 558人参与
# 工作压力大，你会干什么？ #
9741次浏览 241人参与
# 找实习记录 #
20393次浏览 367人参与
# 如果不上班，你会去做什么 #
4909次浏览 214人参与
# 分享一个让你热爱工作的瞬间 #
57059次浏览 482人参与
# 邪修省钱套路 #
5859次浏览 205人参与
# 你都见过什么样的草台班子？ #
1451次浏览 31人参与
# AI让你的思考变深了还是变浅了？ #
3341次浏览 99人参与
# 通信硬件薪资爆料 #
1200013次浏览 7192人参与
# 我的求职精神状态 #
419249次浏览 3071人参与
# 如果让你发明个APP，你会想做什么 #
1174次浏览 32人参与
# 大家实习每天都在干啥 #
111597次浏览 602人参与
# 你找工作经历过哪些骗局？ #
27235次浏览 217人参与
# 我的付费上班经历 #
10540次浏览 178人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务