T1
一道数学题, 考场上对题意的理解有些问题, 现在还没仔细研究, 因此鸽了
T2
是个先判断是否存在合法方案, 如果有合法方案倒推求每一个 $x$ 的题, 倒推的过程有些像模拟, 我们先来讨论如何确定是否存在合法方案, 它用了个 DP 你敢想?$skyh$ 考场 AC, 人家咋想到的, 咱也不知道, 咱也不敢问
判断合法
设 $dp[i][j]$ 表示在进行第 $i$ 个运算之后, 是否有可能出现 1,$dp[i][j]=0$ 代表无解,$dp[i][j]=1$ 代表有解, 接下来我们考虑对于什么样的 $dp[i-1][j]$ 可以转移到的 $dp[i][k]$ 中,$k$ 需要满足什么样的条件
对于 $and$ 操作来说, 我们原本的结果中已经出现了 $j$ 个一, 当前还可以与上一个有 $a[i]$ 个一的数, 那我们得到的数中最多有 ${\min}(a[i],j)$ 个一, 最少应该有 $\max(0,a[i]+j-m)$ 个一, 前半个好理解, 完全不重合, 后半个是不得不重合
对于 $or$ 操作来说, 得到的数中最少有 $\max(a[i],j)$ 个一, 最多有 $\min(m,a[i]+j)$ 个一
对于 $xor$, 一最少的情况是有一个数中所有的一都被另一个数抵消了, 此时有 $|a[i]-j|$ 个一, 再一个就是全部错开了, 那此时就有 $\min(m,a[i]+j)$ 个一, 但显然还有另一个限制条件就是零的个数,$xor$ 的结果为一, 必须是一个 0 和一个 1$xor$ 得来的, 所以还需要和 $2*m-a[i]-j$ 取一下 ${\min}$
寻找方案
设 $c$ 当中一有 $num$ 个, 那么 $dp[n][num]$ 如果等于 1, 我们就一定可以找到一组合法方案, 接下来我们讨论倒推过程
对于 $xor$, 假设 $y$ $xor$ $x=c$, 我们已知 $c$ 以及 $xy$ 中一的个数, 求 $xy$, 由于要满足对于 1 个数的限制, 我们首先想到的应该是在 $c$ 中是 0 的地方, 给 $xy$ 中都放一, 其实有几个是 0 的地方需要放一, 是可以算出来的, 应该有 $\frac{a[i]+j-num}{2}$, 我们就找够这么多位给 $xy$ 全放上一, 然后在剩下 $c$ 中为 1 的地方给 $x$ 或 $y$ 放上一即可
$and$ 和 $or$ 较为简单, 可以自己 yy 一下
T3
正解好像有换根 DP 之类的, 没仔细看, 就又咕咕咕了
来源: http://www.bubuko.com/infodetail-3158892.html