10.26听课笔记

清北学堂 笔记

我们发现每一位都是相互独立的。
从大到小枚举每一位，观察是否可以作为最优解，并计算经过$n$扇门后的值，求出最大值即可。
复杂度$n\times$位数。

Part1:
从高到低位，尽可能是0就可以了。
由此转化为判定问题
从高到低枚举第$k$位，$dp[i][j]$表示前$i$棵树分成$j$组，第$k$位能否为$0$
枚举上一组末尾的树在$t$位置，$dp[t][j-1]\rightarrow dp[i][j](\sum_{j=t+1}^i b[j]$满足已得知的条件) $O(n^3\times 32$
$dp[i]$表示前$i$棵树至少分成几组能满足已知条件。
Part2:
仍然从高到低枚举每一位。由于$A=1$的存在，我们可以令$dp[i]$表示前$i$个数在满足条件的情况下最少分为几组。
因此复杂度降为$n^2\times$位数。

最朴素的想法
从高到低枚举每一位，统计这一位有多少二元组是$1$
考虑枚举位数$x$，我们要求的是该位为$1$的方案对数是否是奇数
考虑$a_i+b_j$的第$i$位是否是$1$，我们可以先将$a_i,b_j$都对$2^(i+1)$取模。

定义：
当表达式$p$为真时，$[p]=1$，否则$[p]=0$。

那么有$[(ai+bj)\&(1<<i)]=[(ai+bj)>=(1<<i)]-[(ai+bj)>=(1<<i+1)]+[(ai+bj)>=3*(1<<i)]$
接下来就相当于有$3\times$位数个限制，求满足每个限制的对数。
对于每个限制，我们可以将$a,b$进行排序，那么就可以用Two Point在$O(n)$时间内求出答案了。
至此，总复杂度为$n\lg n\times$位数，仍然通过不了本题。

容易发现该复杂度的瓶颈在于排序的复杂度。
我们可以将位从高到低枚举，这样每次在对$2^(i+1)$取模后，都会分为两堆数，其中一堆是需要减去$2^(i+1)$的，另一堆是不需要的，而这两堆都是单独排好序的，因此可以通过归并排序在$O(n)$时间内排序完毕。
总复杂度为$n\times$位数。

我们要证明，对于类似的一张图，如果蓝色能越过$p$，那黑色也一定能跳
可以反证出，大一点的数一定跳不过小一点的数。所以要尽可能跳到小一点的数上。所以要预处理出$f[i]$表示能跳到哪里。$dp[i]=dp[f[i]]+1$
所以问题就转化成了求$f[i]$。所以实际问题就是，对于每个$i$，枚举所有的素数。
枚举这$m$个素数，假设是$p$，$f[p-1],f[2p-1],f[3p-1]...f[k\times p-1]$都能更新$f[i]$。$x$跳到的位置一定小于等于$x+1$能跳到的位置。
$f[i]=min(f[i],f[i+1]),i$跳到的位置一定小于$i+1$能跳到的位置。