problem1
给定 a_{0...2^n-1} 问是否存在 a_x + a_y < a_{x\and y} + a_{x\or y}
n\leq 20
sol:
设 x\and y = T, x \oplus T = i, y\oplus T = j，上式可以表示为 a_{T\or i\or j} + a_T > a_{T \or i} + a_{T\or j} ， 考虑令 i \rightarrow i' ，即 i' \subset i .
如果 a_{T\or i'\or j} + a_T > a_{T \or i'} + a_{T\or j} 那我们继续进行这个过程，否则就有:
\left \{
\begin{matrix}
a_{T\or i\or j} + a_T > a_{T \or i} + a_{T\or j}\\
a_{T\or i'\or j} + a_T \leq a_{T \or i'} + a_{T\or j}
\end{matrix}
\right.
令两个不等式两端分别相减得到
a_{T\or i\or j} - a_{T\or i' \or j} > a_{T\or i} - a_{T \or i'}\Rightarrow a_{T\or i \or j} + a_{T\or i'} > a_{T\or i' \or j} + a_{T \or i}
令 T \or i' = T'
a_{T'\or j \or (i \oplus i')} + a_{T'} > a_{T'\or j} + a_{T'\or (i\oplus i')}
可以得到新的三元组 T\or i',j,(i \oplus i') , 同时因为 i,j 等价，最后迭代一定可以得到 T,i,j 使得 i,j 分别仅有一位是 1 , 故枚举不同位的 1 即可，复杂度 \mathcal{O} (n^22^n)
problem2
给定一个排列 a_{1...n} ，定义一个数字 a_i 是美丽的，当且仅当不存在 a_j >a_i, j< i . 整个序列的美丽度被定义为美丽的数字的个数，问进行若干次操作(每次操作你可以选择一个美丽的数，把这个数变成 0 ; 可以不进行操作)后美丽度的最大值。
sol:
最后的序列一定是一个 \rm LIS ，但是相同长度的 \rm LIS 可能有多种，考虑最优构造：如果以若干个位置 i_1,i_2...i_k 结尾的 \rm LIS 长度均为 x ，那么 a_{i_1}, a_{i_2}...a_{i_k} 一定是不增的，否则存在一个 j 使得以 a_{i_j} 结尾的 \rm LIS 长度 \geq x+1, 和假设相矛盾，因此只需要选择最左侧的 a_i 进行转移即可，否则后面的数字一定不大于当前的数字，那么前面要进行的操作次数一定不比当前次数优. 接着用 set 直接维护删除操作即可.