一、最大异或对

        我们首先考虑暴力做法：一一枚举，每当找到更大的异或对就更新一下异或后的最大值。第二层循环到i即可，因为ai^aj和ajai是一样的。

for(int i = 0;i<N;i++)
{for(int j = 0;j<i;j++){…………}
}

        在这里，我们可以采用字典树优化算法。在第二层循环中，我们要找到与ai异或得到最大值的数。我们采取这样的做法：i每前进一步，就把i上一个数的二进制位插入树中，采用与已有的二进制位一一比较的方法得到异或最大值。我们在已经插入过的二进制数中搜索，如果能满足每一位都与ai的该位不同当然最好，否则只能将就。如图，假设当前的ai为11001，我们的树中又恰好有00110，则它们俩可以完美地匹配。上。假若不然，比如某个节点后面只有一条路径，那就没有选择只能走那条路径了。本题中Ai<=2^31，我们可以用一条三十一位的二进制串存储这些数字。

#include 
#include
using namespace std;const int N = 1e5+10;
const int M = 31*N;int son[M][2],a[N],idx;//从最高位开始异或，这样便于更新res结果。若当前位异或结果为0则*2，若当前位异或结果为1则*2+1.如果从最低位开始异或，会出现隔位的情况。例如1110^0101,第二位（从低往高数）异或结果是1，在最高位异或结果是1的情况下，如果第三位异或结果是1还好说，但是第三位异或结果是0。0可以让res = res，但两个1之间隔了多少0是不确定的，也就是说低位的1不知道具体乘以多少能得到高位为1的数。因此我们存储和询问都要从最高位开始。
void Insert(int x)
{int p = 0;for(int i =30;i>=0;i--){int u = x>>i&1;if(!son[p][u])  son[p][u] = ++idx;p = son[p][u];}
}int Query(int x)
{int p = 0,res = 0;for(int i = 30;i>=0;i--){int u = x>>i&1;if(son[p][!u]){p = son[p][!u];res = res*2+1;}else{res = res*2;p = son[p][u];}}return res;
}int main()
{int n;scanf("%d",&n);int res = 0;for(int i = 0;i<n;i++)  scanf("%d",&a[i]);for(int i = 0;i<n;i++){Insert(a[i]);res = max(res,Query(a[i]));}printf("%d",res);return 0;
}

二、食物链

        我们可以用并查集维护这些动物和它们之间的关系。通过画图可以发现，若某个节点到根节点的距离与另一个节点到根节点的距离分别模3的结果相差1，则它们是吃与被吃的关系；若某个节点到根节点的距离与另一个节点到根节点的距离分别模3后相等，则它们是同类。因此我们可以维护一个到父节点的距离的数组，同时通过路径压缩把某条路径上的节点的父节点都修改为根节点，这样就可以得到到根节点的距离（因为此时父节点就是根节点）。

#include 
using namespace std;const int N = 50010;
//d[x]表示x到它的父节点的距离
int p[N],d[N];int find(int x)
{if(p[x]!=x){int tmp = find(p[x]);d[x] += d[p[x]];p[x] = tmp;}return p[x];
}int main()
{int n,k;//局部变量要初始化，否则为随机值int res = 0;scanf("%d%d",&n,&k);//别忘了初始化father数组，初始化时从1开始！for(int i = 1;i<=n;i++)  p[i] = i;while(k--){int t,x,y;scanf("%d%d%d",&t,&x,&y);if(x>n||y>n)    res++;else{int px = find(x),py = find(y);if(t==1){if(find(x)==find(y)&&(d[x]-d[y])%3)   res++;else if(find(x)!=find(y)){p[px] = find(y);//一定要用px和py存储下最初find(x)的值！否则若写成d[find(x)]，由于上一句已经把find(x)的father改成find(y)，那么find(x)也会跟着变动，不再是我们想要找的原来的结点了！d[px] = d[y] - d[x]; }}else{if(find(x)==find(y)&&(d[x]-d[y]-1)%3) res++;else if(find(x)!=find(y)){p[px] = py;d[px] = d[y] - d[x] + +1;}}}}printf("%d",res);
}

三、堆的额外操作

        在上一篇文章中，我们讲到了堆的up和down操作。在这里我们补充一个堆的映射关系修改操作。ph数组存储的是左边的点在右边的对应点，hp数组存储的是右边的点在左边的对应点。如图：

        交换a和b的值后，相应“伪指针”的指向也要发生改变。改进后的交换代码如下：

swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a],hp[b]);
swap(heap[a],heap[b]);

以上就是本篇文章的全部内容啦！如果你感觉对自己有帮助，请多多支持博主，你的支持就是我日更的动力！

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！