n个数任取进行异或，求最大值与严格次大值
第一次写线性基www 弄出线性基后可以得到最大值。 接下来我们从小到大枚举次大值在哪一个位与最大值不一样，比如在i位，那么比i位高的要与最大值进行一样的选择，而第i位与最大值进行不一样的选择，比i位低的需要最大化，最后判定如果是严格比最大值小就可以退出，这一定是严格次大值。
#include<cstdio>#include<algorithm>#define fo(i,a,b) for(i=a;i<=b;i++)#define fd(i,a,b) for(i=a;i>=b;i--)using namespace std;int a[40],b[40];int i,j,k,l,t,n,m,ans,num;int main(){ scanf("%d",&n); fo(i,1,n){ scanf("%d",&t); fd(j,31,0){ if ((t&(1<<j))!=0){ if (!a[j]){ a[j]=t; break; } t^=a[j]; } } } fd(i,31,0){ if ((ans&(1<<i))==0){ ans^=a[i]; b[i]=1; } } PRintf("%d ",ans); fo(i,0,31){ num=0; fd(j,31,i+1) if (b[j]) num^=a[j]; if (!b[i]) num^=a[i]; fd(j,i-1,0) if ((num&(1<<j))==0) num^=a[j]; if (num<ans) break; } printf("%d/n",num);}新闻热点
疑难解答
