P2114 [NOI2014] 起床困难综合症

题目大意

给出 $n$ 个位运算操作，构造出一个小于 $m$ 的数使得对于每一位进行给出的 $n$ 次位运算后得出的数最大。

题目分析

加上 小于 $m$ 这一条件后不好分析，考虑先去掉这个限制。

因为是对于每一位单独进行操作，根据位运算的性质：位运算在二进制表示下不进位。所以我们可以对每一位贪心的进行选择。现在考虑怎么构造每一位最优。

列出真值表，针对每种情况分析：

1. 0->0 && 1->1 : 该位填 $1$ 比填 $0$ 更优。
2. 0->1 && 1->1 : 无论如何都会对最终结果产生贡献，该位可以任意填。
3. 0->0 && 1->0 ：无论如何无法对最终结果产生贡献，可以任意填。
4. 0->1 && 1->0 : 该位填 $0$ 比填 $1$ 更优。

考虑把先前去掉的条件加，为了让结果小于 $m$ ，我们发现可以在贡献一致时填入较小的数 —— $0$。现在重新回顾两种任意填的情况，为了使结果不变的情况下初始值最小，这两种也填 $0$。

但这样还无法保证结果一定小于等于 $m$。要想结果符合要求，必然要舍弃一些本可以填的位置。考虑从高位开始枚举是否能填入 $1$，因为最高位能产生的贡献比其后所有位能产生贡献值之和高，所以说最高位局部最优可以推出全局最优。

Code

注意数据范围。使用 bitset 获得更快的速度和更多的RE