9.10 腾讯笔试

逆天牛客，提交完等了一小时都没等到结果。

• 第一题

题意：给一颗二叉树（n≤1e5），每个节点权值为0/1。求根节点到叶节点的路径中，有多少条上1的数量比0的数量多一？

题解：dfs的时候，顺便维护cnt1-cnt0。

• 第二题

题意：给一个n个数的数组a（n≤1e5，a[i]≤1e9），接下来有n-1次操作，每次删除a中的一个数。求数组原始的中位数，以及每次操作后的中位数。

题解：用两个multiset维护中位数，力扣应该有类似的题目。

• 第三题

题意：给一个n个数的数组a（n≤2e5，a[i]≤1e9），表示n个怪物的战斗力。牛牛的初始战力x为0，和怪物战斗时，如果x＜a[i]，牛牛的战力x会上升至a[i]；否则x下降至a[i]。求打败n只怪物后，牛牛累计上升的战力最大为多少？

题解：贪心。排序后，先打一个战力最大的，再打一个战力最小的，循环下去。

• 第四题

题意：有一个长度为n的01串，给出k（k≤n≤1e6）时，定义串的检验和为所有长度为k的子串的异或和。给定n和k，对任意一个长度为n的01串S，求其他长度为n的01串中和S校验和相同的有多少个？

题解：结论题。S串有2^n种，校验和有2^k种，平均每种有2^(n-k)个，那么答案为2^(n-k)-1。

• 第五题

题意：给一个n个数的数组a（n≤1e5，a[i]≤1e9），每次操作可以选一个数将其二进制下最低位的1变成0。求k（k≤100）次操作后a数组的总和最小为多少？

题解：背包。用dp[i][j]表示前i个数进行了j次操作后的最大总和，转移时需要对a[i]进行二进制分解，转移方程如下。复杂度为O(n*k*30)。

//对当前数a[i]进行j次操作，减去的值为sum
//对前i-1个数进行了pre次操作
//0≤pre≤k
dp[i][pre + j] = max{dp[i - 1][pre] + sum} 

本以为虹软笔试已经天下无敌，没想到有人比他还勇猛，这是谁的部将（x