一. 最大异或对题目来源Acwing 143.最大异或对解题思路这里大概说一下异或的概念异或(^)是作用在二进制表示中的对于相同的数异或的结果是0相异的数异或是1例如3 ^ 5 (011) ^ (101) 110 6(对于最低位因为两个都是1所以异或结果是0第二位和最高位两边都是不同的所以异或结果是1这题我们很容易就想到暴力的解法就是枚举所有的数字的搭配找到异或的最大值即可解法一暴力枚举#includeiostreamusingnamespacestd;constintN1e510;inta[N];intn;intmain(){for(inti0;in;i)cina[i];intret0;for(inti0;in;i)for(intj0;jn;j)retmax(ret,a[i]^a[j]);coutretendl;return0;}时间复杂度O(n∗n)O(n*n)O(n∗n)这样是肯定会超时的所以我们需要优化一下方案对于暴力解法我们枚举一个数后找这个数和另外一个数异或后的最大值需要再遍历一次数组这样效率太低了我们知道异或的性质就是相异的二进制位异或后就是1所以要找异或后的最大值其实就是从最高位开始找最多不一样的二进制位所以问题就变成了如何快速找到从最高位开始最多相异的二进制串快速找到一个已有数字的二进制串那我们很容易就可以想到一个数据结构trie树优化方案此时方案就可以优化为先将所有数字存进一个01trie树中再枚举每个数字用trie树快速找到数组中和这个数异或的最大值再维护最终结果即可解法二Trie树枚举#includeiostreamusingnamespacestd;constintN1e510;inta[N],tree[N*31][2],idx;intn;voidinsert(intx){intcur0;for(inti30;i0;i--){intpath(xi)1;if(!tree[cur][path])tree[cur][path]idx;curtree[cur][path];}}//找到在数组中x异或的最大值intfind(intx){intcur0,ret0;for(inti0;i0;i--){intpath(xi)1;if(tree[cur][!path])//第i位有相异的数{curtree[cur][!path];ret(1i);}else{curtree[cur][path];}}returnret;}intmain(){for(inti0;in;i){cina[i];insert(a[i]);}intret0;for(inti0;in;i){retmax(ret,find(a[i]);}coutretendl;return0;}二. 雪花雪花雪花题目来源Acwing 137.雪花雪花雪花解题思路此题题意是给定n个6元序列找到其中是否满足有两个序列经过旋转和翻转后能得出来相同的序列因为相同的雪花经过旋转和翻转后最多可以得到12种不同的序列的而如果想将每个雪花对应的所有序列存下来再判重是不现实的所以我们要有一种哈希映射的思想即用一个序列来代表这个雪花因为是旋转的序列所以我们可以使用字符串的最小表示的序列来代表这个雪花字符串的最小表示概念字符串的最小表示意思是一个字符串经过若干次旋转后得出得所有序列中字典序最小的序列就是它的最小表示那么如何求字符串的最小表示呢1.将目标字符串sss存储两次2.定义两个指针i0,j1i 0, j 1i0,j1和一个比较长度k0k 0k03.每次比较s[ik]和s[jk]s[i k]和s[j k]s[ik]和s[jk]的大小如果相等就kkk,如果不相等大的一方的指针就需要跳到比较字符位置的下一个例如if(s[ik]s[jk])iik1;if(s[i k] s[j k]) i i k 1;if(s[ik]s[jk])iik1;4.最后得出来的min(i,j)min(i, j)min(i,j)就是字符串最小表示的起始位置再将临时数组从起始位置赋值字符串的长度到原字符串中即可Code#includeiostreamusingnamespacestd;intmain(){string s;cins;intns.size();sss;inti0,j1,k0;while(injnkn){if(s[ik]s[jk])k;else{if(s[ik]s[jk])iik1;elsejjk1;k0;//i或者j更新位置之后k也要更新if(ij)j;}}}再回到题目本身现在知道了可以使用最小表示来代表一个雪花那我们其实就是要到是否有两个相同的序列了所以我们其实就可以直接给所有的序列按照字典序排序如果是有相同的序列的话那它们肯定是相邻的所以最后判断是否有相邻且相同的元素即可因为此题还有翻转字符串的情况而字符串的最小表示只有所有旋转字符串的最小字典序的性质所以最终的雪花的表示是需要同时对翻转前和翻转后都求一次最小表示然后再取最小值解法字符串的最小表示 排序找重Code#includeiostream#includecstring#includealgorithmusingnamespacestd;constintN1e510;intsnows[N][6],snow[6],isnow[6],idx[N],n;voidget_min(int*a){inttmp[12];for(inti0;i12;i)tmp[i]a[i%6];//将字符串存两遍inti0,j1,k0;while(i6j6k6){if(a[ik]a[jk])k;else{if(a[ik]a[jk])iik1;elsejjk1;k0;if(ij)j;}}intstmin(i,j);for(inti0;i6;i)a[i]tmp[sti];}//判断a是否小于等于bboolcmp_min(int*a,int*b){for(inti0;i6;i){if(a[i]b[i])returntrue;elseif(a[i]b[i])returnfalse;}returntrue;}//排序也是小的字典序的在前面boolcmp(inta,intb){returncmp_min(sonws[a],snows[b]);}intmain(){cinn;for(inti0;in;i){for(intj0,k5;j6;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,idxn,cmp);for(inti1;in;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;}