时间线

流程概况

240425 笔试

应该都写出来了,个别问题存疑。

240527

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


笔试

Part1 选择题

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

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

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

    A. 13;  B. 29;  C. 2061;  D. 2990;A.~\frac{1}{3};~~B.~\frac{2}{9};~~C.~\frac{20}{61};~~D.~\frac{29}{90}; (完全不会,五次算出五个答案,没一个在选项里)

  • 一副扑克 54 张,均分 3 副,一副 18 张。问大小王在同一人手中的概率是多少?(吉比特你超爱考概率啊!)

剩余一道读代码题:本质是数二进制 11

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

Part2 填空题

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

聪明点,把代码抄下来放到 Part3 跑一下…

Part3 编程题

球赛综合排名

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

两端取数博弈

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

不考虑优化,O(N3)O(N^3) 的区间 dpdp

dp[l][r][w]=max{j=lra[j]j=l+1ra[j]dp[i][r][1w], l<irj=lr1a[j]dp[l][i][1w], li<rdp[l][r][w] = \max\left\{\begin{array}{ll} \sum_{j=l}^{r}{a[j]}\\ \sum_{j=l+1}^{r}{a[j]} - dp[i][r][1-w] & ,~l < i \le r \\ \sum_{j=l}^{r-1}{a[j]} - dp[l][i][1-w] & ,~l \le i < r \\ \end{array}\right.

dp[i][j][w]dp[i][j][w] 表示当前数字为 a[l..r]a[l..r] 的状态下,玩家 ww 比对手最多多多少筹码。应该可以单调队列优化为 O(N2)O(N^2)

去除一点的 MST

单独召唤精灵 ii 的代价为 aia_i。不过如果两种精灵存在吸引力,你可以花费 bi,jb_{i,j} 的代价通过精灵 ii 召唤精灵 jj,这样做的前提是你已经召唤了精灵 ii。已知并非任何精灵间存在吸引力,但如果存在总有 bi,j=bj,ib_{i,j}=b_{j,i}。请问集齐其中任意 n1n-1 种精灵的最小代价。数据范围 N150N \le 150

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

解法有三:

  • Prim 从 00 开始,只剩一个点时结束。复杂度 O(N2)O(N^2)
  • Prim 采用堆优化。复杂度 O(MlogN)O(MlogN)MN(N1)2M \le \frac{N(N-1)}{2}
  • Kruskal 枚举去除的点,每次重跑。复杂度 O(NM+MlogM)O(NM+MlogM)MN(N1)2M \le \frac{N(N-1)}{2}

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