题解

公平划分

设这n个数的异或值为 X ，集合 B 的异或值为 Y

相当于要满足 X xor Y=Y，于是可得X=0

于是只需要判断下读入的 n 个数的异或值是否为 0，如果是 0 输出2^n-2，否则输出 0

配对

考虑状态压缩dp，令f[S][i]表示配对了前 i-1 个男生，用的女生的集合为 S 的方案数，直接转移即可。

字符串问题

考虑第二种操作每次肯定能加多长就加多长，于是只要维护串 S 的子序列自动机，每次贪心跳就行了。

公共山峰

定义f[i][j][type]表示考虑了x[1..i] 和y[1..j]，且x[i]和y[j]配对，当前山峰的类型是 type的情况的最长公共山峰长度。

朴素的转移是枚举下一个 k 是啥，然后进行转移，时间复杂度：O(n^3)

但是我们可以令g[i][j][type]=Max_{k=1}^{i}f[k][j]，然后只要考虑k=i+1就行了

时间复杂度：O(n^2)