一. 最大异或对
题目来源：Acwing 143.最大异或对
解题思路
这里大概说一下异或的概念：
异或(^)是作用在二进制表示中的，对于相同的数异或的结果是0，相异的数异或是1
例如3 ^ 5 = (011) ^ (101) = 110 = 6(对于最低位因为两个都是1所以异或结果是0，第二位和最高位两边都是不同的所以异或结果是1）
这题我们很容易就想到暴力的解法，就是枚举所有的数字的搭配，找到异或的最大值即可
解法一：暴力枚举
#include<iostream>usingnamespacestd;constintN=1e5+10;inta[N];intn;intmain(){for(inti=0;i<n;i++)cin>>a[i];intret=0;for(inti=0;i<n;i++)for(intj=0;j<n;j++)ret=max(ret,a[i]^a[j]);cout<<ret<<endl;return0;}时间复杂度O(n∗n)O(n*n)O(n∗n)
这样是肯定会超时的，所以我们需要优化一下方案
对于暴力解法我们枚举一个数后找这个数和另外一个数异或后的最大值需要再遍历一次数组，这样效率太低了，我们知道异或的性质就是相异的二进制位异或后就是1，所以要找异或后的最大值其实就是从最高位开始找最多不一样的二进制位，所以问题就变成了如何快速找到从最高位开始最多相异的二进制串？
快速找到一个已有数字的二进制串，那我们很容易就可以想到一个数据结构：trie树
优化方案
此时方案就可以优化为先将所有数字存进一个01trie树中，再枚举每个数字，用trie树快速找到数组中和这个数异或的最大值，再维护最终结果即可
解法二：Trie树+枚举
#include<iostream>usingnamespacestd;constintN=1e5+10;inta[N],tree[N*31][2],idx;intn;voidinsert(intx){intcur=0;for(inti=30;i>=0;i--){intpath=(x>>i)&1;if(!tree[cur][path])tree[cur][path]=++idx;cur=tree[cur][path];}}//找到在数组中x异或的最大值intfind(intx){intcur=0,ret=0;for(inti=0;i>=0;i--){intpath=(x>>i)&1;if(tree[cur][!path])//第i位有相异的数{cur=tree[cur][!path];ret+=(1<<i);}else{cur=tree[cur][path];}}returnret;}intmain(){for(inti=0;i<n;i++){cin>>a[i];insert(a[i]);}intret=0;for(inti=0;i<n;i++){ret=max(ret,find(a[i]);}cout<<ret<<endl;return0;}二. 雪花雪花雪花
题目来源：Acwing 137.雪花雪花雪花
解题思路
此题题意是给定n个6元序列，找到其中是否满足有两个序列经过旋转和翻转后能得出来相同的序列
因为相同的雪花经过旋转和翻转后最多可以得到12种不同的序列的，而如果想将每个雪花对应的所有序列存下来再判重是不现实的，所以我们要有一种哈希（映射）的思想，即用一个序列来代表这个雪花，因为是旋转的序列，所以我们可以使用字符串的最小表示的序列来代表这个雪花
字符串的最小表示
概念：字符串的最小表示意思是一个字符串经过若干次旋转后得出得所有序列中字典序最小的序列就是它的最小表示
那么如何求字符串的最小表示呢？
1.将目标字符串sss存储两次
2.定义两个指针i=0,j=1i = 0, j = 1i=0,j=1和一个比较长度k=0k = 0k=0
3.每次比较s[i+k]和s[j+k]s[i + k]和s[j + k]s[i+k]和s[j+k]的大小，如果相等就k++k++k++,如果不相等大的一方的指针就需要跳到比较字符位置的下一个（例如：if(s[i+k]>s[j+k])i=i+k+1;if(s[i + k] > s[j + k]) i = i + k + 1;if(s[i+k]>s[j+k])i=i+k+1;
4.最后得出来的min(i,j)min(i, j)min(i,j)就是字符串最小表示的起始位置，再将临时数组从起始位置赋值字符串的长度到原字符串中即可
Code
#include<iostream>usingnamespacestd;intmain(){string s;cin>>s;intn=s.size();s=s+s;inti=0,j=1,k=0;while(i<n&&j<n&&k<n){if(s[i+k]==s[j+k])k++;else{if(s[i+k]>s[j+k])i=i+k+1;elsej=j+k+1;k=0;//i或者j更新位置之后k也要更新if(i==j)j++;}}}再回到题目本身，现在知道了可以使用最小表示来代表一个雪花，那我们其实就是要到是否有两个相同的序列了，所以我们其实就可以直接给所有的序列按照字典序排序，如果是有相同的序列的话那它们肯定是相邻的，所以最后判断是否有相邻且相同的元素即可
因为此题还有翻转字符串的情况，而字符串的最小表示只有所有旋转字符串的最小字典序的性质，所以最终的雪花的表示是需要同时对翻转前和翻转后都求一次最小表示，然后再取最小值
解法：字符串的最小表示 + 排序找重
Code
#include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;constintN=1e5+10;intsnows[N][6],snow[6],isnow[6],idx[N],n;voidget_min(int*a){inttmp[12];for(inti=0;i<12;i++)tmp[i]=a[i%6];//将字符串存两遍inti=0,j=1,k=0;while(i<6&&j<6&&k<6){if(a[i+k]==a[j+k])k++;else{if(a[i+k]>a[j+k])i=i+k+1;elsej=j+k+1;k=0;if(i==j)j++;}}intst=min(i,j);for(inti=0;i<6;i++)a[i]=tmp[st+i];}//判断a是否小于等于bboolcmp_min(int*a,int*b){for(inti=0;i<6;i++){if(a[i]<b[i])returntrue;elseif(a[i]>b[i])returnfalse;}returntrue;}//排序也是小的字典序的在前面boolcmp(inta,intb){returncmp_min(sonws[a],snows[b]);}intmain(){cin>>n;for(inti=0;i<n;i++){for(intj=0,k=5;j<6;j++,k--){scanf("%d",&snow[j]);isnow[k]=snow[j];//存储翻转的字符串}get_min(snow);get_min(isnow);if(cmp_min(snow,isnow))memcpy(snows[i],snow,sizeofsnow);elsememcpt(snows[i],isnow,sizeofisnow);idx[i]=i;//二维数组排序做索引}sort(idx,idx+n,cmp);for(inti=1;i<n;i++){if(cmp(idx[i-1],idx[i])&&cmp(idx[i],idx[i-1])){puts("Twin snowflakes found.");return0;}}puts("No two snowflakes are alike.");return0;}
