位运算求最值 学习笔记 (待补充QAQ)
2024-10-16 21:29:15
没有什么前言?直接进入正题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
最新文章
- 微软软件开发技术二十年回顾-COM、OLE、ActiveX及COM+篇
- textFiled的placeHolder字体颜色
- Qt create 配置git版本管理
- java.sql.SQLException: JZ00L
- 【Algorithm】堆排,C++实现
- 大数据技术 —— MapReduce 简介
- EPP3怎么安装SVN(EclipsePHP Studio 3.0)
- 从tcp原理角度理解Broken pipe和Connection reset by peer的区别
- Linux 图形系统界面 和 文本系统和界面切换
- PHP流程管理,堪比小小程序
- RGB与HSV之间的转换公式及颜色表
- C# WinForm 富文本编辑器 用kindeditor实现本地图片只选取不上传到编辑器
- WIN10 安装 ReportBuilder3.msi 提示需要 .NET Framework 4.5
- jqueryValidate
- mock获取入参数并动态设置返回值
- android rom开发
- HTTP请求返回值所代表的含义
- 微信小程序开发——活动规则类文案文件读取及自动转换为小程序排版代码
- sqlserver中利用Tran_sql把逗号分隔的字符串拆成临时表
- 【刷题】BZOJ 2346 [Baltic 2011]Lamp
热门文章
- 【RF库XML测试】parse xml
- Explaining Delegates in C# - Part 1 (Callback and Multicast delegates)
- SpringBoot(六)-- 静态资源处理
- [转]JAVA并发编程学习笔记之Unsafe类
- VS无法导航到插入点F12失败
- Maven编译出现“[ERROR] java.lang.OutOfMemoryError: Java heap space”
- C#编写中使用预编译指令代替不停的注释
- c++学习笔记—动态内存与智能指针浅析
- Xcode - 添加自定义代码提示
- SQL - 根据天来分组比较