没有什么前言?直接进入正题qwq
俩俩异或 求最值:
建trie树
O(n)枚举每个数找这个数的最值,每次反走就成,还可以剪枝一波(如果在某位已经小于ans显然可以直接return?
void Insert(int val) { ; <<;i>=;i>>=) { :; if(!ch[x][to]) ch[x][to]=++node; x=ch[x][to]; } } //建树,懒得说 int Que(int val) { ,bs=; <<;i>=;i>>=) { :; ]) x=ch[x][to^],bs+=i; else x=ch[x][to]; } return bs; } //查询,懒得说 ; ;i<=k;i++) { Ans=max(Ans,Que(A[i])); Insert(A[i]);//就想说下因为a^b b^a结果一样所以我们可以边查询边加点,over } cout<<Ans<<endl; //对了这个并不是自己的代码鸭...有时间自己坐下典型题然后把自己代码放上来qwq
代码在这儿!
俩俩或 求最值:
还没懂,在网上也没找到什么学习笔记?只能硬啃今天考试的代码尝试理解QAQ等我理解了再回来写QAQ
ummm先推翻我的一错误想法,是这样的:
我选一个最大的,肯定不会更劣,所以我就选最大的然后再O(n)算一遍它和每个数的或起来的值就可以了
然后成功hack掉了:110010 100001 011110 此时显然选后俩更优不应该选max
所以还是乖乖学正解去趴qwq
;i<=k;i++) f[A[i]]=;//A[i]:原来的所有数 ;p<=(<<);p<<=) <<)-;i>=;i--);//如果能构出i 并且 i和p有交集 那么i^p就也能构造出来?ummm还是没懂x ; ;i<=k;i++) { ; <<;p>=;p>>=) if(!(A[i]&p))if(f[bs|p]) bs|=p; Ans=max(Ans,bs|A[i]); } cout<<Ans<<endl;
先放个保证正解的代码qwq
然而事实是这个代码我还是没懂啊...没办法先放上来然后有空想想在NOIp前回来填坑趴QAQ
俩俩并 求最值:
从高位到低走,若这位有>=2个1则可以是1然后暴力把所有这位不是1的数全删了,直接暴力走一遍
; i<=k; ++i)a[].push_back(atk[i]); ; p; --p) { ; ; i<tot; ++i)) ++cnt; ); i<tot; ++i)) a[p-].push_back(a[p][i]); ; i<tot; ++i)a[p-].push_back(a[p][i]); } ].size(), cnt=; ; i<tot; ++i)][i]&)++cnt; ) { cnt=; ; i<tot; ++i) ) break; else ][i]&) { ]=a[][i]; ]&=a[][i]; ++cnt; } } ]=a[][]&a[][]; printf(]);
还是比较好理解的趴我觉得?就懒得放注释了qwq
多个异或 求最值(还没学会qwq待补充):
线性基经典问题了,但是我线性基还没学会?等学会了把主要思想放线性基学习笔记里这里就放个模板代码趴qwq