赛时三题，\(D\)就差一个显然的剪枝就能过了，qwq...

A

显然第一步能选偶数就选偶数，之后只能选奇数。细节见代码。

code

B

对于选取的任意四条边，设腰为\(x\)，短边为\(a\)，长边为\(b\)，则能形成等腰梯形的充要条件为：\(x\)出现次数\(>=2\)，且\(a+2*x>b\)。两个腰选最大，并且\(a，b\)尽可能接近显然更优。具体实现见代码。

code

C

刚开这题时以为是一个神奇妙妙题，硬想了四十多分钟。等意识到是\(dp\)时，不到十分钟就码完了，只能说自己太唐了。。。

状态定义：\(dp[i][0/1]\)：表示考虑前\(i\)个人，且第\(i\)个人是诚实者(\(1\))\(or\)说谎者(\(0\))的方案数。

\(init\)：第一个人是诚实者的充要条件为\(a[1]==0\)，是说谎者的充要条件为\(a[2]==1\)（证明略）

\(ans = dp[n][0] + dp[n][1]\)

\(trans：\)根据题目规定的条件，对每一步转移的合法性做相应判断，来决定是否转移即可，细节见代码。

code

D

逆向思考，\(b\)中每个数的拆分是唯一的。所以直接对\(b\)中的每个数尝试拆分。可以证明按任意顺序拆\(b\)数组中的数都是可行的，只要拆分过程中能与\(a\)中的某个数匹配则直接匹配，最后看是否能全部匹配即可。

注意，操作数最多为\(n-m\)（本题赛时的败笔。太显然了，不知道赛时为啥忘了这一点。。）所以直接记录拆分次数，\(>n-m\)时直接判不可行即可。同时，若拆分出的某个数没有在\(a\)中出现，且不能继续拆分（即为\(1\)），则也直接判不可行即可。

code

E

不难的一道题。

对某一个数的操作次数最多为\(m\)次，因为没有必要与相同的数，且最多能 \(and\) \(m\)个数。

故可以设一个数组\(w[i][j]：\)对\(a[i]\)操作\(j\)次，可以减少的最大差值。

该数组可以用\(O(n 2^{m})\)的复杂度预处理出来，具体实现见代码。

再考虑\(k\)次操作：显然，每一次贪心地选择一个能最大化差值的方案总是最优的，而\(k\)是\(O(nm)\)级别，故可以考虑模拟操作过程，每次贪心地选取最优方案。

暴力模拟的复杂度是\(O(nmk)\)，考虑优化：

需要注意到一个关键性质：对于固定的\(i\)，\(w[i][]\)的差分数组是递减的，即对于任意\(j1 < j2\)：

因为减少\(a[i]\)的方式是做与运算，故每次操作时，一定是贪心地选取能减少当前\(a[i]\)的最高二进制位为\(1\)的那个\(b[i]\)，那么显然后续的操作，\(a[i]\)减少的值就一定不会比这一次操作多。也就是说随着操作进行，\(a[i]\)减少的值是递减的，故上式成立。

所以可以用一个大根堆来维护对于每个\(a[i]\)做当前操作会减少的差值，每次做完操作后把对\(a[i]\)做下一次操作会减少的差值放进堆中。这样可以保证每次堆顶都是最优操作（因为堆维护的都是当前操作，后续的操作 由上述证明可知 减少的差值都比当前操作要少，所以可以这样贪心，否则得用背包\(dp\)），模拟\(k\)次即可。复杂度为\(O(n 2^{m} + klogn)\)

code