吉比特 引擎开发实习生 笔经 面试拒

时间线

240425 笔试：应该都写出来了，个别问题存疑。

240527 拒面：拒绝了面试邀约，因为这段时间没什么时间。

有一说一，你家流程有点慢。。。Maybe 是我排序太靠后了。。。

笔试

Part1 选择题

回忆几道印象深刻的题，其余部分概括一下。

• 甲乙丙丁戊其中四人发言说 “XX 是我的 XX (亲戚) 的 XX (亲戚)”，请问谁未发言。（岳母和女婿是啥来着...）

• 有三个小组各 10 / 15 / 25 人，其中女生 3 / 7 / 5 人，问随机从其中一个组选两人，已知后选出的为男生，则先选出为女生的概率？

  （完全不会，五次算出五个答案，没一个在选项里）

• 一副扑克 54 张，均分 3 副，一副 18 张。问大小王在同一人手中的概率是多少？（吉比特你超爱考概率啊！）

剩余一道读代码题：本质是数二进制 。

两道时间复杂度分析，余下都是些计算机基础选择题，和大学考试题有点像。

Part2 填空题

• 大小端与 gcd，读代码填输出。
• 奇怪赋值、引用、指针，读代码填输出。

聪明点，把代码抄下来放到 Part3 跑一下...

Part3 编程题

球赛综合排名

已知多场球赛所有选手排名序列，根据拿到第一名、第二名... 的次数排名选手；如果选手并列，按字典序输出姓名。具体而言，选手 A 比选手 B 排名好，当取得第一名的次数比选手 B 更多，或取得第一名次数一样多而取得第二名次数更多，或前面同等条件取得第三名次数更多... 忘记数据范围了，别太蠢应该都行。

两端取数博弈

给定一个序列，A 和 B 从两段取数，可以选择一端，然后从该端拿走至少一个数，取到空游戏结束。游戏结束时，两人比手上拿到的数之和的差，然后可以从对方手上赢取相应的筹码。取到的数可能是负数，数据范围 。

不考虑优化， 的区间 ：

表示当前数字为 的状态下，玩家 比对手最多多多少筹码。应该可以单调队列优化为 。

去除一点的 MST

单独召唤精灵 的代价为 。不过如果两种精灵存在吸引力，你可以花费 的代价通过精灵 召唤精灵 ，这样做的前提是你已经召唤了精灵 。已知并非任何精灵间存在吸引力，但如果存在总有 。请问集齐其中任意 种精灵的最小代价。数据范围 。

本质是个图论问题。将精灵间吸引力关系连边，这是个无向图。然后把召唤者当精灵 ，用单独召唤代价与其他精灵连边。问题转化为去除任意一个点（ 除外）的最小生成树。

解法有三：

• Prim 从 开始，只剩一个点时结束。复杂度 。
• Prim 采用堆优化。复杂度 ，。
• Kruskal 枚举去除的点，每次重跑。复杂度 ，。

方法一最优秀，不过当时我用的方法三，因为平时写 Kruskal 比较多。