微众银行后端笔（个人认为凉）经

第一题： X是1的位N在那个位置也必须是1，设X是1的位数量为n_x Y是1的位N在那个位可能是1，设Y是1的位数量为n_y 那么这个问题就可以改成，n_y个坑，其中有n_x个坑已经种了萝卜，你至少要种L个萝卜，至多能种R个萝卜。 这是一个组合数求和的问题，需要注意非法情况，如Y|X != Y || X&Y != X(即在坑以外的地方种萝卜)还有n_x > R || n_y < L(即萝卜不够用或坑不够用） 第二题： 结论：两个湮灭术最优的情况一定是放在某个点的左边（或不放）和右边（或不放） 证明：如果两个湮灭术放在了某个点的同侧，则两个湮灭术之间肯定有一段区间为正，则该区间的点符合结论。 那问题就变成了left和right各炸哪段（或不炸）收益最大。此时可以用dp_left[i], dp_right[i]，分别表示i左边（右边）的连续区间和最小值(<=0)。那只需要从左到右，从右到左dp记录前缀和的最小值。最后再遍历找到max(sum_all-dp_left[i]-dp_right[i]) 第三题： 显然上界是12，因为全取2的幂肯定能覆盖全部魔方。如果我们记录当天所有编号12位各位是1的次数，记录完后再选12位里面出现次数最多的那位，去删除队列里有该位的，并维护这个全局的总数。 想象12位就是12个圈两两相交，从顶向下贪心出现总数最多的位（比如1），每次删除都会去掉一个大集合，只有一定不被包含的解才不会被删掉（即2/4/8...）删到最后队列为空，贪心得到最优解。 但是这种贪心复杂度很高，会超时。 优化思路：自底向上，既然大集合变小集合很慢，那就让小集合变大集合。 举个例子：9,3,11,2,7 这五个数分别代表5个圈，9&3==1说明9和3合并后成一个公共大圈1，3&11==3说明3和11合并成公共圈3，9&2==0说明没有公共圈，这是两个不相交的问题。 按照这个思路，我们可以维护一个链表，把第0个问题9加入链表。然后继续往后遍历num，遍历链表状态s，next_state = num & s。如果遍历链表s，存在一个使得next_state不为0说明它们可以变成一个集合更大的新问题，则更新s变为next_state；否则这是两个不相交的问题则将next_state加入链表。 比如9，3，11，2，7的过程就是 [9] 3，11，2，7 [1] 11，2，7 [1] 2，7 [1，2] 7 [1，2] 最后1，2就是所有状态合成后不相交的最优解 第三题优化后复杂度为O(nlogC)，C是编号上界，最坏的情况就是链表马上就有12个问题，每个num都要遍历12次才合并进去（当然链表有12个可以直接break了） 第三题自底向上思路的证明： 两个问题只可能相交或不相交🍌 结论：若不相交，则以后都不可能相交 反证： 假设问题i，j不相交，k是从j更新得到的问题，k与i相交。 k与i相交得(k & i) != 0，k是从j更新得到的问题k = j & X (X是一组问题)，则 (j & X & i) != 0，推出 (j & i) != 0（否则前者不成立），那么j与i相交，矛盾。

微众银行这次笔试公认的难啊😂大佬知道啥时候出结果不？

好牛😌学计算机的就是不一样😸

何烨煜？