微众银行笔试

第一题暴力能过81

😭xd我笔试时没做出来，但是现在有思路了。 第一题： 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。如果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就是所有状态合成后不相交的最优解

https://www.nowcoder.com/discuss/1149281感觉跟你的差不多。